Cut Matrix: A Deep Dive into the DP + Binary Search Solution

The Problem, in Plain Words

You're given a grid of 0s and 1s, and a number k. You want to slice the grid into exactly k rectangular pieces, where every piece must contain at least one 1.

The catch is in how you're allowed to cut:

A cut is either horizontal (splits into top/bottom) or vertical (splits into left/right).
After a horizontal cut, only the bottom piece can be cut again.
After a vertical cut, only the right piece can be cut again.

In other words, once you cut off a piece, that piece is "final"—it's locked in as one of your k pieces, and it never gets touched again. Only the remaining rectangle (bottom or right) stays "in play" for further cutting.

We need to count how many distinct sequences of cuts produce exactly k valid pieces, modulo 1e9 + 7.

The Key Observation

At first glance, this looks like it could require tracking arbitrary sub-rectangles of the matrix—which would blow up the state space. But look closely at the cutting rule again:

Horizontal cut → only the bottom survives.
Vertical cut → only the right survives.

This means the "still cuttable" region is never an arbitrary rectangle. It is always a suffix rectangle—defined by a starting row r and starting column c, extending all the way to the bottom-right corner of the original matrix: rows [r, n-1] and columns [c, m-1].

Why? Because:

Cutting horizontally at row i shrinks the top boundary from r to i, but the bottom is still n-1 and columns are untouched.
Cutting vertically at column j shrinks the left boundary from c to j, but the right is still m-1 and rows are untouched.

So no matter how many cuts you chain together, the "remaining piece" is always described by just two numbers: (r, c). That's the whole trick—it turns an exponential-looking problem into something with only O(n * m) possible active regions.

Defining the DP State

We define:

dp[r][c][p] = number of ways to split the suffix-rectangle
              rows [r, n-1], cols [c, m-1]
              into exactly p valid pieces (each containing ≥1 one)

Our final answer is:

dp[0][0][k]

which represents splitting the whole matrix into k pieces.

Base Case: p = 1

If we only need one piece, there's nothing left to cut. It's valid if and only if the rectangle contains at least one 1.

dp[r][c][1] = 1   if sum(rows[r..n-1], cols[c..m-1]) > 0
dp[r][c][1] = 0   otherwise

Recursive Case: p > 1

To split the rectangle (r, c) into p pieces, we make one cut—either horizontal or vertical—that peels off a valid piece, and recurse on the rest with p - 1 pieces remaining.

Horizontal Cut

For a cut at row i (r < i <= n-1):

The piece cut off is rows [r, i-1], columns [c, m-1]. This must contain at least one 1.
The remaining rectangle, rows [i, n-1], columns [c, m-1], must be split into p-1 pieces:

dp[i][c][p-1]

Vertical Cut

For a cut at column j (c < j <= m-1):

The piece cut off is rows [r, n-1], columns [c, j-1]. This must contain at least one 1.
The remaining rectangle is:

dp[r][j][p-1]

So:

dp[r][c][p] = Σ dp[i][c][p-1]  over all valid horizontal cut rows i
            + Σ dp[r][j][p-1]  over all valid vertical cut columns j

If done naively, this sum runs over up to n + m cut positions for every one of the n * m * k states—giving O(n * m * k * (n + m)), which is too slow for the problem's constraints.

Speeding It Up: Monotonicity + Binary Search + Suffix Sums

Two tricks bring this down to the required O(n * m * k * log(n + m)).

Trick 1 — Monotonicity Lets Us Binary Search the Cut Boundary

As the cut row i moves further away from r, the peeled-off piece only grows, so the count of 1s in it is monotonically non-decreasing.

That means:

There is a smallest valid cut index.
Every cut after that index is also valid.

We binary search for this first valid index using the matrix's 2D prefix-sum array (rectSum) to check whether a piece contains at least one 1 in O(1) time.

This costs:

O(log n) for horizontal cuts.
O(log m) for vertical cuts.

Trick 2 — Suffix Sums Replace Repeated DP Summations

Once we know the smallest valid cut index res, we need:

Σ dp[i][c][p-1]   for i = res .. n-1

and

Σ dp[r][j][p-1]   for j = res .. m-1

Instead of summing these ranges every time, we precompute suffix sum arrays once per DP layer.

rowSuffix[c][r] = sum of dp[i][c][p-1] for i = r ... n-1
colSuffix[r][c] = sum of dp[r][j][p-1] for j = c ... m-1

These are built in O(n * m) per layer, and each required range sum becomes a single lookup.

Putting It Together

For each layer p from 1 to k:

Build rowSuffix and colSuffix from the previous DP layer.
For every (r, c):
- Binary search the first valid horizontal cut.
- Binary search the first valid vertical cut.
- Retrieve the DP contribution in O(1) using the suffix arrays.

This gives each state only O(log(n+m)) work, resulting in a total complexity of:

O(n * m * k * log(n + m))

Walking Through Example 1

matrix = [[1, 0, 0],
          [1, 1, 1],
          [0, 0, 0]]

k = 3

The active rectangle starts as the whole matrix (r=0, c=0).

Option A

Horizontal cut after row 0.

Top piece:

[1,0,0]

Valid.

Remaining rectangle:

rows [1,2], cols [0,2]

Need 2 more pieces.

Inside this rectangle:

Vertical cut after column 0 gives one valid split.
Vertical cut after column 1 gives another valid split.

Total from this branch:

2 ways

Option B

Vertical cut after column 0.

Left piece:

[1,1,0]

Valid.

Remaining rectangle:

rows [0,2], cols [1,2]

Need 2 more pieces.

A vertical cut after column 1 produces two valid pieces.

Total:

1 way

Overall:

2 + 1 = 3 ways

which matches the expected output.

Complexity Recap

Metric	Value	Why
Time	O(n · m · k · log(n + m))	k layers × n·m cells × two binary searches per cell
Space	O(n · m · k)	Full 3D DP table plus O(n·m) scratch space reused each layer

Full Java Solution

class Solution {
    static final int MOD = 1000000007;

    public int findWays(int[][] matrix, int k) {
        int n = matrix.length, m = matrix[0].length;

        // 2D prefix sum of ones
        int[][] P = new int[n + 1][m + 1];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                P[i + 1][j + 1] = P[i][j + 1] + P[i + 1][j] - P[i][j] + matrix[i][j];

        int[][][] dp = new int[n][m][k + 1];

        for (int p = 1; p <= k; p++) {
            if (p == 1) {
                for (int r = 0; r < n; r++)
                    for (int c = 0; c < m; c++)
                        dp[r][c][1] = (rectSum(P, r, c, n - 1, m - 1) > 0) ? 1 : 0;
            } else {
                int[][] rowSuffix = new int[m][n + 1];
                for (int c = 0; c < m; c++)
                    for (int r = n - 1; r >= 0; r--)
                        rowSuffix[c][r] = (int)(((long)dp[r][c][p - 1] + rowSuffix[c][r + 1]) % MOD);

                int[][] colSuffix = new int[n][m + 1];
                for (int r = 0; r < n; r++)
                    for (int c = m - 1; c >= 0; c--)
                        colSuffix[r][c] = (int)(((long)dp[r][c][p - 1] + colSuffix[r][c + 1]) % MOD);

                for (int r = 0; r < n; r++) {
                    for (int c = 0; c < m; c++) {
                        if (rectSum(P, r, c, n - 1, m - 1) == 0) {
                            dp[r][c][p] = 0;
                            continue;
                        }

                        long total = 0;

                        if (r + 1 <= n - 1) {
                            int lo = r + 1, hi = n - 1, res = -1;
                            while (lo <= hi) {
                                int mid = (lo + hi) / 2;
                                if (rectSum(P, r, c, mid - 1, m - 1) >= 1) {
                                    res = mid;
                                    hi = mid - 1;
                                } else {
                                    lo = mid + 1;
                                }
                            }
                            if (res != -1) total += rowSuffix[c][res];
                        }

                        if (c + 1 <= m - 1) {
                            int lo = c + 1, hi = m - 1, res = -1;
                            while (lo <= hi) {
                                int mid = (lo + hi) / 2;
                                if (rectSum(P, r, c, n - 1, mid - 1) >= 1) {
                                    res = mid;
                                    hi = mid - 1;
                                } else {
                                    lo = mid + 1;
                                }
                            }
                            if (res != -1) total += colSuffix[r][res];
                        }

                        dp[r][c][p] = (int)(total % MOD);
                    }
                }
            }
        }

        return dp[0][0][k];
    }

    private int rectSum(int[][] P, int r1, int c1, int r2, int c2) {
        if (r1 > r2 || c1 > c2) return 0;
        return P[r2 + 1][c2 + 1] - P[r1][c2 + 1]
             - P[r2 + 1][c1] + P[r1][c1];
    }
}

Takeaways

The elegance of this problem is in noticing that the cutting rule (bottom-only, right-only) restricts the state space to suffix rectangles instead of arbitrary ones. From there:

Prefix sums turn "does this piece contain a 1?" into an O(1) check.
Monotonicity of that check as the cut moves away from the anchor lets us binary search the boundary between an empty piece and a valid piece.
Suffix sums of the DP layer below turn "sum over all cuts past that boundary" into an O(1) lookup.

Together, these take a problem that looks combinatorially explosive down to a clean, polynomial-time DP.

Summary

This solution models the remaining cuttable region as a suffix rectangle, reducing the state space to O(n × m). By combining dynamic programming with 2D prefix sums, binary search, and suffix-sum preprocessing, it efficiently counts all valid cutting sequences in O(n × m × k × log(n + m)) time while ensuring every resulting piece contains at least one 1.