Skip to main content

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

Difficulty: Medium | Pattern: Greedy / Sorting | Company tags: Amazon, Google

Problem Statement​

You have 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
  • 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. Since the answer can be large, return it modulo 10^9 + 7.

Example 1:

Input: h=5, w=4, horizontalCuts=[1,2,4], verticalCuts=[1,3]
Output: 4
Explanation: Max horizontal gap: max(4-2)=2; Max vertical gap: max(3-1)=2; Area=4

Example 2:

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

Approach: Find Max Gaps — O(n log n + m log m)​

Key insight: After cuts, the maximum piece area = (max horizontal gap) × (max vertical gap). Just sort the cut positions and find the largest gap between consecutive cuts (including edges at 0 and h/w).

def maxArea(h: int, w: int, horizontalCuts: list[int], verticalCuts: list[int]) -> int:
    MOD = 10**9 + 7
    
    horizontalCuts.sort()
    verticalCuts.sort()
    
    def max_gap(cuts, size):
        max_g = cuts[0]  # gap from 0 to first cut
        for i in range(1, len(cuts)):
            max_g = max(max_g, cuts[i] - cuts[i-1])
        max_g = max(max_g, size - cuts[-1])  # gap from last cut to edge
        return max_g
    
    max_h = max_gap(horizontalCuts, h)
    max_v = max_gap(verticalCuts, w)
    
    return (max_h * max_v) % MOD

Algorithm Flow​

Dry Run​

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

Horizontal gaps: 1-0=1, 2-1=1, 4-2=2, 5-4=1 → max=2 Vertical gaps: 1-0=1, 3-1=2, 4-3=1 → max=2

Area = 2×2 = 4 ✓

Edge Cases​

  • No cuts in one direction → gap = full dimension
  • Single cut → at most 2 pieces per dimension
  • Cuts at extremes → may give gap of 0 (shouldn't happen per constraints)

Complexity​

  • Time: O(n log n + m log m) for sorting
  • Space: O(1) extra

Key Terms​

TermDefinition
Gap maximizationFinding the largest distance between consecutive sorted values, which represents the widest uncut strip of cake.
SortingOrdering the cut positions so adjacent cuts can be compared in a single linear pass.
Boundary sentinelTreating 0 and h/w as implicit cuts so the first and last gaps are measured correctly.
Modular arithmeticTaking % (10^9 + 7) on the final product to keep the result within standard integer bounds.
Independence of dimensionsThe horizontal and vertical cuts don't interact — the max area is simply the product of the two independent max gaps.

FAQ​

Q: Why does the largest piece always come from the max horizontal gap times the max vertical gap? A: Every piece of cake is a rectangle formed by one horizontal strip and one vertical strip. The largest possible rectangle uses the widest strip in each direction, so pairing the two maximum gaps always yields the maximum-area piece, even if that exact rectangle sits at different physical positions.

Q: Can this be solved without sorting? A: Not efficiently in general — you need the cuts in order to compute consecutive gaps. If the inputs were guaranteed sorted, you could skip that step and get true O(n + m) time.

Q: What if horizontalCuts or verticalCuts is empty? A: Per constraints this won't happen (there's always at least one cut), but conceptually an empty array would mean the max gap in that direction equals the full dimension (h or w).

Q: Why is the modulo applied only at the end and not during gap computation? A: The gaps themselves (h, w up to 10^9) and their product can exceed 32-bit range but fit comfortably in 64-bit/Python integers, so modulo is only needed once, on the final multiplication, to match the problem's required output format.

Q: How would the approach change if cuts could be duplicated or cut positions could equal 0 or h/w? A: Duplicate cuts just produce a zero gap at that point, which never becomes the max (unless all cuts coincide), so no special-casing is needed. Cuts at exactly 0 or h/w are typically excluded by problem constraints since they wouldn't actually divide the cake.

Quick Revision​

  • Pattern: gap maximization after sorting, applied independently per dimension.
  • Max piece area = (max horizontal gap) × (max vertical gap).
  • Sort horizontalCuts and verticalCuts first — O(n log n + m log m).
  • Include the edges (0 and h, 0 and w) as virtual cut boundaries when computing gaps.
  • Compute gaps with one linear scan per array after sorting.
  • Multiply the two max gaps, then apply % (10^9 + 7) once at the end.
  • Time: O(n log n + m log m); Space: O(1) extra (ignoring sort's internal space).
  • Edge cases: single cut, cuts clustered near one edge, cuts already sorted.
  • The two dimensions never need to be considered jointly — this decoupling is the key insight that avoids an O(n·m) brute force.

This problem's core pattern — sort then scan for the maximum gap — also appears in:

  • Interval/gap-based problems such as "Missing Ranges" and "Maximum Gap" (sort array, find largest consecutive difference).
  • Meeting-room / interval-scheduling style problems where sorting endpoints before a linear scan is the standard technique.
  • 88-MergeSortedArray.md — shares the sorted-array linear-scan technique.

No other file in this directory currently covers the exact "maximum gap" or "interval scheduling" pattern by name; if added later, link them here.