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

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: 6

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

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

Understanding the Visualization

Input

Cake dimensions 5×4 with cuts at [1,2,4] horizontal and [1,3] vertical

Process

Cuts create a grid - find largest rectangle

Output

Maximum area piece = 4

Key Takeaway

🎯 Key Insight: The largest cake piece is formed by the maximum spacing between consecutive cuts in each direction

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

Approach	Time	Space	Notes
✓ Optimal - Sort and Find Max Gaps	O(n log n + m log m)	O(1)	Sort cuts and find the largest gap in each direction, then multiply
Brute Force - Check All Rectangles	O(n²m²)	O(1)	Generate all possible rectangles and find the one with maximum area

Optimal - Sort and Find Max Gaps — Algorithm Steps

Step 1: Add boundary cuts at 0 and h/w
Step 2: Sort both cut arrays
Step 3: Find maximum gap between consecutive cuts in each direction
Step 4: Multiply max horizontal gap × max vertical gap

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Cuts

Add boundaries and sort both cut arrays

Find Max Gaps

Calculate maximum spacing between consecutive cuts

Multiply

Max area = max height × max width

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

int main() {
    int h, w;
    scanf("%d", &h);
    scanf("%d", &w);
    
    // Simple parsing - assuming small arrays
    int horizontalCuts[100], verticalCuts[100];
    int hSize = 0, vSize = 0;
    
    // Read horizontal cuts
    char line[1000];
    scanf(" %s", line);
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        horizontalCuts[hSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    // Read vertical cuts
    scanf(" %s", line);
    token = strtok(line + 1, ",]");
    while (token != NULL) {
        verticalCuts[vSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(h, w, horizontalCuts, hSize, verticalCuts, vSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + m log m)

Sorting horizontal cuts takes O(n log n) and vertical cuts takes O(m log m)

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for variables (sorting can be in-place)

✓ Linear Space

98.3K 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimal - Sort and Find Max Gaps — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler