1444. Number of Ways of Cutting a Pizza - Leetcode Solution

Problem Description

You are given a rectangular pizza represented by a list of strings pizza, where each character is either 'A' (representing an apple) or '.' (empty cell). You are also given an integer k, the number of pieces you must cut the pizza into. Each cut must be either horizontal or vertical, and after each cut, you choose one of the resulting pieces to cut again, until you have exactly k pieces.

The goal is to find the number of ways to cut the pizza such that each piece contains at least one apple. Two ways are considered different if they involve a different sequence of cuts. The answer can be large, so return it modulo 10^9 + 7.

Constraints:

1 <= pizza.length, pizza[0].length <= 50
1 <= k <= 10
Each character in pizza is either 'A' or '.'
There is at least one apple in pizza

Thought Process

At first glance, the problem seems to require generating all possible ways to cut the pizza and counting those where every piece contains at least one apple. A brute-force approach would try all possible cut combinations, but with up to 50 rows and columns and up to 9 cuts, this quickly becomes infeasible.

To optimize, we notice:

We can use recursion (or dynamic programming) to represent the process of making cuts.
At each step, we only need to know the current subrectangle and how many cuts remain.
We should avoid recalculating the same states, so memoization is crucial.
We need a fast way to check if a subrectangle contains at least one apple, which suggests precomputing prefix sums.

The key insight is to use DP with memoization and prefix sums to efficiently count valid ways of cutting.

Solution Approach

We solve this problem using dynamic programming with memoization, combined with a prefix sum array to quickly check if a subrectangle contains apples.

Prefix Sum Preprocessing:
- We create a 2D prefix sum array preSum where preSum[i][j] is the number of apples in the subrectangle from (i, j) to the bottom-right corner.
- This allows us to check in O(1) time if a subrectangle has any apples.
Dynamic Programming State:
- Define dp(i, j, k) as the number of ways to cut the subrectangle starting at (i, j) into k pieces, each with at least one apple.
- Base case: If k == 1, return 1 if the current subrectangle has at least one apple, else 0.
Recursive Transitions:
- Try all possible horizontal cuts below row i. If the top part has at least one apple, recursively solve for the bottom part with k-1 cuts.
- Try all possible vertical cuts to the right of column j. If the left part has at least one apple, recursively solve for the right part with k-1 cuts.
- Sum all valid ways and memoize the result for (i, j, k).
Implementation Details:
- Use memoization (cache) to avoid recalculating the same state.
- All results are taken modulo 10^9 + 7.

Example Walkthrough

Example Input:
pizza = ["A..","AAA","..."], k = 3

Step-by-step:

We need to cut the pizza into 3 pieces, each with at least one apple.
We start with the full pizza and try all possible first cuts (horizontal and vertical).
For each cut, we recursively try to cut the remaining part into k-1 pieces.
Using prefix sums, we quickly check if each piece after a cut has at least one apple.
We repeat this process until we've made k-1 cuts, and count a valid way if all pieces have at least one apple.

For this input, there are 3 valid ways to cut the pizza into 3 pieces, each containing at least one apple.

Time and Space Complexity

Brute-force: The naive solution tries all possible cut sequences, leading to exponential time complexity, which is infeasible for large grids.

Optimized DP Approach:

There are at most rows * cols * k unique DP states.
For each state, we try up to rows + cols possible cuts.
Thus, the time complexity is O(k * rows^2 * cols^2) in the worst case.
Space complexity is O(rows * cols * k) for the memoization table and O(rows * cols) for the prefix sum array.

Summary

This problem is elegantly solved by combining dynamic programming with memoization and prefix sum preprocessing. The prefix sum allows fast apple checks in any subrectangle, while DP ensures we only compute each state once. By structuring the problem as a recursive process of making cuts and counting valid ways, we avoid brute-force enumeration and achieve an efficient solution even for large pizzas and multiple cuts.

Code Implementation

from functools import lru_cache

class Solution:
    def ways(self, pizza, k):
        MOD = 10 ** 9 + 7
        rows, cols = len(pizza), len(pizza[0])
        
        # Precompute prefix sums
        preSum = [[0] * (cols + 1) for _ in range(rows + 1)]
        for i in range(rows - 1, -1, -1):
            for j in range(cols - 1, -1, -1):
                preSum[i][j] = (1 if pizza[i][j] == 'A' else 0) + preSum[i+1][j] + preSum[i][j+1] - preSum[i+1][j+1]

        @lru_cache(maxsize=None)
        def dp(i, j, cuts):
            if preSum[i][j] == 0:
                return 0
            if cuts == 1:
                return 1
            res = 0
            # Horizontal cuts
            for x in range(i+1, rows):
                if preSum[i][j] - preSum[x][j] > 0:
                    res = (res + dp(x, j, cuts-1)) % MOD
            # Vertical cuts
            for y in range(j+1, cols):
                if preSum[i][j] - preSum[i][y] > 0:
                    res = (res + dp(i, y, cuts-1)) % MOD
            return res

        return dp(0, 0, k)

class Solution {
public:
    int ways(vector<string>& pizza, int k) {
        const int MOD = 1e9 + 7;
        int rows = pizza.size(), cols = pizza[0].size();
        vector<vector<int>> preSum(rows+1, vector<int>(cols+1, 0));
        // Precompute prefix sums
        for (int i = rows - 1; i >= 0; --i) {
            for (int j = cols - 1; j >= 0; --j) {
                preSum[i][j] = (pizza[i][j] == 'A') + preSum[i+1][j] + preSum[i][j+1] - preSum[i+1][j+1];
            }
        }
        vector<vector<vector<int>>> memo(rows, vector<vector<int>>(cols, vector<int>(k+1, -1)));
        function<int(int,int,int)> dp = [&](int i, int j, int cuts) {
            if (preSum[i][j] == 0) return 0;
            if (cuts == 1) return 1;
            if (memo[i][j][cuts] != -1) return memo[i][j][cuts];
            int res = 0;
            // Horizontal cuts
            for (int x = i+1; x < rows; ++x) {
                if (preSum[i][j] - preSum[x][j] > 0)
                    res = (res + dp(x, j, cuts-1)) % MOD;
            }
            // Vertical cuts
            for (int y = j+1; y < cols; ++y) {
                if (preSum[i][j] - preSum[i][y] > 0)
                    res = (res + dp(i, y, cuts-1)) % MOD;
            }
            return memo[i][j][cuts] = res;
        };
        return dp(0, 0, k);
    }
};

class Solution {
    public int ways(String[] pizza, int k) {
        int MOD = 1_000_000_007;
        int rows = pizza.length, cols = pizza[0].length();
        int[][] preSum = new int[rows+1][cols+1];
        // Precompute prefix sums
        for (int i = rows - 1; i >= 0; --i) {
            for (int j = cols - 1; j >= 0; --j) {
                preSum[i][j] = (pizza[i].charAt(j) == 'A' ? 1 : 0)
                    + preSum[i+1][j] + preSum[i][j+1] - preSum[i+1][j+1];
            }
        }
        Integer[][][] memo = new Integer[rows][cols][k+1];

        return dp(0, 0, k, preSum, memo, rows, cols, MOD);
    }

    private int dp(int i, int j, int cuts, int[][] preSum, Integer[][][] memo, int rows, int cols, int MOD) {
        if (preSum[i][j] == 0) return 0;
        if (cuts == 1) return 1;
        if (memo[i][j][cuts] != null) return memo[i][j][cuts];
        int res = 0;
        // Horizontal cuts
        for (int x = i+1; x < rows; ++x) {
            if (preSum[i][j] - preSum[x][j] > 0)
                res = (res + dp(x, j, cuts-1, preSum, memo, rows, cols, MOD)) % MOD;
        }
        // Vertical cuts
        for (int y = j+1; y < cols; ++y) {
            if (preSum[i][j] - preSum[i][y] > 0)
                res = (res + dp(i, y, cuts-1, preSum, memo, rows, cols, MOD)) % MOD;
        }
        memo[i][j][cuts] = res;
        return res;
    }
}

/**
 * @param {string[]} pizza
 * @param {number} k
 * @return {number}
 */
var ways = function(pizza, k) {
    const MOD = 1e9 + 7;
    const rows = pizza.length, cols = pizza[0].length;
    // Precompute prefix sums
    const preSum = Array.from({length: rows+1}, () => Array(cols+1).fill(0));
    for (let i = rows - 1; i >= 0; --i) {
        for (let j = cols - 1; j >= 0; --j) {
            preSum[i][j] = (pizza[i][j] === 'A' ? 1 : 0)
                + preSum[i+1][j] + preSum[i][j+1] - preSum[i+1][j+1];
        }
    }
    const memo = new Map();

    function dp(i, j, cuts) {
        const key = i + ',' + j + ',' + cuts;
        if (preSum[i][j] === 0) return 0;
        if (cuts === 1) return 1;
        if (memo.has(key)) return memo.get(key);
        let res = 0;
        // Horizontal cuts
        for (let x = i+1; x < rows; ++x) {
            if (preSum[i][j] - preSum[x][j] > 0)
                res = (res + dp(x, j, cuts-1)) % MOD;
        }
        // Vertical cuts
        for (let y = j+1; y < cols; ++y) {
            if (preSum[i][j] - preSum[i][y] > 0)
                res = (res + dp(i, y, cuts-1)) % MOD;
        }
        memo.set(key, res);
        return res;
    }

    return dp(0, 0, k);
};

AlgoMap.io

Want Help Cracking FAANG?