1444. Number of Ways of Cutting a Pizza


Problem Description

The problem asks us to cut a rows x cols pizza into k pieces with k-1 cuts, ensuring that each piece contains at least one apple ('A'). An empty cell is represented by a '.'. The cuts can be made either horizontally or vertically, and the direction determines which piece is given away (left part for vertical cuts, upper part for horizontal cuts). The last piece is always given to the last person. The task is to determine the number of possible ways to cut the pizza complying with the mentioned conditions. The result should be returned modulo 10^9 + 7 due to the potential size of the number.

Intuition

To solve the problem, we observe that:

  1. We can perform each cut based on the boundary of cells, either cutting horizontally or vertically.

  2. After every cut, the remaining pizza is smaller, and we then need to find a solution for this smaller pizza with one less cut to make.

  3. When making a cut, we need to ensure that there is at least one apple on the side of the pizza we are giving away.

  4. Every cut divides the problem into a smaller subproblem, which suggests that the problem can be approached recursively or through dynamic programming.

The solution to this problem relies on dynamic programming to avoid re-computation of subproblems. We compute the number of valid cuts from every possible starting position and for every number of cuts remaining, memoizing these computations to speed up the calculation.

The key approaches for the solution are:

  • Precomputing the number of apples in a submatrix to quickly decide whether a cut is valid.
  • Using recursion with memoization (or dynamic programming) to explore all feasible ways to cut the remaining pizza with the remaining number of cuts.
  • Ensuring that cuts only occur if they leave at least one apple on the given away piece.
  • Using modulo arithmetic to handle large numbers, as required by the problem statement.

By utilizing these concepts, the dfs (depth-first search) function can count the number of ways to cut the remaining pizza with the specified number of cuts left. It does this by iterating over all possible cut positions and checking for a valid cut, where a valid cut is one that leaves at least one apple on the pizza being given away. If a valid cut is found, the function recursively computes the number of ways to cut the resulting smaller piece.

The base case for the recursion is when k equals 0, which signifies only one piece left without further cuts. At this point, if there is at least one apple on the pizza, the function returns 1; otherwise, it returns 0.

Solution Approach

To implement the solution, we use several strategies from dynamic programming and recursion to handle the complexity of the problem.

  1. Dynamic Programming (Memoization): We use the @cache decorator on the dfs function, which triggers memoization. This means that once we compute the number of ways to cut a piece of pizza with a certain number of cuts left, we don't need to compute it again for the same parameters.

  2. Precomputing Apple Count: We construct a 2D prefix-sum matrix (s in the code) that allows us to quickly look up the number of apples in any rectangular submatrix of the pizza. This is done through the expression s[m][n] - s[i][n] - s[m][j] + s[i][j], which gives the number of apples between the corners (i, j) and (m, n). It uses the inclusion-exclusion principle to subtract and add the appropriate prefix sums.

  3. Recursion and Base Case: The dfs function represents the recursive depth-first search. Its purpose is to determine the number of ways to cut the remaining pizza when it starts from the upper left corner at (i, j) with k cuts remaining. The base case occurs when k is 0, meaning no more cuts are needed. If at least one apple is present in that piece, the function should return 1, signifying one valid way to cut.

  4. Recursion for Cutting: When k is greater than 0, the function tries to cut the pizza both horizontally and vertically starting from the next row or column. For each position, it first checks whether the cut would result in a valid piece containing at least one apple before making the recursive call to dfs. The number of ways from these recursive calls is then added to the answer (ans).

  5. Modulo Operation: Given the potentially huge number of ways to cut the pizza, the problem requires that answers be given modulo 10^9 + 7. To adhere to this, the result of the recursive calls is modulus with this number right before the function returns to ensure all intermediate calculations remain within the required bounds.

  6. Edge Case Handling: The solution only attempts cuts that strictly leave apples in the portion being distributed; this is managed by the conditions inside the for-loops. If the submatrix defined by the next row or column onwards does not have an apple, we do not make a recursive call for that cut.

The algorithm is efficient because of its use of memoization and the prefix sum matrix which reduce the runtime from exponential to polynomial complexity. As a result, despite the potentially large search space, the solution can be computed in a reasonable time.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's illustrate the solution approach with a small example of a 3x3 pizza and we want to make k=3 cuts. The pizza looks like this:

1. . A
2A . .
3. A .

We define k-1=2 cuts to divide the pizza into k=3 pieces. Here's how we apply the solution:

  1. Precomputing Apple Count: We first construct the prefix-sum matrix. For the given pizza, it would look like this:

    1s[0] = [0, 0, 1]
    2s[1] = [1, 1, 2]
    3s[2] = [1, 2, 3]

    This matrix helps us to query the apple count in any submatrix in O(1) time.

  2. Recursive dfs with Memoization: We use a recursive depth-first search that leverages memoization to avoid re-computation.

    • We start with dfs(0, 0, 3) where (0, 0) is the upper left corner of the pizza and 3 is the number of pieces we need.
    • Since we need to make 2 cuts to get 3 pieces, the dfs function will explore all possible horizontal and vertical cuts.
  3. Performing Cuts: The function will try all horizontal cuts below the first row and all vertical cuts to the right of the first column while ensuring that each piece has at least one apple.

    For example:

    • Cut horizontally below the first row. Since there's no apple in this row, we move to the next row.
    • Cut horizontally below the second row, and check if the upper piece (first and second row) has at least one apple using the prefix-sum matrix. It does, so we proceed to the next subproblem dfs(2, 0, 2) (now starting from row '2', column '0' with 2 pieces needed).
  4. Base Case and Recursive Calls:

    Continuing with the previous point:

    • Our new dfs call is dfs(2, 0, 2). Now our base case is k=1. Since there is 1 apple in the new submatrix (2, 0) to (3, 3), we return 1.
    • Backtracking, we attempt other cuts like a vertical cut after the first column, and so on for all possibilities.
  5. Modulo Operation: Each time we come up with a count, we take it modulo 10^9 + 7 to handle large numbers.

  6. Adding Valid Cuts: Every time we find a valid cut, which gives at least one apple piece, we add them up, which after modulo operation gives us the count for that dfs call.

For this example, the algorithm explores different cut configurations and counts the valid ones. The main goal of the example is to simplify the understanding of the process, rather than to count all valid cuts manually, which can be tedious. The efficiency comes from avoiding the repetition of state calculations due to memoization and checking for valid cuts rapidly using the prefix-sum matrix.

Python Solution

1from typing import List
2from functools import lru_cache
3
4class Solution:
5    def ways(self, pizza: List[str], k: int) -> int:
6        # Helper function to calculate ways using dynamic programming with memoization.
7        @lru_cache(None)
8        def dfs(row: int, col: int, remaining_cuts: int) -> int:
9            # If no more cuts need to be made, return 1 if there's at least one apple, else 0.
10            if remaining_cuts == 0:
11                return int(apple_prefix_sum[rows][cols] - apple_prefix_sum[row][cols] -
12                           apple_prefix_sum[rows][col] + apple_prefix_sum[row][col] > 0)
13            ways_to_cut = 0
14            # Try cutting horizontally, and recursively find ways for the remaining part.
15            for x in range(row + 1, rows):
16                if apple_prefix_sum[x][cols] - apple_prefix_sum[row][cols] -
17                   apple_prefix_sum[x][col] + apple_prefix_sum[row][col] > 0:
18                    ways_to_cut += dfs(x, col, remaining_cuts - 1)
19            # Try cutting vertically, and recursively find ways for the remaining part.
20            for y in range(col + 1, cols):
21                if apple_prefix_sum[rows][y] - apple_prefix_sum[row][y] -
22                   apple_prefix_sum[rows][col] + apple_prefix_sum[row][col] > 0:
23                    ways_to_cut += dfs(row, y, remaining_cuts - 1)
24            # Return the number of ways, modulo the large prime number.
25            return ways_to_cut % mod
26
27        # Define a large prime number to take modulo with the possible ways to avoid overflow.
28        mod = 10**9 + 7
29        rows, cols = len(pizza), len(pizza[0])
30        # Calculate the prefix sum of apples to make queries of apples in a rectangle O(1).
31        apple_prefix_sum = [[0] * (cols + 1) for _ in range(rows + 1)]
32        for i, row in enumerate(pizza, 1):
33            for j, cell in enumerate(row, 1):
34                apple_prefix_sum[i][j] = (apple_prefix_sum[i - 1][j] + apple_prefix_sum[i][j - 1] -
35                                           apple_prefix_sum[i - 1][j - 1] + int(cell == 'A'))
36        # Start the DFS from the top-left corner of the pizza with k-1 cuts remaining.
37        return dfs(0, 0, k - 1)
38
39# The code can be tested by creating an instance of the Solution class and calling the ways method:
40# solution = Solution()
41# number_of_ways = solution.ways(["A..","AAA","..."], 3)
42# print(number_of_ways) # this should print the number of ways the pizza can be cut.
43

Java Solution

1class Solution {
2    private int rows;
3    private int cols;
4    private int[][] cumulativeApples;
5    private Integer[][][] memo;
6    private final int MOD = (int) 1e9 + 7;
7
8    public int ways(String[] pizza, int k) {
9        rows = pizza.length;
10        cols = pizza[0].length();
11        cumulativeApples = new int[rows + 1][cols + 1];
12        memo = new Integer[rows][cols][k];
13
14        // Build a cumulative sum matrix to count apples in O(1)
15        for (int i = 1; i <= rows; ++i) {
16            for (int j = 1; j <= cols; ++j) {
17                int hasApple = pizza[i - 1].charAt(j - 1) == 'A' ? 1 : 0;
18                cumulativeApples[i][j] = cumulativeApples[i - 1][j]
19                                        + cumulativeApples[i][j - 1]
20                                        - cumulativeApples[i - 1][j - 1]
21                                        + hasApple;
22            }
23        }
24        // Start the DFS from the top-left corner of the pizza
25        return dfs(0, 0, k - 1);
26    }
27
28    private int dfs(int i, int j, int k) {
29        // Base case: if no more cuts are needed, check if current piece has at least one apple
30        if (k == 0) {
31            return hasApple(i, j, rows - 1, cols - 1) ? 1 : 0;
32        }
33        // Return memoized result if it exists
34        if (memo[i][j][k] != null) {
35            return memo[i][j][k];
36        }
37
38        int waysToCut = 0;
39
40        // Try cutting horizontally
41        for (int x = i + 1; x < rows; ++x) {
42            if (hasApple(i, j, x - 1, cols - 1)) {
43                waysToCut = (waysToCut + dfs(x, j, k - 1)) % MOD;
44            }
45        }
46
47        // Try cutting vertically
48        for (int y = j + 1; y < cols; ++y) {
49            if (hasApple(i, j, rows - 1, y - 1)) {
50                waysToCut = (waysToCut + dfs(i, y, k - 1)) % MOD;
51            }
52        }
53
54        // Store the result in memo and return it
55        memo[i][j][k] = waysToCut;
56        return waysToCut;
57    }
58  
59    // Helper method to check if there's at least one apple in the given rectangle
60    private boolean hasApple(int rowStart, int colStart, int rowEnd, int colEnd) {
61        return cumulativeApples[rowEnd + 1][colEnd + 1]
62             - cumulativeApples[rowStart][colEnd + 1]
63             - cumulativeApples[rowEnd + 1][colStart]
64             + cumulativeApples[rowStart][colStart] > 0;
65    }
66}
67

C++ Solution

1class Solution {
2public:
3    // Computes the number of ways to cut the pizza into k pieces, each with at least one apple.
4    int ways(vector<string>& pizza, int k) {
5        const int mod = 1e9 + 7; // The modulo value for the result to prevent integer overflow
6        int rows = pizza.size(), cols = pizza[0].size();
7        // Dynamic programming cache, initialized to -1 to indicate uncomputed values
8        vector<vector<vector<int>>> dp(rows, vector<vector<int>>(cols, vector<int>(k, -1)));
9        // Prefix sum array to efficiently calculate the number of apples in any subrectangle
10        vector<vector<int>> prefixSum(rows + 1, vector<int>(cols + 1));
11
12        // Build the prefix sum array
13        for (int i = 1; i <= rows; i++) {
14            for (int j = 1; j <= cols; j++) {
15                int hasApple = pizza[i - 1][j - 1] == 'A' ? 1 : 0;
16                prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + hasApple;
17            }
18        }
19
20        // Depth-first search with memoization to find the number of ways to cut the pizza
21        function<int(int, int, int)> dfs = [&](int x, int y, int piecesRemaining) -> int {
22            // Base case: no more cuts needed, check for at least one apple
23            if (piecesRemaining == 0) {
24                return (prefixSum[rows][cols] - prefixSum[x][cols] - prefixSum[rows][y] + prefixSum[x][y] > 0) ? 1 : 0;
25            }
26            // Return the cached value if already computed
27            if (dp[x][y][piecesRemaining] != -1) {
28                return dp[x][y][piecesRemaining];
29            }
30
31            int ways = 0; // Number of ways to cut the remaining pizza
32
33            // Try cutting horizontally and make recursive calls
34            for (int newRow = x + 1; newRow < rows; newRow++) {
35                if (prefixSum[newRow][cols] - prefixSum[x][cols] - prefixSum[newRow][y] + prefixSum[x][y] > 0) {
36                    ways = (ways + dfs(newRow, y, piecesRemaining - 1)) % mod;
37                }
38            }
39
40            // Try cutting vertically and make recursive calls
41            for (int newCol = y + 1; newCol < cols; newCol++) {
42                if (prefixSum[rows][newCol] - prefixSum[x][newCol] - prefixSum[rows][y] + prefixSum[x][y] > 0) {
43                    ways = (ways + dfs(x, newCol, piecesRemaining - 1)) % mod;
44                }
45            }
46
47            // Cache and return the computed value
48            return dp[x][y][piecesRemaining] = ways;
49        };
50
51        // Start the DFS with the entire pizza and k - 1 cuts left
52        return dfs(0, 0, k - 1);
53    }
54};
55

Typescript Solution

1function ways(pizza: string[], cutCount: number): number {
2    // Define the modulo to prevent overflow when dealing with large numbers
3    const MOD = 1e9 + 7;
4    const rows = pizza.length;
5    const cols = pizza[0].length;
6  
7    // memoization array to store previously calculated values
8    const memo = new Array(rows)
9      .fill(0)
10      .map(() => new Array(cols)
11        .fill(0)
12        .map(() => new Array(cutCount).fill(-1)));
13    
14    // prefix sum array to calculate the number of apple pieces in any rectangular slice
15    const prefixSum = new Array(rows + 1)
16      .fill(0)
17      .map(() => new Array(cols + 1).fill(0));
18
19    // Compute the prefix sum
20    for (let i = 1; i <= rows; ++i) {
21        for (let j = 1; j <= cols; ++j) {
22            const hasApple = pizza[i - 1][j - 1] === 'A' ? 1 : 0;
23            prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + hasApple;
24        }
25    }
26
27    // Depth First Search function to find the number of ways to cut the pizza
28    const dfs = (row: number, col: number, remainingCuts: number): number => {
29        // If we've computed this subproblem before, return the stored value
30        if (memo[row][col][remainingCuts] !== -1) {
31            return memo[row][col][remainingCuts];
32        }
33      
34        // Base case: If there are no cuts left, check if there are apples in the remaining piece
35        if (remainingCuts === 0) {
36            return (prefixSum[rows][cols] - prefixSum[row][cols] - prefixSum[rows][col] + prefixSum[row][col] > 0) ? 1 : 0;
37        }
38      
39        // Start with 0 ways and calculate the number of ways by splitting further
40        let waysToCut = 0;
41      
42        // Try cutting horizontally and recurse on the subproblem
43        for (let x = row + 1; x < rows; ++x) {
44            if (prefixSum[x][cols] - prefixSum[row][cols] - prefixSum[x][col] + prefixSum[row][col] > 0) {
45                waysToCut = (waysToCut + dfs(x, col, remainingCuts - 1)) % MOD;
46            }
47        }
48        // Try cutting vertically and recurse on the subproblem
49        for (let y = col + 1; y < cols; ++y) {
50            if (prefixSum[rows][y] - prefixSum[row][y] - prefixSum[rows][col] + prefixSum[row][col] > 0) {
51                waysToCut = (waysToCut + dfs(row, y, remainingCuts - 1)) % MOD;
52            }
53        }
54
55        // Memoize and return the number of ways to cut from this subproblem
56        return memo[row][col][remainingCuts] = waysToCut;
57    };
58  
59    // Initiate the DFS with the entire pizza and one less cut (since k slices require k-1 cuts)
60    return dfs(0, 0, cutCount - 1);
61}
62

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by several factors:

  1. There are m * n states due to the matrix size.
  2. For each state, we can potentially make m + n recursive calls since we are considering cuts along rows and columns.
  3. Each recursive call decreases the value of k, and we have k pieces to cut, which adds another layer of complexity.

Hence, the upper bound for the time complexity would be O((m * n) * (m + n) * k). However, due to memoization with @cache, each state is only computed once. This reduces the time complexity significantly.

After memoization, the time complexity becomes O(m * n * k) because each state (i, j, k) is only computed once, and we make at most m + n calls in each state.

Space Complexity

The space complexity is also affected by two key components:

  1. The caching of results which potentially stores m * n * k states.
  2. The auxiliary space used by the recursion stack, which in the worst-case scenario could also go up to k levels deep.

As a result, the space complexity is O(m * n * k) for storing the results, along with the space taken by the recursion stack, which is O(k). The total space complexity can therefore be denoted by O(m * n * k + k) which simplifies to O(m * n * k).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫