Number of Ways of Cutting a Pizza - Problem

Array Dynamic Programming Memoization Matrix Prefix Sum Hard

🍕 Imagine you're at a pizza party and need to share a rectangular pizza with your friends! The pizza is represented as a rows × cols grid where each cell contains either:

'A' - an apple topping 🍎
'.' - an empty space

Your challenge is to cut the pizza into k pieces using exactly k-1 cuts, where each piece must contain at least one apple.

Cutting Rules:

Vertical cuts: Split along column boundaries - left piece goes to current person
Horizontal cuts: Split along row boundaries - top piece goes to current person
The final remaining piece goes to the last person

Return the number of ways to cut the pizza such that everyone gets at least one apple. Since the answer can be huge, return it modulo 10⁹ + 7.

Input & Output

example_1.py — Python

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

› Output: 3

💡 Note: There are 3 ways to cut the pizza: 1) Horizontal cut at row 1, then vertical cut at col 1. 2) Vertical cut at col 1, then horizontal cut at row 1. 3) Horizontal cut at row 1, then vertical cut at col 2. Each way results in 3 pieces where each has at least one apple.

example_2.py — Python

$ Input: pizza = ["A..","AA.","..."], k = 3

› Output: 1

💡 Note: There's only 1 way to cut this pizza into 3 pieces with each piece having an apple: first cut vertically at column 1 (giving left piece with 2 apples), then cut the remaining piece horizontally at row 1.

example_3.py — Python

$ Input: pizza = ["A..","A..","..."], k = 1

› Output: 1

💡 Note: No cuts needed since k=1. The entire pizza goes to one person and it contains apples, so there's 1 way.

Constraints

1 ≤ rows, cols ≤ 50
rows == pizza.length
cols == pizza[i].length
1 ≤ k ≤ 10
pizza[i][j] is either 'A' or '.'
Each piece must contain at least one apple

Visualization

Tap to expand

Asked in

A Amazon 15 G Google 8 ⊞ Microsoft 5 f Meta 3

The optimal solution uses dynamic programming with memoization combined with prefix sums. We precompute a 2D prefix sum array to check if any rectangle contains apples in O(1) time, then use memoized recursion with state (row, col, people_left) to count all valid cutting sequences. Time complexity: O(rows × cols × k × (rows + cols)).

Common Approaches

✓ Brute Force Recursion

⏱️ Time: O((rows*cols)^k * rows * cols) Space: O(k)

Recursively try every possible cut (horizontal and vertical) at each step, checking if the remaining piece has apples. This approach explores all possible cutting sequences without any memoization or preprocessing.

Dynamic Programming with Prefix Sums

⏱️ Time: O(rows * cols * k * (rows + cols)) Space: O(rows * cols * k)

This approach optimizes the brute force method by using prefix sums to quickly check if a rectangle contains apples, and memoization to avoid recomputing the same subproblems. We precompute a 2D prefix sum array where each cell contains the total number of apples in the rectangle from that position to the bottom-right corner.

Brute Force Recursion — Algorithm Steps

For each recursive call, try all possible horizontal cuts
For each horizontal cut, check if the top piece has at least one apple
If valid, recursively solve for the bottom piece with k-1 people
Repeat the same process for vertical cuts
Sum up all valid ways from both horizontal and vertical cuts

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with full pizza, need k cuts

Try All Cuts

For each position, try both horizontal and vertical cuts

Validate Piece

Check if the cut piece contains at least one apple

Recurse

If valid, recursively solve for remaining pizza with k-1 people

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MOD 1000000007
#define MAXN 51

int rows, cols, k;
char pizza[MAXN][MAXN];

int countApples(int r, int c) {
    int count = 0;
    for (int i = r; i < rows; i++)
        for (int j = c; j < cols; j++)
            if (pizza[i][j] == 'A') count++;
    return count;
}

long long recurse(int r, int c, int cuts) {
    if (cuts == 0)
        return countApples(r, c) > 0 ? 1 : 0;

    if (countApples(r, c) == 0) return 0;

    long long ways = 0;

    // Try all horizontal cuts
    for (int i = r; i < rows - 1; i++) {
        int hasApple = 0;
        for (int ri = r; ri <= i && !hasApple; ri++)
            for (int ci = c; ci < cols && !hasApple; ci++)
                if (pizza[ri][ci] == 'A') hasApple = 1;
        if (hasApple)
            ways = (ways + recurse(i + 1, c, cuts - 1)) % MOD;
    }

    // Try all vertical cuts
    for (int j = c; j < cols - 1; j++) {
        int hasApple = 0;
        for (int ri = r; ri < rows && !hasApple; ri++)
            for (int ci = c; ci <= j && !hasApple; ci++)
                if (pizza[ri][ci] == 'A') hasApple = 1;
        if (hasApple)
            ways = (ways + recurse(r, j + 1, cuts - 1)) % MOD;
    }

    return ways;
}

int solution() {
    return (int)recurse(0, 0, k - 1);
}

void parsePizza(const char* line) {
    rows = 0;
    const char* p = line;
    while (*p) {
        if (*p == '"') {
            p++;
            int col = 0;
            while (*p && *p != '"')
                pizza[rows][col++] = *p++;
            pizza[rows][col] = '\0';
            rows++;
            if (*p == '"') p++;
        } else {
            p++;
        }
    }
    cols = (rows > 0) ? (int)strlen(pizza[0]) : 0;
}

int main() {
    char line[4096];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\r\n")] = '\0';
    parsePizza(line);

    char kline[32];
    fgets(kline, sizeof(kline), stdin);
    k = atoi(kline);

    printf("%d\n", solution());
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((rows*cols)^k * rows * cols)

For each of the exponential number of cutting sequences, we need O(rows*cols) to count apples in a rectangle

✓ Linear Growth

Space Complexity

O(k)

Recursion depth is at most k for the number of cuts needed

✓ Linear Space

38.4K Views

Medium Frequency

~35 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Number of Ways of Cutting a Pizza - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler