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:
-
We can perform each cut based on the boundary of cells, either cutting horizontally or vertically.
-
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.
-
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.
-
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
.
Learn more about Memoization and Dynamic Programming patterns.
Solution Approach
To implement the solution, we use several strategies from dynamic programming and recursion to handle the complexity of the problem.
-
Dynamic Programming (Memoization): We use the
@cache
decorator on thedfs
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. -
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 expressions[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. -
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) withk
cuts remaining. The base case occurs whenk
is0
, meaning no more cuts are needed. If at least one apple is present in that piece, the function should return1
, signifying one valid way to cut. -
Recursion for Cutting: When
k
is greater than0
, 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 todfs
. The number of ways from these recursive calls is then added to the answer (ans
). -
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. -
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
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.
-
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 and3
is the number of pieces we need. - Since we need to make
2
cuts to get3
pieces, thedfs
function will explore all possible horizontal and vertical cuts.
- We start with
-
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' with2
pieces needed).
-
Base Case and Recursive Calls:
Continuing with the previous point:
- Our new
dfs
call isdfs(2, 0, 2)
. Now our base case isk=1
. Since there is1
apple in the new submatrix(2, 0)
to(3, 3)
, we return1
. - Backtracking, we attempt other cuts like a vertical cut after the first column, and so on for all possibilities.
- Our new
-
Modulo Operation: Each time we come up with a count, we take it modulo
10^9 + 7
to handle large numbers. -
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.
Solution Implementation
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
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
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
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:
- There are
m * n
states due to the matrix size. - For each state, we can potentially make
m + n
recursive calls since we are considering cuts along rows and columns. - Each recursive call decreases the value of
k
, and we havek
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:
- The caching of results which potentially stores
m * n * k
states. - 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)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.