1444. Number of Ways of Cutting a Pizza LeetCode Solution
In this guide, you will get 1444. Number of Ways of Cutting a Pizza LeetCode Solution with the best time and space complexity. The solution to Number of Ways of Cutting a Pizza problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Ways of Cutting a Pizza
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.
1 <= rows, cols <= 50
rows == pizza.length
cols == pizza[i].length
1 <= k <= 10
pizza consists of characters 'A' and '.' only.
Complexity Analysis
Time Complexity: O(MNk \cdot (M + N))
Space Complexity: O(MNk)
1444. Number of Ways of Cutting a Pizza LeetCode Solution in C++
class Solution {
public:
int ways(vector<string>& pizza, int k) {
const int M = pizza.size();
const int N = pizza[0].size();
vector<vector<vector<int>>> mem(M,
vector<vector<int>>(N, vector<int>(k, -1)));
vector<vector<int>> prefix(M + 1, vector<int>(N + 1));
for (int i = 0; i < M; ++i)
for (int j = 0; j < N; ++j)
prefix[i + 1][j + 1] = (pizza[i][j] == 'A') + prefix[i][j + 1] +
prefix[i + 1][j] - prefix[i][j];
return ways(0, 0, k - 1, M, N, prefix, mem);
}
private:
static constexpr int kMod = 1'000'000'007;
// Returns the number of ways to cut pizza[m..M)[n..N) with k cuts.
int ways(int m, int n, int k, const int M, const int N,
const vector<vector<int>>& prefix,
vector<vector<vector<int>>>& mem) {
if (k == 0)
return hasApple(prefix, m, M, n, N) ? 1 : 0;
if (mem[m][n][k] != -1)
return mem[m][n][k];
mem[m][n][k] = 0;
for (int i = m + 1; i < M; ++i) // Cut horizontally.
if (hasApple(prefix, m, i, n, N) && hasApple(prefix, i, M, n, N)) {
mem[m][n][k] += ways(i, n, k - 1, M, N, prefix, mem);
mem[m][n][k] %= kMod;
}
for (int j = n + 1; j < N; ++j) // Cut vertically.
if (hasApple(prefix, m, M, n, j) && hasApple(prefix, m, M, j, N)) {
mem[m][n][k] += ways(m, j, k - 1, M, N, prefix, mem);
mem[m][n][k] %= kMod;
}
return mem[m][n][k];
}
// Returns true if pizza[row1..row2)[col1..col2) has apple.
bool hasApple(const vector<vector<int>>& prefix, int row1, int row2, int col1,
int col2) {
return (prefix[row2][col2] - prefix[row1][col2] - //
prefix[row2][col1] + prefix[row1][col1]) > 0;
};
}; /* code provided by PROGIEZ */
1444. Number of Ways of Cutting a Pizza LeetCode Solution in Java
class Solution {
public int ways(String[] pizza, int k) {
final int M = pizza.length;
final int N = pizza[0].length();
int[][][] mem = new int[M][N][k];
int[][] prefix = new int[M + 1][N + 1];
Arrays.stream(mem).forEach(A -> Arrays.stream(A).forEach(B -> Arrays.fill(B, -1)));
for (int i = 0; i < M; ++i)
for (int j = 0; j < N; ++j)
prefix[i + 1][j + 1] = (pizza[i].charAt(j) == 'A' ? 1 : 0) + prefix[i][j + 1] +
prefix[i + 1][j] - prefix[i][j];
return ways(0, 0, k - 1, M, N, prefix, mem);
}
private static final int kMod = 1_000_000_007;
// Returns the number of ways to cut pizza[m..M)[n..N) with k cuts.
private int ways(int m, int n, int k, int M, int N, int[][] prefix, int[][][] mem) {
if (k == 0)
return hasApple(prefix, m, M, n, N) ? 1 : 0;
if (mem[m][n][k] != -1)
return mem[m][n][k];
mem[m][n][k] = 0;
for (int i = m + 1; i < M; ++i) // Cut horizontally.
if (hasApple(prefix, m, i, n, N) && hasApple(prefix, i, M, n, N)) {
mem[m][n][k] += ways(i, n, k - 1, M, N, prefix, mem);
mem[m][n][k] %= kMod;
}
for (int j = n + 1; j < N; ++j) // Cut vertically.
if (hasApple(prefix, m, M, n, j) && hasApple(prefix, m, M, j, N)) {
mem[m][n][k] += ways(m, j, k - 1, M, N, prefix, mem);
mem[m][n][k] %= kMod;
}
return mem[m][n][k];
}
// Returns true if pizza[row1..row2)[col1..col2) has apple.
private boolean hasApple(int[][] prefix, int row1, int row2, int col1, int col2) {
return (prefix[row2][col2] - prefix[row1][col2] - //
prefix[row2][col1] + prefix[row1][col1]) > 0;
}
} // code provided by PROGIEZ
1444. Number of Ways of Cutting a Pizza LeetCode Solution in Python
class Solution:
def ways(self, pizza: list[str], k: int) -> int:
kMod = 1_000_000_007
M = len(pizza)
N = len(pizza[0])
prefix = [[0] * (N + 1) for _ in range(M + 1)]
for i in range(M):
for j in range(N):
prefix[i + 1][j + 1] = ((pizza[i][j] == 'A') + prefix[i][j + 1] +
prefix[i + 1][j] - prefix[i][j])
def hasApple(row1: int, row2: int, col1: int, col2: int) -> bool:
"""Returns True if pizza[row1..row2)[col1..col2) has apple."""
return (prefix[row2][col2] - prefix[row1][col2] -
prefix[row2][col1] + prefix[row1][col1]) > 0
@functools.lru_cache(None)
def dp(m: int, n: int, k: int) -> int:
"""Returns the number of ways to cut pizza[m..M)[n..N) with k cuts."""
if k == 0:
return 1 if hasApple(m, M, n, N) else 0
res = 0
for i in range(m + 1, M): # Cut horizontally.
if hasApple(m, i, n, N) and hasApple(i, M, n, N):
res += dp(i, n, k - 1)
for j in range(n + 1, N): # Cut vertically.
if hasApple(m, M, n, j) and hasApple(m, M, j, N):
res += dp(m, j, k - 1)
return res % kMod
return dp(0, 0, k - 1) # code by PROGIEZ
