Number of Ways of Cutting a Pizza

Hard

#1335Time: O((rows + cols)^k). This is a rough estimate. For each of the `k-1` cuts, there are up to `rows + cols - 2` choices. Since subproblems are recomputed, the complexity is exponential, making it too slow for the given constraints.Space: O(rows * cols + k). `O(rows * cols)` is for the suffix sum grid `apples`, and `O(k)` is for the depth of the recursion call stack.

Patterns

Dynamic Programming Memoization Prefix Sum

Data structures

Array Matrix

Prompt

Given a rectangular pizza represented as a rows x cols matrix containing the following characters: 'A' (an apple) and '.' (empty cell) and given the integer k. You have to cut the pizza into k pieces using k-1 cuts.

For each cut you choose the direction: vertical or horizontal, then you choose a cut position at the cell boundary and cut the pizza into two pieces. If you cut the pizza vertically, give the left part of the pizza to a person. If you cut the pizza horizontally, give the upper part of the pizza to a person. Give the last piece of pizza to the last person.

Return the number of ways of cutting the pizza such that each piece contains at least one apple. Since the answer can be a huge number, return this modulo 10^9 + 7.

Example 1:

Input: pizza = ["A..","AAA","..."], k = 3
Output: 3 
Explanation: The figure above shows the three ways to cut the pizza. Note that pieces must contain at least one apple.

Example 2:

Input: pizza = ["A..","AA.","..."], k = 3
Output: 1

Example 3:

Input: pizza = ["A..","A..","..."], k = 1
Output: 1

Constraints:

1 <= rows, cols <= 50
rows == pizza.length
cols == pizza[i].length
1 <= k <= 10
pizza consists of characters 'A' and '.' only.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a straightforward recursive function to explore all possible sequences of k-1 cuts. The function's state is defined by the current top-left corner of the pizza being considered and the number of cuts still to be made. It systematically tries every possible horizontal and vertical cut. For each cut, it checks if the piece being given away contains at least one apple. If it does, it makes a recursive call for the remaining piece of pizza with one fewer cut. The total number of ways is the sum of the results from all valid recursive calls.

Algorithm

Pre-compute a 2D suffix sum grid apples where apples[i][j] stores the number of apples in the rectangular sub-pizza from (i, j) to (rows-1, cols-1). This allows for O(1) queries to find the number of apples in any rectangular piece.
Define a recursive function solve(row, col, cuts_left) that returns the number of ways to cut the pizza starting at (row, col) with cuts_left cuts remaining.
Base Case: If cuts_left is 0, it means we have made k-1 cuts. The current sub-pizza is the last piece. If it contains at least one apple (i.e., apples[row][col] > 0), we have found one valid sequence of cuts, so return 1. Otherwise, return 0.
Recursive Step:
- Initialize count = 0.
- Horizontal Cuts: Iterate through all possible horizontal cut positions h from row + 1 to rows - 1. For each h, the top piece is the rectangle from (row, col) to (h-1, cols-1). Check if this piece has at least one apple using the pre-computed apples grid. If it does, this is a valid first cut. Recursively call solve(h, col, cuts_left - 1) for the remaining bottom piece and add the result to count.
- Vertical Cuts: Similarly, iterate through all vertical cut positions v from col + 1 to cols - 1. If the left piece has an apple, recursively call solve(row, v, cuts_left - 1) for the remaining right piece and add the result to count.
Return the total count modulo 10^9 + 7.
The initial call to start the process is solve(0, 0, k - 1).

Walkthrough

The core of this method is a recursive helper function, let's call it solve(row, col, cuts_left). This function calculates the number of valid ways to cut the sub-pizza whose top-left corner is at (row, col) and extends to the original pizza's bottom-right corner, given that we still need to make cuts_left cuts.

To avoid repeatedly scanning the grid to check for apples, we first pre-process the pizza into a 2D suffix sum array, apples. apples[i][j] will store the total number of apples in the rectangle from (i, j) to (rows-1, cols-1). This allows us to determine if any rectangular piece has apples in constant time.

The recursion proceeds by exploring all valid cuts. A horizontal cut at row h is valid if the top piece (rows row to h-1) has apples. A vertical cut at column v is valid if the left piece (columns col to v-1) has apples. For each valid cut, we recurse on the remaining piece. The base case for the recursion is when cuts_left becomes 0. At this point, if the final remaining piece has at least one apple, we've found one valid way.

However, this naive recursion re-solves the same subproblems multiple times. For example, solve(r, c, cuts) might be called through different sequences of initial cuts, leading to an exponential number of calls.

Complexity

Time

O((rows + cols)^k). This is a rough estimate. For each of the `k-1` cuts, there are up to `rows + cols - 2` choices. Since subproblems are recomputed, the complexity is exponential, making it too slow for the given constraints.

Space

O(rows * cols + k). `O(rows * cols)` is for the suffix sum grid `apples`, and `O(k)` is for the depth of the recursion call stack.

Trade-offs

Pros

Conceptually simple and directly translates the problem statement into code.
Serves as a good foundation for more optimized dynamic programming solutions.

Cons

Extremely inefficient due to a massive number of redundant computations for the same subproblems (same row, col, and cuts_left).
Will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest test cases.

This approach significantly optimizes the brute-force recursion by using memoization, a technique also known as top-down dynamic programming. The key idea is to store the results of subproblems so that we don't have to re-compute them. We use a 3D array, memo[cuts][row][col], to store the result for each state. Before the function computes the number of ways for a given state, it first checks if the result is already in the memo table. If it is, it returns the stored value. Otherwise, it computes the result, stores it in the table for future use, and then returns it. This avoids the exponential complexity of the naive recursive solution.

Algorithm

Pre-compute the apples suffix sum grid, same as the brute-force approach.
Create a 3D memoization table, memo[k][rows][cols], initialized with a sentinel value (e.g., null or -1) to indicate that a state has not been computed.
Define the recursive function solve(row, col, cuts_left).
At the beginning of the function, check if memo[cuts_left][row][col] has been computed. If yes, return the stored value immediately.
If the current piece from (row, col) has no apples (apples[row][col] == 0), no valid cuts are possible. Return 0.
Base Case: If cuts_left == 0, return 1 (since the check for apples in the current piece passed in step 5).
Recursive Step: Perform the same logic as the brute-force approach to iterate through horizontal and vertical cuts, making recursive calls for valid cuts.
Before returning the computed count, store it in the memoization table: memo[cuts_left][row][col] = count.
Return the count.
The initial call is solve(0, 0, k - 1).

Walkthrough

This method enhances the previous recursive solution by adding a cache (memoization table) to store the results of subproblems that have already been solved. The state of a subproblem is uniquely identified by (cuts_left, row, col). We use a 3D array, memo, for this purpose.

The recursive function solve(row, col, cuts_left) first checks memo[cuts_left][row][col]. If a value exists, it's returned directly, preventing re-computation. If not, the function proceeds as before: it calculates the number of ways by trying all valid horizontal and vertical cuts and summing the results from the corresponding recursive calls. The final computed value is then stored in memo[cuts_left][row][col] before being returned. This ensures that each of the k * rows * cols possible states is computed at most once, drastically improving the time complexity.

1class Solution {2    private int MOD = 1_000_000_007;3    private int rows;4    private int cols;5    private Integer[][][] memo;6    private int[][] apples;7 8    public int ways(String[] pizza, int k) {9        rows = pizza.length;10        cols = pizza[0].length();11        memo = new Integer[k][rows][cols];12        apples = new int[rows + 1][cols + 1];13 14        // Precompute suffix sums of apples15        for (int r = rows - 1; r >= 0; r--) {16            for (int c = cols - 1; c >= 0; c--) {17                apples[r][c] = (pizza[r].charAt(c) == 'A' ? 1 : 0) 18                             + apples[r + 1][c] 19                             + apples[r][c + 1] 20                             - apples[r + 1][c + 1];21            }22        }23 24        return solve(0, 0, k - 1);25    }26 27    private int solve(int r, int c, int cuts) {28        // If the current piece has no apples, no valid cuts can be made.29        if (apples[r][c] == 0) {30            return 0;31        }32        // Base case: k-1 cuts made, this is the last piece.33        // If it has at least one apple (checked above), it's a valid way.34        if (cuts == 0) {35            return 1;36        }37        // If result is already computed, return it.38        if (memo[cuts][r][c] != null) {39            return memo[cuts][r][c];40        }41 42        long count = 0;43 44        // Horizontal cuts45        for (int nr = r + 1; nr < rows; nr++) {46            // Check if the upper piece has at least one apple47            if (apples[r][c] - apples[nr][c] > 0) {48                count = (count + solve(nr, c, cuts - 1)) % MOD;49            }50        }51 52        // Vertical cuts53        for (int nc = c + 1; nc < cols; nc++) {54            // Check if the left piece has at least one apple55            if (apples[r][c] - apples[r][nc] > 0) {56                count = (count + solve(r, nc, cuts - 1)) % MOD;57            }58        }59 60        return memo[cuts][r][c] = (int) count;61    }62}

Complexity

Time

O(k * rows * cols * (rows + cols)). There are `k * rows * cols` states. For each state, we iterate through `O(rows)` possible horizontal cuts and `O(cols)` possible vertical cuts.

Space

O(k * rows * cols). This is dominated by the size of the memoization table. The recursion stack adds `O(k)`.

Trade-offs

Pros

Efficient enough to pass within the given constraints.
Relatively intuitive to implement as it follows the logical flow of recursion.
Correctly handles overlapping subproblems.

Cons

Uses O(k * rows * cols) space for the memoization table, which can be significant.
May have a slight performance overhead compared to the iterative version due to recursion function calls.

This approach, also known as bottom-up dynamic programming, is an iterative version of the memoized recursion. It eliminates recursion entirely, often leading to better performance by avoiding function call overhead and potential stack overflow issues. We build the solution from the simplest case (0 cuts) up to the desired k-1 cuts. We use a DP table, dp[r][c], to store the number of ways to cut the pizza starting at (r, c) for a given number of cuts. By iterating from 0 to k-1 cuts, we can compute the values for the current number of cuts based on the values computed for the previous number of cuts. This approach can also be space-optimized, as calculating the ways for c cuts only requires the results for c-1 cuts.

Algorithm

Pre-compute the apples suffix sum grid as in the other approaches.
Create a 2D DP table, dp[rows][cols]. This will store the number of ways for the current number of cuts being processed.
Base Case (k=1 piece, 0 cuts): Initialize dp[r][c] = 1 if the sub-pizza from (r, c) has at least one apple (apples[r][c] > 0), and 0 otherwise. This dp table now holds the answers for making 0 cuts.
Iteration: Loop for the number of cuts c from 1 to k-1.
- Inside this loop, create a newDp[rows][cols] table to store the results for the current number of cuts c.
- Iterate through each cell (r, c) from (0, 0) to (rows-1, cols-1).
- To calculate newDp[r][c], sum up the ways from the previous state (dp table):
  - Horizontal Cuts: Iterate h from r + 1 to rows - 1. If the top piece (from r to h-1) has an apple, add dp[h][c] to the total for newDp[r][c].
  - Vertical Cuts: Iterate v from c + 1 to cols - 1. If the left piece (from c to v-1) has an apple, add dp[r][v] to the total.
- After computing newDp for all (r, c), update dp = newDp for the next iteration.
After the loops complete, the answer is dp[0][0], which represents the number of ways to cut the whole pizza k-1 times.

Walkthrough

The bottom-up DP approach tabulates the results iteratively. We start with the base case: the number of ways to have 1 piece (i.e., 0 cuts). This is 1 for any sub-pizza that contains at least one apple, and 0 otherwise. We store this in a 2D array dp[rows][cols].

Then, we iterate from cuts = 1 to k-1. In each iteration, we compute the number of ways to get cuts + 1 pieces. We use a new table, newDp, to store these results. The value newDp[r][c] is calculated by summing up the valid ways from the previous dp table. A horizontal cut at h contributes dp[h][c] ways if the top piece is valid. A vertical cut at v contributes dp[r][v] ways if the left piece is valid. After filling the newDp table for all (r, c), we replace the old dp table with newDp and proceed to the next number of cuts.

This process continues until we have computed the results for k-1 cuts. The final answer is the value at dp[0][0].

1class Solution {2    public int ways(String[] pizza, int k) {3        int rows = pizza.length;4        int cols = pizza[0].length();5        int MOD = 1_000_000_007;6 7        int[][] apples = new int[rows + 1][cols + 1];8        for (int r = rows - 1; r >= 0; r--) {9            for (int c = cols - 1; c >= 0; c--) {10                apples[r][c] = (pizza[r].charAt(c) == 'A' ? 1 : 0) 11                             + apples[r + 1][c] 12                             + apples[r][c + 1] 13                             - apples[r + 1][c + 1];14            }15        }16 17        int[][] dp = new int[rows][cols];18        // Base case: for 1 piece (0 cuts), there's 1 way if the piece has an apple.19        for (int r = 0; r < rows; r++) {20            for (int c = 0; c < cols; c++) {21                if (apples[r][c] > 0) {22                    dp[r][c] = 1;23                }24            }25        }26 27        // Iterate for number of cuts from 1 to k-128        for (int cuts = 1; cuts < k; cuts++) {29            int[][] newDp = new int[rows][cols];30            for (int r = 0; r < rows; r++) {31                for (int c = 0; c < cols; c++) {32                    long count = 0;33                    // Horizontal cuts34                    for (int nr = r + 1; nr < rows; nr++) {35                        // Check if upper piece has an apple36                        if (apples[r][c] > apples[nr][c]) {37                            count = (count + dp[nr][c]) % MOD;38                        }39                    }40                    // Vertical cuts41                    for (int nc = c + 1; nc < cols; nc++) {42                        // Check if left piece has an apple43                        if (apples[r][c] > apples[r][nc]) {44                            count = (count + dp[r][nc]) % MOD;45                        }46                    }47                    newDp[r][c] = (int) count;48                }49            }50            dp = newDp;51        }52 53        return dp[0][0];54    }55}

Complexity

Time

O(k * rows * cols * (rows + cols)). The complexity is determined by the nested loops: `k` for cuts, `rows*cols` for the cells, and `rows+cols` for iterating through possible cut locations.

Space

O(rows * cols). We need space for the `apples` grid and two `dp` tables (current and previous), each of size `rows * cols`.

Trade-offs

Pros

Generally the most performant solution in practice due to the absence of recursion overhead.
Avoids potential stack overflow errors for very deep recursion (though not an issue with k <= 10).
Space complexity is optimized to O(rows * cols) instead of O(k * rows * cols).

Cons

The logic can be slightly less intuitive to formulate compared to the top-down recursive approach.

Solutions

Solution

1class Solution {2private3  int m;4private5  int n;6private7  int[][] s;8private9  Integer[][][] f;10private11  final int mod = (int)1 e9 + 7;12public13  int ways(String[] pizza, int k) {14    m = pizza.length;15    n = pizza[0].length();16    s = new int[m + 1][n + 1];17    f = new Integer[m][n][k];18    for (int i = 1; i <= m; ++i) {19      for (int j = 1; j <= n; ++j) {20        int x = pizza[i - 1].charAt(j - 1) == 'A' ? 1 : 0;21        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;22      }23    }24    return dfs(0, 0, k - 1);25  }26private27  int dfs(int i, int j, int k) {28    if (k == 0) {29      return s[m][n] - s[i][n] - s[m][j] + s[i][j] > 0 ? 1 : 0;30    }31    if (f[i][j][k] != null) {32      return f[i][j][k];33    }34    int ans = 0;35    for (int x = i + 1; x < m; ++x) {36      if (s[x][n] - s[i][n] - s[x][j] + s[i][j] > 0) {37        ans = (ans + dfs(x, j, k - 1)) % mod;38      }39    }40    for (int y = j + 1; y < n; ++y) {41      if (s[m][y] - s[i][y] - s[m][j] + s[i][j] > 0) {42        ans = (ans + dfs(i, y, k - 1)) % mod;43      }44    }45    return f[i][j][k] = ans;46  }47}

1class Solution {2public:3  int ways(vector<string> &pizza, int k) {4    const int mod = 1e9 + 7;5    int m = pizza.size(), n = pizza[0].size();6    vector<vector<vector<int>>> f(m,7                                  vector<vector<int>>(n, vector<int>(k, -1)));8    vector<vector<int>> s(m + 1, vector<int>(n + 1));9    for (int i = 1; i <= m; ++i) {10      for (int j = 1; j <= n; ++j) {11        int x = pizza[i - 1][j - 1] == 'A' ? 1 : 0;12        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;13      }14    }15    function<int(int, int, int)> dfs = [&](int i, int j, int k) -> int {16      if (k == 0) {17        return s[m][n] - s[i][n] - s[m][j] + s[i][j] > 0 ? 1 : 0;18      }19      if (f[i][j][k] != -1) {20        return f[i][j][k];21      }22      int ans = 0;23      for (int x = i + 1; x < m; ++x) {24        if (s[x][n] - s[i][n] - s[x][j] + s[i][j] > 0) {25          ans = (ans + dfs(x, j, k - 1)) % mod;26        }27      }28      for (int y = j + 1; y < n; ++y) {29        if (s[m][y] - s[i][y] - s[m][j] + s[i][j] > 0) {30          ans = (ans + dfs(i, y, k - 1)) % mod;31        }32      }33      return f[i][j][k] = ans;34    };35    return dfs(0, 0, k - 1);36  }37};

1class Solution:2    def ways(self, pizza: List[str], k: int) -> int: @ cache def dfs(i: int, j: int, k: int) -> int: if k == 0: return int(s[m][n] - s[i][n] - s[m][j] + s[i][j] > 0) ans = 0 for x in range(i + 1, m): if s[x][n] - s[i][n] - s[x][j] + s[i][j] > 0: ans += dfs(x, j, k - 1) for y in range(j + 1, n): if s[m][y] - s[i][y] - s[m][j] + s[i][j] > 0: ans += dfs(i, y, k - 1) return ans % mod mod = 10 ** 9 + 7 m, n = len(pizza), len(pizza[0]) s = [[0] * (n + 1) for _ in range(m + 1)] for i, row in enumerate(pizza, 1): for j, c in enumerate(row, 1): s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + int(c == 'A') return dfs(0, 0, k - 1)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  int m;4private5  int n;6private7  int[][] s;8private9  Integer[][][] f;10private11  final int mod = (int)1 e9 + 7;12public13  int ways(String[] pizza, int k) {14    m = pizza.length;15    n = pizza[0].length();16    s = new int[m + 1][n + 1];17    f = new Integer[m][n][k];18    for (int i = 1; i <= m; ++i) {19      for (int j = 1; j <= n; ++j) {20        int x = pizza[i - 1].charAt(j - 1) == 'A' ? 1 : 0;21        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;22      }23    }24    return dfs(0, 0, k - 1);25  }26private27  int dfs(int i, int j, int k) {28    if (k == 0) {29      return s[m][n] - s[i][n] - s[m][j] + s[i][j] > 0 ? 1 : 0;30    }31    if (f[i][j][k] != null) {32      return f[i][j][k];33    }34    int ans = 0;35    for (int x = i + 1; x < m; ++x) {36      if (s[x][n] - s[i][n] - s[x][j] + s[i][j] > 0) {37        ans = (ans + dfs(x, j, k - 1)) % mod;38      }39    }40    for (int y = j + 1; y < n; ++y) {41      if (s[m][y] - s[i][y] - s[m][j] + s[i][j] > 0) {42        ans = (ans + dfs(i, y, k - 1)) % mod;43      }44    }45    return f[i][j][k] = ans;46  }47}

1class Solution {2public:3  int ways(vector<string> &pizza, int k) {4    const int mod = 1e9 + 7;5    int m = pizza.size(), n = pizza[0].size();6    vector<vector<vector<int>>> f(m,7                                  vector<vector<int>>(n, vector<int>(k, -1)));8    vector<vector<int>> s(m + 1, vector<int>(n + 1));9    for (int i = 1; i <= m; ++i) {10      for (int j = 1; j <= n; ++j) {11        int x = pizza[i - 1][j - 1] == 'A' ? 1 : 0;12        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;13      }14    }15    function<int(int, int, int)> dfs = [&](int i, int j, int k) -> int {16      if (k == 0) {17        return s[m][n] - s[i][n] - s[m][j] + s[i][j] > 0 ? 1 : 0;18      }19      if (f[i][j][k] != -1) {20        return f[i][j][k];21      }22      int ans = 0;23      for (int x = i + 1; x < m; ++x) {24        if (s[x][n] - s[i][n] - s[x][j] + s[i][j] > 0) {25          ans = (ans + dfs(x, j, k - 1)) % mod;26        }27      }28      for (int y = j + 1; y < n; ++y) {29        if (s[m][y] - s[i][y] - s[m][j] + s[i][j] > 0) {30          ans = (ans + dfs(i, y, k - 1)) % mod;31        }32      }33      return f[i][j][k] = ans;34    };35    return dfs(0, 0, k - 1);36  }37};

1class Solution:2    def ways(self, pizza: List[str], k: int) -> int: @ cache def dfs(i: int, j: int, k: int) -> int: if k == 0: return int(s[m][n] - s[i][n] - s[m][j] + s[i][j] > 0) ans = 0 for x in range(i + 1, m): if s[x][n] - s[i][n] - s[x][j] + s[i][j] > 0: ans += dfs(x, j, k - 1) for y in range(j + 1, n): if s[m][y] - s[i][y] - s[m][j] + s[i][j] > 0: ans += dfs(i, y, k - 1) return ans % mod mod = 10 ** 9 + 7 m, n = len(pizza), len(pizza[0]) s = [[0] * (n + 1) for _ in range(m + 1)] for i, row in enumerate(pizza, 1): for j, c in enumerate(row, 1): s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + int(c == 'A') return dfs(0, 0, k - 1)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.