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 <= 10pizza consists of characters 'A' and '.' only.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.
Java
Time Complexity: O(k * rows^2 * cols^2) due to the nested loops.
Space Complexity: O(k * rows * cols) for the DP table.
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.
JavaScript
Time Complexity: O(k * rows^2 * cols^2) due to the nested iteration.
Space Complexity: O(k * rows * cols) for storing DP results.
| 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 iteration. |
Number of Ways of Cutting a Pizza - (Google, TikTok) | Leetcode-1444 | Explanation ➕ Live Coding • codestorywithMIK • 6,352 views views
Watch 9 more video solutions →Practice Number of Ways of Cutting a Pizza with our built-in code editor and test cases.
Practice on FleetCode