How hard is LeetCode 1444. Number of Ways of Cutting a Pizza?

LeetCode 1444. Number of Ways of Cutting a Pizza is rated Hard on LeetCode.

What is the time complexity of LeetCode 1444. Number of Ways of Cutting a Pizza?

The Python solution on this page runs in O(m \times n \times k \times (m + n)).

What is the space complexity of LeetCode 1444. Number of Ways of Cutting a Pizza?

The Python solution on this page uses O(m \times n \times k) auxiliary space.

What topics does LeetCode 1444. Number of Ways of Cutting a Pizza cover?

LeetCode 1444. Number of Ways of Cutting a Pizza is tagged Memoization, Array, Dynamic Programming, Matrix and Prefix Sum on LeetCode.

Number of Ways of Cutting a Pizza — LeetCode 1444 Python Solution

HardMemoizationArrayDynamic ProgrammingMatrixPrefix Sum

Problem: #1444
Pattern: Prefix Sum
Reading time: 4 min
Source: leetcode.com

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.

Example

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.

Python solution

Python

class Solution:
    def ways(self, pizza: List[str], k: int) -> int:
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            if k == 0:
                return int(s[m][n] - s[i][n] - s[m][j] + s[i][j] > 0)
            ans = 0
            for x in range(i + 1, m):
                if s[x][n] - s[i][n] - s[x][j] + s[i][j] > 0:
                    ans += dfs(x, j, k - 1)
            for y in range(j + 1, n):
                if s[m][y] - s[i][y] - s[m][j] + s[i][j] > 0:
                    ans += dfs(i, y, k - 1)
            return ans % mod

        mod = 10**9 + 7
        m, n = len(pizza), len(pizza[0])
        s = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(pizza, 1):
            for j, c in enumerate(row, 1):
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + int(c == 'A')
        return dfs(0, 0, k - 1)

Complexity

Measure	Complexity
Time	O(m \times n \times k \times (m + n))
Space	O(m \times n \times k) auxiliary

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 1444. Number of Ways of Cutting a Pizza is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1444. Number of Ways of Cutting a Pizza?: LeetCode 1444. Number of Ways of Cutting a Pizza is rated Hard on LeetCode.
What is the time complexity of LeetCode 1444. Number of Ways of Cutting a Pizza?: The Python solution on this page runs in O(m \times n \times k \times (m + n)).
What is the space complexity of LeetCode 1444. Number of Ways of Cutting a Pizza?: The Python solution on this page uses O(m \times n \times k) auxiliary space.
What topics does LeetCode 1444. Number of Ways of Cutting a Pizza cover?: LeetCode 1444. Number of Ways of Cutting a Pizza is tagged Memoization, Array, Dynamic Programming, Matrix and Prefix Sum on LeetCode.