Number of Ways of Cutting a Pizza

Hard
1510.

Number of Ways of Cutting a Pizza

Number of Ways of Cutting a Pizza is a hard coding problem on arrays, dynamic programming and matrix, asked in Amazon and Google interviews.

A rectangular pizza is given as a grid pizza of rows strings, each cols characters long: 'A' marks a cell with an apple and '.' an empty cell. You must cut it into k pieces with k - 1 cuts.

Each cut is made on the part of the pizza that is still left: choose a direction and a position on a cell boundary, then cut straight across. A horizontal cut gives away the upper part; a vertical cut gives away the left part. After the last cut, the remaining part is the final piece. Every piece — each one given away and the final one — must contain at least one apple.

Return the number of ways to cut the pizza, modulo 10^9 + 7. Two ways are different if some cut differs in direction or position.

Example 1

Input
pizza = [".A.","A.A","..A"], k = 3
Output
7

Example 2

Input
pizza = ["A.A","..."], k = 2
Output
2
Explanation
Both vertical cuts work. The horizontal cut would leave the empty bottom row as the last piece.

Example 3

Input
pizza = ["AA","AA"], k = 4
Output
0
Explanation
Every cut removes at least a whole row or column, so a 2 × 2 pizza allows at most two cuts.

Constraints

  • 1 <= rows, cols <= 50
  • rows == pizza.length
  • cols == pizza[i].length
  • 1 <= k <= 10
  • pizza consists of 'A' and '.' only
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} pizza
 * @param {number} k
 * @return {number}
 */
var ways = function(pizza, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Ways of Cutting a Pizza — Problem & Solution

Number of Ways of Cutting a Pizza solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Number of Ways of Cutting a Pizza is a hard coding problem on arrays, dynamic programming and matrix, asked in Amazon and Google interviews.

Problem statement

A rectangular pizza is given as a grid pizza of rows strings, each cols characters long: 'A' marks a cell with an apple and '.' an empty cell. You must cut it into k pieces with k - 1 cuts.

Each cut is made on the part of the pizza that is still left: choose a direction and a position on a cell boundary, then cut straight across. A horizontal cut gives away the upper part; a vertical cut gives away the left part. After the last cut, the remaining part is the final piece. Every piece — each one given away and the final one — must contain at least one apple.

Return the number of ways to cut the pizza, modulo 10^9 + 7. Two ways are different if some cut differs in direction or position.

Example 1

Input: pizza = [".A.","A.A","..A"], k = 3
Output: 7

Example 2

Input: pizza = ["A.A","..."], k = 2
Output: 2
Explanation: Both vertical cuts work. The horizontal cut would leave the empty bottom row as the last piece.

Example 3

Input: pizza = ["AA","AA"], k = 4
Output: 0
Explanation: Every cut removes at least a whole row or column, so a 2 × 2 pizza allows at most two cuts.

Constraints

  • 1 <= rows, cols <= 50
  • rows == pizza.length
  • cols == pizza[i].length
  • 1 <= k <= 10
  • pizza consists of 'A' and '.' only

Hints for Number of Ways of Cutting a Pizza

  1. Hint 1

    Whatever cuts you make, the part still left is always a bottom-right sub-rectangle starting at some cell (r, c).

  2. Hint 2

    Let ways(p, r, c) count the ways to cut the sub-pizza from (r, c) into p pieces. A cut at row nr hands away rows r..nr-1 and continues with (nr, c); a cut at column nc continues with (r, nc).

  3. Hint 3

    Precompute apples[r][c], the number of apples in the sub-pizza from (r, c), as a suffix sum. The piece given away by a horizontal cut has apples[r][c] - apples[nr][c] apples; by a vertical cut, apples[r][c] - apples[r][nc].

How to solve Number of Ways of Cutting a Pizza

Since cuts always give away the top or the left, what remains is always the bottom-right sub-rectangle anchored at some cell. That makes the state (pieces still to produce, r, c), and a 2-D suffix sum of apples answers 'does this piece have an apple?' in O(1).

Approach

  1. Compute apples[r][c] for the sub-pizza from (r, c) to the bottom-right, by inclusion–exclusion from the bottom-right corner.
  2. Base layer: dp[r][c] = 1 if apples[r][c] > 0, else 0 (one piece, which must hold an apple).
  3. Repeat k - 1 times, building a new layer: for each (r, c), sum the previous layer at (nr, c) for every nr > r with apples[r][c] - apples[nr][c] > 0, and at (r, nc) for every nc > c with apples[r][c] - apples[r][nc] > 0; reduce modulo 10^9 + 7.
  4. Return the last layer at (0, 0).

Why it works

Every sequence of cuts is determined by its first cut and the sequence of cuts on what remains. The first cut is valid exactly when the piece it gives away holds an apple, and the remaining sub-pizza must then be cut into p - 1 valid pieces — which is the previous layer at the new anchor (and that layer is 0 when the remainder has no apple). Summing over all first cuts counts every valid sequence exactly once.

Complexity

  • Time — O(k · rows · cols · (rows + cols))
  • Space — O(rows · cols)

Pitfalls

  • Check the piece being given away, not the remaining part — the remaining part is checked by the next layer.
  • The final piece needs an apple too; the base layer encodes that.
  • Reduce modulo 10^9 + 7 as you sum.

Reference solution

Python

from typing import List

def ways(pizza: List[str], k: int) -> int:
    MOD = 10 ** 9 + 7
    R, C = len(pizza), len(pizza[0])
    apples = [[0] * (C + 1) for _ in range(R + 1)]
    for r in range(R - 1, -1, -1):
        for c in range(C - 1, -1, -1):
            apples[r][c] = (1 if pizza[r][c] == 'A' else 0) + apples[r + 1][c] + apples[r][c + 1] - apples[r + 1][c + 1]
    dp = [[1 if apples[r][c] > 0 else 0 for c in range(C)] for r in range(R)]
    for _ in range(k - 1):
        nd = [[0] * C for _ in range(R)]
        for r in range(R):
            for c in range(C):
                total = 0
                for nr in range(r + 1, R):
                    if apples[r][c] - apples[nr][c] > 0:
                        total += dp[nr][c]
                for nc in range(c + 1, C):
                    if apples[r][c] - apples[r][nc] > 0:
                        total += dp[r][nc]
                nd[r][c] = total % MOD
        dp = nd
    return dp[0][0]

Java

public static int ways(String[] pizza, int k) {
    final long MOD = 1000000007L;
    int R = pizza.length, C = pizza[0].length();
    int[][] apples = new int[R + 1][C + 1];
    for (int r = R - 1; r >= 0; r--) {
        for (int c = C - 1; c >= 0; c--) {
            apples[r][c] = (pizza[r].charAt(c) == 'A' ? 1 : 0) + apples[r + 1][c] + apples[r][c + 1] - apples[r + 1][c + 1];
        }
    }
    long[][] dp = new long[R][C];
    for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) dp[r][c] = apples[r][c] > 0 ? 1 : 0;
    for (int p = 1; p < k; p++) {
        long[][] nd = new long[R][C];
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                long total = 0;
                for (int nr = r + 1; nr < R; nr++) if (apples[r][c] - apples[nr][c] > 0) total += dp[nr][c];
                for (int nc = c + 1; nc < C; nc++) if (apples[r][c] - apples[r][nc] > 0) total += dp[r][nc];
                nd[r][c] = total % MOD;
            }
        }
        dp = nd;
    }
    return (int) dp[0][0];
}

C++

int ways(vector<string>& pizza, int k) {
    const long long MOD = 1000000007LL;
    int R = pizza.size(), C = pizza[0].size();
    vector<vector<int>> apples(R + 1, vector<int>(C + 1, 0));
    for (int r = R - 1; r >= 0; r--) {
        for (int c = C - 1; c >= 0; c--) {
            apples[r][c] = (pizza[r][c] == 'A' ? 1 : 0) + apples[r + 1][c] + apples[r][c + 1] - apples[r + 1][c + 1];
        }
    }
    vector<vector<long long>> dp(R, vector<long long>(C, 0));
    for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) dp[r][c] = apples[r][c] > 0 ? 1 : 0;
    for (int p = 1; p < k; p++) {
        vector<vector<long long>> nd(R, vector<long long>(C, 0));
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                long long total = 0;
                for (int nr = r + 1; nr < R; nr++) if (apples[r][c] - apples[nr][c] > 0) total += dp[nr][c];
                for (int nc = c + 1; nc < C; nc++) if (apples[r][c] - apples[r][nc] > 0) total += dp[r][nc];
                nd[r][c] = total % MOD;
            }
        }
        dp = nd;
    }
    return (int)dp[0][0];
}

JavaScript

var ways = function(pizza, k) {
    var MOD = 1000000007, R = pizza.length, C = pizza[0].length;
    var apples = [];
    for (var r = 0; r <= R; r++) apples.push(new Array(C + 1).fill(0));
    for (var r = R - 1; r >= 0; r--) {
        for (var c = C - 1; c >= 0; c--) {
            apples[r][c] = (pizza[r][c] === 'A' ? 1 : 0) + apples[r + 1][c] + apples[r][c + 1] - apples[r + 1][c + 1];
        }
    }
    var dp = [];
    for (var r = 0; r < R; r++) {
        dp.push([]);
        for (var c = 0; c < C; c++) dp[r].push(apples[r][c] > 0 ? 1 : 0);
    }
    for (var p = 1; p < k; p++) {
        var nd = [];
        for (var r = 0; r < R; r++) {
            nd.push(new Array(C).fill(0));
            for (var c = 0; c < C; c++) {
                var total = 0;
                for (var nr = r + 1; nr < R; nr++) if (apples[r][c] - apples[nr][c] > 0) total += dp[nr][c];
                for (var nc = c + 1; nc < C; nc++) if (apples[r][c] - apples[r][nc] > 0) total += dp[r][nc];
                nd[r][c] = total % MOD;
            }
        }
        dp = nd;
    }
    return dp[0][0];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming