Maximum Area of a Piece of Cake After Cuts: Greedy Gap Finding

You are given a rectangular cake of size h x w and two arrays: horizontalCuts and verticalCuts. Each horizontal cut is a distance from the top of the cake, and each vertical cut is a distance from the left. After making all the cuts, find the maximum area of any resulting piece. Since the answer can be large, return it modulo 10^9 + 7.

This is LeetCode 1465: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts.

Why this problem matters

At first glance, this looks like it might require simulating the grid of pieces and checking every one. But the structure of the problem allows a much cleaner approach. Horizontal cuts and vertical cuts operate independently of each other. Every horizontal cut crosses the entire width of the cake, and every vertical cut crosses the entire height. That means the shape of every piece is determined by exactly one horizontal gap and one vertical gap. The largest piece is simply the largest horizontal gap times the largest vertical gap.

This "independence" insight shows up across many problems. Whenever two dimensions of a problem do not interact, you can solve each dimension separately and combine the results. It is a powerful simplification that turns what looks like a 2D search into two 1D scans.

The problem also reinforces a core greedy pattern: sorting data to reveal structure that is hidden in the unsorted input. Once you sort the cuts, the maximum gap between consecutive values jumps out immediately. You will see this same "sort, then scan for max gap" idea in problems about partitioning arrays, scheduling tasks, and placing items with minimum spacing.

The key insight

Horizontal and vertical cuts are completely independent. Every horizontal cut spans the full width, and every vertical cut spans the full height. So the largest rectangular piece must sit between two consecutive horizontal cuts and two consecutive vertical cuts.

This means you do not need to consider all combinations of pieces. You just need the largest gap in each dimension:

1. Sort the horizontal cuts and add the boundaries (0 at the start, h at the end).
2. Sort the vertical cuts and add the boundaries (0 at the start, w at the end).
3. Find the maximum difference between consecutive values in each sorted list.
4. Multiply the two maximum gaps. That product is the area of the largest piece.

The solution

def max_area(h: int, w: int, horizontalCuts: list[int], verticalCuts: list[int]) -> int:
    MOD = 10**9 + 7

    horizontalCuts.sort()
    verticalCuts.sort()

    max_h = max(horizontalCuts[0], h - horizontalCuts[-1])
    for i in range(1, len(horizontalCuts)):
        max_h = max(max_h, horizontalCuts[i] - horizontalCuts[i - 1])

    max_v = max(verticalCuts[0], w - verticalCuts[-1])
    for i in range(1, len(verticalCuts)):
        max_v = max(max_v, verticalCuts[i] - verticalCuts[i - 1])

    return (max_h * max_v) % MOD

The function starts by sorting both cut arrays. Sorting is what makes consecutive differences meaningful. Without it, adjacent entries in the array have no geometric relationship.

After sorting, we compute the maximum gap for horizontal cuts. The first gap is horizontalCuts[0] - 0 (the distance from the top of the cake to the first cut). The last gap is h - horizontalCuts[-1] (from the last cut to the bottom). We initialize max_h with the larger of these two boundary gaps, then scan through the interior gaps.

We repeat the same process for vertical cuts, finding max_v.

Finally, we multiply the two max gaps and return the result modulo 10^9 + 7. The modular arithmetic is only applied at the end because both gaps individually fit in a standard integer.

Visual walkthrough

Let's trace through the example with h=5, w=4, horizontalCuts=[1,2,4], and verticalCuts=[1,3].

The algorithm processes each dimension in isolation. In the horizontal direction, the sorted boundaries are [0, 1, 2, 4, 5], and the largest gap is 2 (between positions 2 and 4). In the vertical direction, the sorted boundaries are [0, 1, 3, 4], and the largest gap is also 2 (between positions 1 and 3). Multiplying gives 2 * 2 = 4, which is the area of the largest piece.

Complexity analysis

Time is O(n log n + m log m) where n is the length of horizontalCuts and m is the length of verticalCuts. Sorting dominates. The subsequent linear scan to find the max gap is O(n + m), which is absorbed by the sort.

Space is O(1) beyond the input if you sort in place. Python's list.sort() is in-place, so no auxiliary arrays are needed. If you use sorted() instead, it becomes O(n + m) for the copies.

The building blocks

1. Max consecutive gap after sorting

nums.sort()
max_gap = max(nums[0], boundary - nums[-1])
for i in range(1, len(nums)):
    max_gap = max(max_gap, nums[i] - nums[i - 1])

This is the core subroutine. Sort the values, then sweep through them keeping track of the largest difference between neighbors. You handle the boundaries (0 and the dimension size) as special cases at the edges. This same pattern appears in problems like Maximum Gap (LeetCode 164) and in partitioning problems where you need to find the widest empty region.

2. Modular multiplication for large results

MOD = 10**9 + 7
result = (a * b) % MOD

When the problem says "return the answer modulo 10^9 + 7," apply the modulus at the very end. Since the two gap values are each at most 10^9, their product fits in a 64-bit integer (up to about 10^18). Python handles big integers natively, so overflow is not a concern, but in languages like Java or C++ you would cast to long before multiplying.

Edge cases

• Single cut in one direction. If there is only one horizontal cut, the two gaps are horizontalCuts[0] and h - horizontalCuts[0]. The logic still works because we initialize with boundary gaps.
• Cuts at the boundaries. A cut at position 0 or at position h creates a gap of 0 on that side. The max gap will come from the other gaps.
• All cuts evenly spaced. Every gap is the same. The max gap equals h / (len(horizontalCuts) + 1). The answer is that value times the analogous vertical gap.
• Very large dimensions with few cuts. h and w can be up to 10^9, but the arrays might be small. Sorting is still fast because it depends on array length, not dimension size. The boundary gaps will likely dominate.

From understanding to recall

The logic here is clean: sort, find max gap, multiply. But under time pressure, the details matter. Do you remember to include the boundary gaps (0 to first cut, last cut to dimension)? Do you apply the modulus at the right point? Do you handle both dimensions separately?

These are exactly the kinds of details that slip away if you only read through a solution once. Spaced repetition locks them in. You practice writing the max-gap scan from memory, first after a day, then after three days, then after a week. Each time, the pattern gets more automatic. When a similar greedy problem shows up in your interview, you recognize the structure and write the code without hesitation.

Related posts

• Merge Intervals - Another problem where sorting transforms a messy input into a clean left-to-right scan
• Insert Interval - Builds on the sorting and boundary logic used in interval problems
• Jump Game - A greedy problem where scanning for the farthest reachable position mirrors scanning for the widest gap

CodeBricks breaks Maximum Area of a Piece of Cake into its sorting and gap-finding building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the greedy pattern is automatic. When a problem asks you to optimize across independent dimensions, you know exactly what to do.