LeetCode 1444 - Number of Ways of Cutting a Pizza
Edit This problem asks us to count the number of valid ways to divide a rectangular pizza into exactly k pieces such tha
Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Memoization, Matrix, Prefix Sum
Solution
Edit
LeetCode 1444 - Number of Ways of Cutting a Pizza
Problem Understanding
This problem asks us to count the number of valid ways to divide a rectangular pizza into exactly k pieces such that every piece contains at least one apple.
The pizza is represented as a grid of characters where 'A' indicates an apple and '.' indicates an empty cell. We must perform exactly k - 1 cuts to produce k pieces. Each cut can either be horizontal or vertical.
A horizontal cut splits the pizza into an upper piece and a lower piece. The upper piece is immediately given away to a person, while the lower piece remains for future cuts. A vertical cut splits the pizza into a left piece and a right piece. The left piece is given away, while the right piece continues to be cut.
The important detail is that every resulting piece must contain at least one apple. A cut is only valid if the piece being handed out contains an apple, and after all cuts are complete, the final remaining piece also contains at least one apple.
The output is the total number of distinct valid cutting sequences, modulo 10^9 + 7.
The constraints are important for understanding what type of solution is feasible:
rows, cols <= 50k <= 10
A brute-force recursive search over every possible sequence of cuts would explode combinatorially. However, the relatively small value of k suggests dynamic programming may work. Since we repeatedly need to answer whether a subrectangle contains any apples, efficient submatrix queries are also necessary.
An important observation is that after each cut, only one side continues to be processed. Therefore, a state can be described by the remaining top-left coordinate of the current pizza and the number of cuts left.
Several edge cases deserve attention. A pizza with no apples cannot be divided into valid pieces. A pizza with fewer apples than k can never produce k valid pieces. When k = 1, we do not cut at all, and the answer is simply whether the whole pizza contains at least one apple. Another subtle case is when many possible cuts exist geometrically, but some produce empty sections without apples, which must be excluded.
Approaches
Brute Force Approach
A brute-force solution would recursively try every possible horizontal and vertical cut at every stage.
At any point, we examine the current pizza rectangle and attempt every legal horizontal cut and every legal vertical cut. After making a cut, we recursively process the remaining section with one fewer cut left.
To ensure correctness, we would need to check whether both resulting pieces contain at least one apple before continuing.
This approach is correct because it explicitly enumerates every possible cutting sequence and counts only those that satisfy the apple constraint.
The problem is that many identical subproblems appear repeatedly. For example, the same remaining subrectangle may be reached through different cutting orders. Without memoization, we recompute the same results exponentially many times.
Additionally, checking whether a rectangle contains apples by scanning the region each time adds another layer of inefficiency.
Optimal Approach, Dynamic Programming with Memoization and Prefix Sum
The key insight is that once a cut is made, only the remaining portion matters. We do not care how we arrived at that subrectangle, only its starting position and how many cuts remain.
This naturally suggests memoization.
We define a dynamic programming state:
dp(row, col, cuts_left)
This represents the number of valid ways to cut the subrectangle beginning at (row, col) into cuts_left + 1 pieces.
To make transitions efficient, we also precompute a suffix-style prefix sum matrix that tells us how many apples exist inside any subrectangle in constant time.
This allows us to quickly answer:
- Does the current rectangle contain any apples?
- Is a proposed cut valid?
For each state, we try all possible horizontal and vertical cuts. A cut is valid if the piece being given away contains at least one apple. Then we recursively compute the number of ways for the remaining portion.
Memoization prevents recomputation, making the algorithm efficient enough for the constraints.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | Exponential | O(k) recursion | Tries every cut sequence repeatedly |
| Optimal | O(k × rows × cols × (rows + cols)) | O(k × rows × cols) | Uses memoization and prefix sum |
Algorithm Walkthrough
- Precompute apple counts using a suffix sum matrix
We build a matrix apple_count where apple_count[r][c] stores the total number of apples in the subrectangle starting at (r, c) and extending to the bottom-right corner.
This allows us to determine whether any subrectangle contains apples in constant time.
The recurrence is:
apple_count[r][c] =
apple_count[r+1][c]
+ apple_count[r][c+1]
- apple_count[r+1][c+1]
+ (1 if pizza[r][c] == 'A' else 0)
- Define the memoized DP state
We define:
dfs(row, col, cuts_remaining)
This means:
Number of valid ways to cut the subrectangle starting at
(row, col)intocuts_remaining + 1valid pieces.
- Handle the base case
If cuts_remaining == 0, we are creating the final piece.
The current subrectangle is valid if it contains at least one apple.
If:
apple_count[row][col] > 0
then return 1, otherwise return 0.
4. Try all horizontal cuts
For every row below the current starting row, attempt a horizontal cut.
The upper section being given away is valid only if:
apple_count[row][col] - apple_count[next_row][col] > 0
This means the top portion contains at least one apple.
If valid, recursively solve:
dfs(next_row, col, cuts_remaining - 1)
- Try all vertical cuts
Similarly, for every column to the right:
apple_count[row][col] - apple_count[row][next_col] > 0
If true, the left portion contains an apple.
Then recursively compute:
dfs(row, next_col, cuts_remaining - 1)
- Memoize results
Since many states repeat, cache the result of every:
(row, col, cuts_remaining)
This avoids redundant recursion. 7. Apply modulo arithmetic
Since the number of valid ways may become extremely large, always compute:
result % (10^9 + 7)
Why it works
The correctness comes from considering every possible valid cut at each step and recursively counting valid completions. Every valid sequence of cuts is counted exactly once because each recursive branch corresponds to a unique cutting order. Invalid cuts are excluded immediately by checking apple presence. Memoization preserves correctness because identical subproblems always produce the same answer.
Python Solution
from functools import lru_cache
from typing import List
class Solution:
def ways(self, pizza: List[str], k: int) -> int:
MOD = 10**9 + 7
rows = len(pizza)
cols = len(pizza[0])
# Suffix sum of apples
apple_count = [[0] * (cols + 1) for _ in range(rows + 1)]
for row in range(rows - 1, -1, -1):
for col in range(cols - 1, -1, -1):
apple_count[row][col] = (
apple_count[row + 1][col]
+ apple_count[row][col + 1]
- apple_count[row + 1][col + 1]
+ (1 if pizza[row][col] == 'A' else 0)
)
@lru_cache(None)
def dfs(row: int, col: int, cuts_remaining: int) -> int:
# No apples in current rectangle
if apple_count[row][col] == 0:
return 0
# Final piece
if cuts_remaining == 0:
return 1
ways_count = 0
# Horizontal cuts
for next_row in range(row + 1, rows):
top_apples = (
apple_count[row][col]
- apple_count[next_row][col]
)
if top_apples > 0:
ways_count += dfs(
next_row,
col,
cuts_remaining - 1
)
# Vertical cuts
for next_col in range(col + 1, cols):
left_apples = (
apple_count[row][col]
- apple_count[row][next_col]
)
if left_apples > 0:
ways_count += dfs(
row,
next_col,
cuts_remaining - 1
)
return ways_count % MOD
return dfs(0, 0, k - 1)
The implementation begins by constructing the suffix sum matrix. Instead of recalculating apple counts for every rectangle repeatedly, this matrix allows constant-time apple queries.
The recursive dfs() function represents the memoized dynamic programming state. Before attempting cuts, it first checks whether the current rectangle has any apples. If not, the state is impossible and immediately returns 0.
The base case occurs when no cuts remain. Since the current region represents the final pizza piece, we simply verify that it contains an apple.
The recursive step tries every possible horizontal and vertical cut. Before recursing, it verifies that the portion being handed out contains at least one apple. This ensures only legal cutting paths are explored.
Memoization through @lru_cache guarantees that repeated states are computed only once.
Go Solution
func ways(pizza []string, k int) int {
const MOD = 1000000007
rows := len(pizza)
cols := len(pizza[0])
// Suffix sum of apples
appleCount := make([][]int, rows+1)
for i := range appleCount {
appleCount[i] = make([]int, cols+1)
}
for row := rows - 1; row >= 0; row-- {
for col := cols - 1; col >= 0; col-- {
apple := 0
if pizza[row][col] == 'A' {
apple = 1
}
appleCount[row][col] =
appleCount[row+1][col] +
appleCount[row][col+1] -
appleCount[row+1][col+1] +
apple
}
}
memo := make(map[[3]int]int)
var dfs func(int, int, int) int
dfs = func(row, col, cutsRemaining int) int {
key := [3]int{row, col, cutsRemaining}
if value, exists := memo[key]; exists {
return value
}
// No apples
if appleCount[row][col] == 0 {
return 0
}
// Final piece
if cutsRemaining == 0 {
return 1
}
totalWays := 0
// Horizontal cuts
for nextRow := row + 1; nextRow < rows; nextRow++ {
topApples :=
appleCount[row][col] -
appleCount[nextRow][col]
if topApples > 0 {
totalWays += dfs(
nextRow,
col,
cutsRemaining-1,
)
totalWays %= MOD
}
}
// Vertical cuts
for nextCol := col + 1; nextCol < cols; nextCol++ {
leftApples :=
appleCount[row][col] -
appleCount[row][nextCol]
if leftApples > 0 {
totalWays += dfs(
row,
nextCol,
cutsRemaining-1,
)
totalWays %= MOD
}
}
memo[key] = totalWays
return totalWays
}
return dfs(0, 0, k-1)
}
The Go implementation follows the same logic as Python but uses a map[[3]int]int for memoization because Go does not provide built-in function caching.
Modulo arithmetic is applied during accumulation to avoid integer overflow. Since Go slices are reference-based, no additional copying occurs during recursion.
Worked Examples
Example 1
pizza = ["A..","AAA","..."]
k = 3
Pizza layout:
A . .
A A A
. . .
Initial apple count:
| Position | Apples Remaining |
|---|---|
| (0,0) | 4 |
| (1,0) | 3 |
| (0,1) | 2 |
Start:
dfs(0, 0, 2)
Possible horizontal cuts:
| Cut Row | Top Has Apple | Valid |
|---|---|---|
| 1 | Yes | Yes |
| 2 | Yes | Yes |
Possible vertical cuts:
| Cut Col | Left Has Apple | Valid |
|---|---|---|
| 1 | Yes | Yes |
| 2 | No | No |
Valid recursive paths:
| Path | Result |
|---|---|
| Horizontal at row 1 | 1 |
| Horizontal at row 2 | 1 |
| Vertical at col 1 | 1 |
Final answer:
3
Example 2
pizza = ["A..","AA.","..."]
k = 3
Only one sequence of cuts produces three valid apple-containing pieces.
Result:
1
Example 3
pizza = ["A..","A..","..."]
k = 1
No cuts are needed.
Whole pizza contains apples:
apple_count[0][0] > 0
Answer:
1
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(k × rows × cols × (rows + cols)) | Each DP state tries all row and column cuts |
| Space | O(k × rows × cols) | Memoization cache plus recursion |
There are at most:
rows × cols × k
unique states.
For each state, we may iterate across every remaining row and column, which costs:
O(rows + cols)
Since rows, cols <= 50 and k <= 10, this is easily efficient enough.
Test Cases
solution = Solution()
assert solution.ways(
["A..", "AAA", "..."], 3
) == 3 # Example 1
assert solution.ways(
["A..", "AA.", "..."], 3
) == 1 # Example 2
assert solution.ways(
["A..", "A..", "..."], 1
) == 1 # Example 3
assert solution.ways(
["A"], 1
) == 1 # Single apple, no cuts
assert solution.ways(
["."], 1
) == 0 # No apples
assert solution.ways(
["AAA"], 3
) == 1 # One-dimensional horizontal impossible
assert solution.ways(
["A", "A", "A"], 3
) == 1 # Vertical impossible
assert solution.ways(
["AA", "AA"], 4
) == 2 # Multiple valid partitions
assert solution.ways(
["A..", "...", "..."], 2
) == 0 # Impossible to create 2 valid pieces
assert solution.ways(
["AAAA", "AAAA"], 5
) > 0 # Stress case with many apples
| Test | Why |
|---|---|
| Example 1 | Validates multiple cutting paths |
| Example 2 | Validates single valid path |
| Example 3 | Validates k = 1 base case |
["A"] |
Smallest valid input |
["."] |
No apples edge case |
["AAA"] |
Single-row handling |
["A","A","A"] |
Single-column handling |
["AA","AA"] |
Multiple partition combinations |
| Sparse pizza | Impossible partition case |
| Dense pizza | Stress test with many apples |
Edge Cases
Case 1: Pizza contains no apples
A pizza such as:
["...", "..."]
can never produce a valid answer because every piece must contain at least one apple.
A naive implementation might still attempt recursion and waste time exploring impossible cuts. This implementation avoids that by immediately returning 0 whenever:
apple_count[row][col] == 0
Case 2: k = 1
When k = 1, no cuts are required. The answer depends entirely on whether the whole pizza contains an apple.
This case can be easy to mishandle if recursion assumes at least one cut always happens. Here, the base case:
cuts_remaining == 0
correctly handles the situation.
Case 3: Invalid geometric cuts
Some cuts may appear geometrically valid but produce an empty apple-less piece.
For example:
A..
...
...
A horizontal cut below the first row creates an empty lower section with no apples.
The implementation carefully validates every cut using suffix sums before recursing, ensuring only legal partitions are counted.
Case 4: Repeated subproblems
Different cutting paths may lead to the same remaining subrectangle.
Without memoization, this creates exponential recomputation. By caching:
(row, col, cuts_remaining)
each unique state is solved only once, making the algorithm efficient enough for the given limits.