Cut Matrix

Problem Overview

Cut a binary matrix into k pieces with k−1 hard cuts (always giving away the top strip or left strip) so every piece contains at least one 1.

Intuition

Cut a binary matrix into k pieces with k−1 hard cuts (always giving away the top strip or left strip) so every piece contains at least one 1. After each cut the remaining bottom-right rectangle is itself a cutting problem with one fewer piece. Suffix sums of filled cells make “does this rectangle still have a 1?” O(1), and binary search finds the earliest cut that actually peels off a 1 so we never enumerate empty cuts.

Algorithm

1Build suff[i][j] = number of 1s in the submatrix from (i,j) to the bottom-right corner.
2dp[1][r][c] = 1 if suff[r][c] > 0 else 0 — one piece needs only a non-empty filled suffix.
3For rem = 2 … k, first build row- and column-wise suffix sums of dp[rem−1] so any bottom-right rectangle of answers can be queried in O(1).
4For each top-left (r,c) with suff[r][c] > 0, binary-search the first next_r where suff[next_r][c] < suff[r][c] (horizontal cut peels ≥1 filled cell) and add dpSumRow[next_r][c].
5Likewise binary-search next_c for a vertical cut and add dpSumCol[r][next_c]. Store the sum modulo 10⁹+7 in dp[rem][r][c].
6Answer is dp[k][0][0].

Example Walkthrough

Input: matrix = [[1,0,0],[1,1,1],[0,0,0]], k = 3

1. Suffix at (0,0) has four 1s; base cases mark every cell whose suffix still contains a 1.
2. First cut must peel at least one 1 from the top or left of the full matrix.
3. Valid sequences of two cuts that leave three non-empty pieces total 3 ways (same as the classic pizza-cutting example).
4. dp[3][0][0] = 3.

Output: 3

Common Pitfalls

• A cut is invalid if the given-away strip has zero filled cells — that is why next_r / next_c require a strict drop in suffix sum.
• Always cut from the current top-left; you never cut previously given-away regions.
• Modulo after every addition; ways grow quickly with k.
• Skip states with suff[r][c] == 0 early — an empty remaining pizza cannot form rem ≥ 1 valid pieces.
• Binary search must return the first index where the suffix becomes strictly smaller, not merely ≤.

Cut Matrix.java

Java

class Solution {
    // Approach: Count ways to cut the matrix into k pieces so each piece has at
    // least one filled cell. Build a bottom-right suffix sum of filled cells.
    // Let dp[rem][r][c] be ways to cut the submatrix starting at (r,c) into rem
    // pieces. Base rem=1 is 1 iff the suffix is non-empty. For rem>1, binary-search
    // the first horizontal/vertical cut that peels off at least one filled cell,
    // then sum remaining (rem-1)-piece answers with row/column suffix sums of dp.
    // Complexity: O(k·n·m·log(max(n,m))) time and O(k·n·m) space.
    public int findWays(int[][] matrix, int k) {
        int n = matrix.length;
        int m = matrix[0].length;
        int MOD = 1000000007;

        int[][] suff = new int[n + 1][m + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                suff[i][j] = matrix[i][j] + suff[i + 1][j] + suff[i][j + 1] - suff[i + 1][j + 1];
            }
        }

        int[][][] dp = new int[k + 1][n][m];
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (suff[r][c] > 0) {
                    dp[1][r][c] = 1;
                }
            }
        }

        for (int rem = 2; rem <= k; rem++) {
            int[][] dpSumRow = new int[n + 1][m];
            int[][] dpSumCol = new int[n][m + 1];

            for (int r = n - 1; r >= 0; r--) {
                for (int c = m - 1; c >= 0; c--) {
                    dpSumRow[r][c] = (dp[rem - 1][r][c] + dpSumRow[r + 1][c]) % MOD;
                    dpSumCol[r][c] = (dp[rem - 1][r][c] + dpSumCol[r][c + 1]) % MOD;
                }
            }

            for (int r = 0; r < n; r++) {
                for (int c = 0; c < m; c++) {
                    if (suff[r][c] == 0) 
                        continue;
                    long totalWays = 0;
                    int next_r = findNextRow(suff, r, c, n);
                    if (next_r < n) {
                        totalWays = (totalWays + dpSumRow[next_r][c]) % MOD;
                    }
                    
                    int next_c = findNextCol(suff, r, c, m);
                    if (next_c < m) {
                        totalWays = (totalWays + dpSumCol[r][next_c]) % MOD;
                    }

                    dp[rem][r][c] = (int) totalWays;
                }
            }
        }
        return dp[k][0][0];
    }

    private int findNextRow(int[][] suff, int r, int c, int n) {
        int low = r + 1, high = n, ans = n;
        int target = suff[r][c];
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (suff[mid][c] < target) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private int findNextCol(int[][] suff, int r, int c, int m) {
        int low = c + 1, high = m, ans = m;
        int target = suff[r][c];
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (suff[r][mid] < target) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }
}

Was this solution helpful?