Number of Ways of Cutting a Pizza solution and explanation
Google
9 more videos on this problem
Number of Ways of Cutting a Pizza - (Google, TikTok) | Leetcode-1444 | Explanation ➕ Live CodingcodestorywithMIK · 1:06:23 · 11K views
Number of Ways of Cutting a Pizza || Dynamic Programming || Prefix Sums || C++/Java/PythonAryan Mittal · 28:07 · 5K views
LeetCode 1444. Number of Ways of Cutting a PizzaHappy Coding · 43:11 · 4K views
Number of Ways of Cutting a Pizza | LeetcodeRoshan Srivastava · 13:49 · 2K views
NUMBER OF WAYS OF CUTTING A PIZZA | LEETCODE 1444 | HARD | PYTHONAniPy · 17:32 · 2K views
Leetcode 1444 (Hard)Number of Ways of Cutting a Pizza: Simple C++ Solution [Multidimensional DP].Shivam Patel · 33:55 · 2K views
1444. Number of Ways of Cutting a Pizza | LeetCode Daily Challenge | LeetCode POTDDeep Tech · 14:12 · 2K views
Leetcode 1444: Number of Ways of Cutting a PizzaAlgorithms Casts · 28:09 · 1K views
LeetCode 1444 Number of Ways of Cutting a PizzaMaxMing · 11:08 · 1K views
1444. Number of Ways of Cutting a Pizza (Leetcode Hard)Programming Live with Larry · 29:43 · 908 views
The problem
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 <= 50rows == pizza.lengthcols == pizza[i].length1 <= k <= 10pizzaconsists of characters'A'and'.'only.
Approach overview
Problem Overview: You are given a rectangular pizza grid where each cell is either an apple ('A') or empty ('.'). The goal is to cut the pizza into k pieces using horizontal or vertical cuts so every piece contains at least one apple. Return the total number of valid ways to perform these cuts.
Approach 1: DP with Prefix Sum + Memoization (Time: O(k * m * n * (m + n)), Space: O(k * m * n))
The key difficulty is quickly checking whether a sub-rectangle contains at least one apple. A 2D prefix sum matrix solves this: it lets you query the apple count of any rectangle in constant time. With that in place, use top-down dynamic programming. Define dfs(r, c, cutsLeft) as the number of ways to cut the submatrix starting at (r, c) with cutsLeft cuts remaining.
From each state, try every possible horizontal cut below the current row and every vertical cut to the right. Before recursing, verify that the piece being separated contains at least one apple using the prefix sum lookup. Memoize the result for each state so repeated subproblems are solved once. This transforms an exponential search into a manageable dynamic programming solution. The approach combines dynamic programming, memoization, and fast region queries over a matrix.
Approach 2: Bottom-Up Dynamic Programming (Time: O(k * m * n * (m + n)), Space: O(k * m * n))
The same recurrence can be computed iteratively instead of recursion. Let dp[c][r][c] represent the number of ways to cut the submatrix starting at (r, c) into c + 1 pieces. Start with the base case where no more cuts are needed and check whether the remaining region contains an apple using the prefix sum matrix.
Then iterate through the number of cuts and accumulate ways by attempting horizontal and vertical cuts. For each candidate cut, confirm the top or left piece contains at least one apple before adding the ways from the remaining subproblem. Bottom-up DP avoids recursion overhead and can be easier to reason about during debugging, but it uses the same state transitions and complexity.
Recommended for interviews: The prefix sum + memoized DFS approach is the one most candidates implement first. It clearly expresses the recursive substructure and shows you understand pruning with fast region queries. Bottom-up DP demonstrates deeper mastery of dynamic programming state transitions, but both solutions rely on the same insight: precompute apple counts and reuse results for overlapping subproblems.
Approach 1: DP with Prefix Sum
This approach leverages a dynamic programming table to store the number of ways to cut sub-pizzas and uses prefix sums to efficiently check if a particular sub-pizza contains apples.
We define a 3D DP array where dp[i][j][k] represents the number of ways to cut the sub-pizza starting from cell (i,j) into k pieces. The base case is when k = 1, where dp[i][j][1] = 1 if the sub-pizza contains at least one apple.
For each position, we attempt both horizontal and vertical cuts and ensure each resulting sub-pizza has at least one 'A'. The prefix sum array helps quickly verify the presence of 'A's within a subregion.
MOD = 10**9 + 7
def ways(pizza, k):
rows, cols = len(pizza), len(pizza[0])
prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(rows - 1, -1, -1):
for c in range(cols - 1, -1, -1):
prefix[r][c] = int(pizza[r][c] == 'A') + prefix[r + 1][c] + prefix[r][c + 1] - prefix[r + 1][c + 1]
def has_apple(r1, c1, r2, c2):
return prefix[r1][c1] - prefix[r2][c1] - prefix[r1][c2] + prefix[r2][c2] > 0
dp = [[[0] * (k + 1) for _ in range(cols)] for _ in range(rows)]
for r in range(rows):
for c in range(cols):
dp[r][c][1] = 1 if has_apple(r, c, rows, cols) else 0
for pieces in range(2, k + 1):
for r in range(rows):
for c in range(cols):
for nr in range(r + 1, rows):
if has_apple(r, c, nr, cols):
dp[r][c][pieces] += dp[nr][c][pieces - 1]
dp[r][c][pieces] %= MOD
for nc in range(c + 1, cols):
if has_apple(r, c, rows, nc):
dp[r][c][pieces] += dp[r][nc][pieces - 1]
dp[r][c][pieces] %= MOD
return dp[0][0][k]class Solution {
private static final int MOD = 1000000007;
public int ways(String[] pizza, int k) {
int rows = pizza.length, cols = pizza[0].length();
int[][] prefix = new int[rows + 1][cols + 1];
for (int r = rows - 1; r >= 0; r--) {
for (int c = cols - 1; c >= 0; c--) {
prefix[r][c] = (pizza[r].charAt(c) == 'A' ? 1 : 0) + prefix[r + 1][c] + prefix[r][c + 1] - prefix[r + 1][c + 1];
}
}
Integer[][][] dp = new Integer[rows][cols][k + 1];
return getWays(0, 0, k - 1, rows, cols, dp, prefix);
}
private int getWays(int r, int c, int cuts, int rows, int cols, Integer[][][] dp, int[][] prefix) {
if (cuts == 0) return prefix[r][c] > 0 ? 1 : 0;
if (dp[r][c][cuts] != null) return dp[r][c][cuts];
int ways = 0;
for (int nr = r + 1; nr < rows; nr++) {
if (prefix[r][c] - prefix[nr][c] > 0) {
ways = (ways + getWays(nr, c, cuts - 1, rows, cols, dp, prefix)) % MOD;
}
}
for (int nc = c + 1; nc < cols; nc++) {
if (prefix[r][c] - prefix[r][nc] > 0) {
ways = (ways + getWays(r, nc, cuts - 1, rows, cols, dp, prefix)) % MOD;
}
}
return dp[r][c][cuts] = ways;
}
}The solution initializes a prefix sum array to check for apples in any subregion of the pizza quickly. The DP table is then filled based on possibilities of horizontal and vertical cuts, ensuring that resulting sub-pizzas have at least one apple.
Time Complexity: O(k * rows^2 * cols^2) due to the nested loops.
Space Complexity: O(k * rows * cols) for the DP table.
Approach 2: Bottom-Up Dynamic Programming
This approach is similar in concept to the first DP solution, but it employs a bottom-up strategy, iterating from smaller sub-problems to larger ones. It avoids recursive calls, focusing on building the solution iteratively.
const MOD = 1e9 + 7;
function ways(pizza, k) {
const rows = pizza.length,
cols = pizza[0].length;
const prefix = Array.from({length: rows + 1}, () => Array(cols + 1).fill(0));
for (let r = rows - 1; r >= 0; r--) {
for (let c = cols - 1; c >= 0; c--) {
prefix[r][c] = (pizza[r][c] === 'A' ? 1 : 0) + prefix[r + 1][c] + prefix[r][c + 1] - prefix[r + 1][c + 1];
}
}
const dp = Array.from({length: rows}, () => Array.from({length: cols}, () => Array(k + 1).fill(0)));
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
dp[r][c][1] = prefix[r][c] > 0 ? 1 : 0;
}
}
for (let pieces = 2; pieces <= k; pieces++) {
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
for (let nr = r + 1; nr < rows; nr++) {
if (prefix[r][c] - prefix[nr][c] > 0) {
dp[r][c][pieces] = (dp[r][c][pieces] + dp[nr][c][pieces - 1]) % MOD;
}
}
for (let nc = c + 1; nc < cols; nc++) {
if (prefix[r][c] - prefix[r][nc] > 0) {
dp[r][c][pieces] = (dp[r][c][pieces] + dp[r][nc][pieces - 1]) % MOD;
}
}
}
}
}
return dp[0][0][k];
}public class Solution {
private const int MOD = 1000000007;
public int Ways(string[] pizza, int k) {
int rows = pizza.Length;
int cols = pizza[0].Length;
int[,] prefix = new int[rows + 1, cols + 1];
for (int r = rows - 1; r >= 0; r--) {
for (int c = cols - 1; c >= 0; c--) {
prefix[r, c] = (pizza[r][c] == 'A' ? 1 : 0) + prefix[r + 1, c] + prefix[r, c + 1] - prefix[r + 1, c + 1];
}
}
int[,,] dp = new int[rows, cols, k + 1];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
dp[r, c, 1] = prefix[r, c] > 0 ? 1 : 0;
}
}
for (int pieces = 2; pieces <= k; pieces++) {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
for (int nr = r + 1; nr < rows; nr++) {
if (prefix[r, c] - prefix[nr, c] > 0) {
dp[r, c, pieces] = (dp[r, c, pieces] + dp[nr, c, pieces - 1]) % MOD;
}
}
for (int nc = c + 1; nc < cols; nc++) {
if (prefix[r, c] - prefix[r, nc] > 0) {
dp[r, c, pieces] = (dp[r, c, pieces] + dp[r, nc, pieces - 1]) % MOD;
}
}
}
}
}
return dp[0, 0, k];
}
}The JavaScript version follows the same logic using a bottom-up dynamic programming approach, iteratively filling the DP table referencing each subregion cut possibility.
Time Complexity: O(k * rows^2 * cols^2) due to the nested loop structure.
Space Complexity: O(k * rows * cols) to store computed DP values.
Approach 3: 2D Prefix Sum + Memoized Search
We can use a 2D prefix sum to quickly calculate the number of apples in each sub-rectangle. Define s[i][j] to represent the number of apples in the sub-rectangle that includes the first i rows and the first j columns. Then s[i][j] can be derived from the number of apples in the three sub-rectangles s[i-1][j], s[i][j-1], and s[i-1][j-1]. The specific calculation method is as follows:
$
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + (pizza[i-1][j-1] == 'A')
Here, pizza[i-1][j-1] represents the character at the i-th row and j-th column in the rectangle. If it is an apple, it is 1; otherwise, it is 0.
Next, we design a function dfs(i, j, k), which represents the number of ways to cut the rectangle (i, j, m-1, n-1) with k cuts to get k+1 pieces of pizza. Here, (i, j) and (m-1, n-1) are the coordinates of the top-left and bottom-right corners of the rectangle, respectively. The calculation method of the function dfs(i, j, k) is as follows:
- If k = 0
, it means no more cuts can be made. We need to check if there are any apples in the rectangle. If there are apples, return1; otherwise, return0. - If k \gt 0
, we need to enumerate the position of the last cut. If the last cut is horizontal, we need to enumerate the cutting positionx, wherei \lt x \lt m. Ifs[x][n] - s[i][n] - s[x][j] + s[i][j] \gt 0, it means there are apples in the upper piece of pizza, and we add the value ofdfs(x, j, k-1)to the answer. If the last cut is vertical, we need to enumerate the cutting positiony, wherej \lt y \lt n. Ifs[m][y] - s[i][y] - s[m][j] + s[i][j] \gt 0, it means there are apples in the left piece of pizza, and we add the value ofdfs(i, y, k-1)to the answer.
The final answer is the value of dfs(0, 0, k-1).
To avoid repeated calculations, we can use memoized search. We use a 3D array f to record the value of dfs(i, j, k). When we need to calculate the value of dfs(i, j, k), if f[i][j][k] is not -1, it means we have already calculated it before, and we can directly return f[i][j][k]. Otherwise, we calculate the value of dfs(i, j, k) according to the above method and save the result in f[i][j][k].
The time complexity is O(m times n times k times (m + n)), and the space complexity is O(m times n times k). Here, m and n$ are the number of rows and columns of the rectangle, respectively.
Similar problems:
class Solution {
public:
int ways(vector<string>& pizza, int k) {
const int mod = 1e9 + 7;
int m = pizza.size(), n = pizza[0].size();
vector<vector<vector<int>>> f(m, vector<vector<int>>(n, vector<int>(k, -1)));
vector<vector<int>> s(m + 1, vector<int>(n + 1));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
int x = pizza[i - 1][j - 1] == 'A' ? 1 : 0;
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;
}
}
function<int(int, int, int)> dfs = [&](int i, int j, int k) -> int {
if (k == 0) {
return s[m][n] - s[i][n] - s[m][j] + s[i][j] > 0 ? 1 : 0;
}
if (f[i][j][k] != -1) {
return f[i][j][k];
}
int ans = 0;
for (int x = i + 1; x < m; ++x) {
if (s[x][n] - s[i][n] - s[x][j] + s[i][j] > 0) {
ans = (ans + dfs(x, j, k - 1)) % mod;
}
}
for (int y = j + 1; y < n; ++y) {
if (s[m][y] - s[i][y] - s[m][j] + s[i][j] > 0) {
ans = (ans + dfs(i, y, k - 1)) % mod;
}
}
return f[i][j][k] = ans;
};
return dfs(0, 0, k - 1);
}
};function ways(pizza: string[], k: number): number {
const mod = 1e9 + 7;
const m = pizza.length;
const n = pizza[0].length;
const f = new Array(m).fill(0).map(() => new Array(n).fill(0).map(() => new Array(k).fill(-1)));
const s = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
const x = pizza[i - 1][j - 1] === 'A' ? 1 : 0;
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;
}
}
const dfs = (i: number, j: number, k: number): number => {
if (f[i][j][k] !== -1) {
return f[i][j][k];
}
if (k === 0) {
return s[m][n] - s[i][n] - s[m][j] + s[i][j] > 0 ? 1 : 0;
}
let ans = 0;
for (let x = i + 1; x < m; ++x) {
if (s[x][n] - s[i][n] - s[x][j] + s[i][j] > 0) {
ans = (ans + dfs(x, j, k - 1)) % mod;
}
}
for (let y = j + 1; y < n; ++y) {
if (s[m][y] - s[i][y] - s[m][j] + s[i][j] > 0) {
ans = (ans + dfs(i, y, k - 1)) % mod;
}
}
return (f[i][j][k] = ans);
};
return dfs(0, 0, k - 1);
}func ways(pizza []string, k int) int {
const mod = 1e9 + 7
m, n := len(pizza), len(pizza[0])
f := make([][][]int, m)
s := make([][]int, m+1)
for i := range f {
f[i] = make([][]int, n)
for j := range f[i] {
f[i][j] = make([]int, k)
for h := range f[i][j] {
f[i][j][h] = -1
}
}
}
for i := range s {
s[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1]
if pizza[i-1][j-1] == 'A' {
s[i][j]++
}
}
}
var dfs func(i, j, k int) int
dfs = func(i, j, k int) int {
if f[i][j][k] != -1 {
return f[i][j][k]
}
if k == 0 {
if s[m][n]-s[m][j]-s[i][n]+s[i][j] > 0 {
return 1
}
return 0
}
ans := 0
for x := i + 1; x < m; x++ {
if s[x][n]-s[x][j]-s[i][n]+s[i][j] > 0 {
ans = (ans + dfs(x, j, k-1)) % mod
}
}
for y := j + 1; y < n; y++ {
if s[m][y]-s[m][j]-s[i][y]+s[i][j] > 0 {
ans = (ans + dfs(i, y, k-1)) % mod
}
}
f[i][j][k] = ans
return ans
}
return dfs(0, 0, k-1)
}Complexity comparison
| Approach | Complexity |
|---|---|
| DP with Prefix Sum | Time Complexity: O(k * rows^2 * cols^2) due to the nested loops. |
| Bottom-Up Dynamic Programming | Time Complexity: O(k * rows^2 * cols^2) due to the nested loop structure. |
| 2D Prefix Sum + Memoized Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DP with Prefix Sum + Memoization | O(k * m * n * (m + n)) | O(k * m * n) | Most intuitive solution. Great for interviews and when recursion with caching is acceptable. |
| Bottom-Up Dynamic Programming | O(k * m * n * (m + n)) | O(k * m * n) | Preferred when avoiding recursion or when you want explicit control over DP state transitions. |
Frequently asked questions
Is Number of Ways of Cutting a Pizza easy or hard?
LeetCode classifies this problem as Hard. The difficulty comes from combining multiple techniques: prefix sums for region queries, recursive state transitions, and dynamic programming to avoid exponential recomputation.
Number of Ways of Cutting a Pizza Python or Java solution?
Both Python and Java implementations typically use DFS with memoization plus a prefix sum matrix. The DFS explores horizontal and vertical cut positions while caching states defined by row, column, and remaining cuts. This keeps the complexity within O(k * m * n * (m + n)).
How to solve Number of Ways of Cutting a Pizza efficiently?
Precompute a 2D prefix sum that stores the number of apples in every sub-rectangle. Use dynamic programming where the state represents the top-left corner of the remaining pizza and how many cuts are left. For each state, iterate through possible horizontal and vertical cuts and recurse only if the separated piece contains at least one apple.
What is the best approach for Number of Ways of Cutting a Pizza?
The most effective solution uses a 2D prefix sum combined with dynamic programming and memoization. Prefix sums allow constant-time checks for whether a sub-rectangle contains an apple, while DP caches results for repeated subproblems. The typical implementation runs in O(k * m * n * (m + n)) time with O(k * m * n) space.
What data structure is used in Number of Ways of Cutting a Pizza?
The solution primarily uses a 2D prefix sum matrix for fast apple counting and a dynamic programming cache (either a memoization map or multidimensional DP array). The pizza itself is treated as a matrix or array of strings.
What is the time complexity of Number of Ways of Cutting a Pizza?
The optimal solutions run in O(k * m * n * (m + n)) time, where m and n are the pizza dimensions and k is the number of pieces required. Each DP state represents a starting cell and remaining cuts, and every state tries possible horizontal and vertical cut positions. Space complexity is O(k * m * n) for memoization or DP tables.
Is Number of Ways of Cutting a Pizza asked at Google, Amazon, or Meta?
Grid dynamic programming and prefix sum problems like this commonly appear in interviews at companies such as Google, Amazon, and Meta. Variations of matrix partitioning, region sum queries, and memoized recursion are frequently tested in senior-level coding rounds.