Skip to main content
Talentd

Number of Ways of Cutting a Pizza - Solution & Explanation

HardArrayDynamic ProgrammingMemoizationMatrix24 min readAsked at: Google
Practice this problem

Problem Statement

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.

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.

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.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(k * rows^2 * cols^2) due to the nested loops.
Space Complexity: O(k * rows * cols) for the DP table.

Try this approach in the editor →

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.

The C# implementation uses a bottom-up dynamic programming approach, building the solution iteratively and processing each possible subregion by checking with prefix sums.

Code

C#JavaScript

C#

JavaScript

Complexity

Time Complexity: O(k * rows^2 * cols^2) due to the nested iteration.
Space Complexity: O(k * rows * cols) for storing DP results.

Try this approach in the editor →

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, return 1; otherwise, return 0.
  • 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 position x, where i \lt x \lt m. If s[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 of dfs(x, j, k-1) to the answer. If the last cut is vertical, we need to enumerate the cutting position y, where j \lt y \lt n. If s[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 of dfs(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:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
DP with Prefix Sum

Time Complexity: O(k * rows^2 * cols^2) due to the nested loops.
Space Complexity: O(k * rows * cols) for the DP table.

Bottom-Up Dynamic Programming

Time Complexity: O(k * rows^2 * cols^2) due to the nested iteration.
Space Complexity: O(k * rows * cols) for storing DP results.

2D Prefix Sum + Memoized Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DP with Prefix Sum + MemoizationO(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 ProgrammingO(k * m * n * (m + n))O(k * m * n)Preferred when avoiding recursion or when you want explicit control over DP state transitions.

Video Solution

Number of Ways of Cutting a Pizza - (Google, TikTok) | Leetcode-1444 | Explanation ➕ Live Coding • codestorywithMIK • 11,179 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Number of Ways of Cutting a Pizza with our built-in code editor and test cases.

Practice on FleetCode
Previous

Selling Pieces of Wood