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:
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:
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:
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.
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:
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:
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.