Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts - Problem

You are given a rectangular cake of size h x w and two arrays of integers horizontalCuts and verticalCuts where:

horizontalCuts[i] is the distance from the top of the rectangular cake to the i-th horizontal cut and similarly, and verticalCuts[j] is the distance from the left of the rectangular cake to the j-th vertical cut.

Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a large number, return this modulo 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]

› Output: 4

💡 Note: After adding boundaries: horizontal cuts [0,1,2,4,5], vertical cuts [0,1,3,4]. Maximum height gap = 5-2 = 3, maximum width gap = 3-1 = 2. But actually max height gap = 2 (4-2) and max width = 2 (3-1), so area = 4.

Example 2 — Single Cut

$ Input: h = 5, w = 4, horizontalCuts = [3], verticalCuts = [1]

› Output: 9

💡 Note: Horizontal gaps: [3-0=3, 5-3=2], max = 3. Vertical gaps: [1-0=1, 4-1=3], max = 3. Area = 3×3 = 9.

Example 3 — No Cuts

$ Input: h = 5, w = 4, horizontalCuts = [], verticalCuts = []

› Output: 20

💡 Note: No internal cuts, so the entire cake 5×4 = 20 is the maximum piece.

Constraints

2 ≤ h, w ≤ 10⁹
1 ≤ horizontalCuts.length, verticalCuts.length ≤ 10⁵
1 ≤ horizontalCuts[i] < h
1 ≤ verticalCuts[i] < w
All the elements in horizontalCuts are distinct
All the elements in verticalCuts are distinct

Visualization

Tap to expand

Asked in

G Google 12 a Amazon 8 f Facebook 6

The optimal approach recognizes that maximum area equals maximum height gap × maximum width gap. After adding boundary cuts and sorting, we find the largest spacing between consecutive cuts in each direction. Time: O(n log n + m log m), Space: O(1).

Common Approaches

✓ Brute Force - Check All Rectangles

⏱️ Time: O(n²m²) Space: O(1)

For every pair of horizontal cuts and every pair of vertical cuts, calculate the area of the rectangle formed. This requires checking all combinations of cut positions.

Optimal - Sort and Find Max Gaps

⏱️ Time: O(n log n + m log m) Space: O(1)

The key insight is that the maximum area rectangle must be formed by the largest horizontal gap and the largest vertical gap. We don't need to check all combinations.

Brute Force - Check All Rectangles — Algorithm Steps

Step 1: Add boundary cuts at 0 and h/w
Step 2: Generate all rectangle combinations
Step 3: Calculate area for each rectangle
Step 4: Return maximum area mod 10^9+7

Visualization

Tap to expand

Step-by-Step Walkthrough

Add Boundaries

Add cuts at edges (0, h) and (0, w)

Generate Pairs

Create all pairs of horizontal and vertical cuts

Calculate Areas

Compute area for each rectangle and find maximum

Code -

solution.c — C

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

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int solution(int h, int w, int* horizontalCuts, int hSize, int* verticalCuts, int vSize) {
    const long long MOD = 1000000007;
    
    // Add boundary cuts
    int* hCuts = (int*)malloc((hSize + 2) * sizeof(int));
    hCuts[0] = 0;
    for (int i = 0; i < hSize; i++) {
        hCuts[i + 1] = horizontalCuts[i];
    }
    hCuts[hSize + 1] = h;
    int hTotal = hSize + 2;
    qsort(hCuts, hTotal, sizeof(int), compare);
    
    int* vCuts = (int*)malloc((vSize + 2) * sizeof(int));
    vCuts[0] = 0;
    for (int i = 0; i < vSize; i++) {
        vCuts[i + 1] = verticalCuts[i];
    }
    vCuts[vSize + 1] = w;
    int vTotal = vSize + 2;
    qsort(vCuts, vTotal, sizeof(int), compare);
    
    // Find maximum gap between consecutive horizontal cuts
    long long maxHeight = 0;
    for (int i = 1; i < hTotal; i++) {
        long long gap = hCuts[i] - hCuts[i-1];
        if (gap > maxHeight) {
            maxHeight = gap;
        }
    }
    
    // Find maximum gap between consecutive vertical cuts
    long long maxWidth = 0;
    for (int i = 1; i < vTotal; i++) {
        long long gap = vCuts[i] - vCuts[i-1];
        if (gap > maxWidth) {
            maxWidth = gap;
        }
    }
    
    free(hCuts);
    free(vCuts);
    
    return (int)((maxHeight * maxWidth) % MOD);
}

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        arr[(*size)++] = (int)strtol(p, (char**)&p, 10);
    }
}

int main() {
    int h, w;
    scanf("%d", &h);
    scanf("%d", &w);
    
    int horizontalCuts[100000], verticalCuts[100000];
    char line[1000000];
    
    // Read horizontal cuts
    scanf(" %[^\n]", line);
    int hSize;
    parseArray(line, horizontalCuts, &hSize);
    
    // Read vertical cuts
    scanf(" %[^\n]", line);
    int vSize;
    parseArray(line, verticalCuts, &vSize);
    
    printf("%d\n", solution(h, w, horizontalCuts, hSize, verticalCuts, vSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²m²)

Nested loops checking all pairs of horizontal cuts (n²) and all pairs of vertical cuts (m²)

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

98.4K Views

Medium Frequency

~25 min Avg. Time

2.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

Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Rectangles — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler