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

This problem gives us a rectangular cake with height h and width w. We are also given two arrays: - horizontalCuts, whic

leetcodemediumarraygreedysorting

LeetCode Problem 1465

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

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

Problem Understanding

This problem gives us a rectangular cake with height h and width w. We are also given two arrays:

  • horizontalCuts, which contains the positions of horizontal cuts measured from the top edge
  • verticalCuts, which contains the positions of vertical cuts measured from the left edge

Every cut slices completely across the cake in its direction. After performing all cuts, the cake is divided into multiple rectangular pieces. The task is to determine the area of the largest resulting piece.

The important observation is that every piece is rectangular. Its height is determined by the distance between two consecutive horizontal boundaries, and its width is determined by the distance between two consecutive vertical boundaries.

The output should be the maximum possible area among all resulting pieces. Since the area can become extremely large, we must return the result modulo 10^9 + 7.

The constraints are important:

  • h and w can be as large as 10^9
  • The number of cuts can be as large as 10^5

These limits immediately tell us that we cannot simulate every resulting rectangle explicitly. A naive approach that examines every possible piece would be far too slow.

The problem also guarantees:

  • All cuts are distinct
  • Every cut lies strictly inside the cake
  • There is at least one cut in each direction

Several edge cases are important:

  • The largest piece may lie against the cake boundary, so we must consider the distance from the edge to the nearest cut.
  • The cuts may not be sorted.
  • The largest horizontal gap and largest vertical gap may occur at different positions.
  • The multiplication may overflow normal 32-bit integers, especially in Go.

Approaches

Brute Force Approach

A brute force solution would first determine every horizontal segment and every vertical segment, then generate every possible rectangle formed by combining them.

For example:

  • If there are m horizontal segments
  • And n vertical segments

Then there are m * n cake pieces.

We could compute each rectangle area individually and track the maximum.

This works because every resulting piece is formed by one horizontal interval and one vertical interval.

However, this approach is unnecessarily expensive. The number of segments can reach 10^5, which means the number of rectangles could approach 10^10. That is impossible to process within time limits.

Optimal Approach

The key insight is that the maximum rectangle area is simply:

  • the maximum horizontal gap
  • multiplied by the maximum vertical gap

We do not need to examine every rectangle individually.

Why does this work?

Every piece's area is:

piece_area = horizontal_gap * vertical_gap

To maximize the product, we independently maximize:

  • the height of a segment
  • the width of a segment

So the problem reduces to:

  1. Sort the horizontal cuts
  2. Find the largest distance between consecutive horizontal boundaries
  3. Sort the vertical cuts
  4. Find the largest distance between consecutive vertical boundaries
  5. Multiply the two maximum gaps

The boundaries of the cake itself must also be included:

  • 0 and h for horizontal cuts
  • 0 and w for vertical cuts

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n) O(1) Checks every resulting rectangle
Optimal O(m log m + n log n) O(1) or O(log n) depending on sorting Finds only the largest gaps

Algorithm Walkthrough

  1. Sort the horizontalCuts array so consecutive cuts can be examined in order.
  2. Compute the maximum horizontal gap.

First, consider the gap between the top edge (0) and the first cut. Then examine every consecutive pair of cuts. Finally, consider the gap between the last cut and the bottom edge (h). 3. Sort the verticalCuts array for the same reason. 4. Compute the maximum vertical gap.

Again, include the left edge (0) and right edge (w) when calculating distances. 5. Multiply the largest horizontal gap by the largest vertical gap.

This gives the largest possible rectangular piece. 6. Return the result modulo 10^9 + 7.

Why it works

Every final cake piece is formed by exactly one horizontal interval and one vertical interval. The area of a piece is the product of those two dimensions.

Because multiplication is monotonic for positive values, the largest area must come from:

  • the largest horizontal interval
  • and the largest vertical interval

No other combination can produce a larger area.

Python Solution

from typing import List

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        MOD = 10**9 + 7

        horizontalCuts.sort()
        verticalCuts.sort()

        max_horizontal_gap = horizontalCuts[0]

        for i in range(1, len(horizontalCuts)):
            gap = horizontalCuts[i] - horizontalCuts[i - 1]
            max_horizontal_gap = max(max_horizontal_gap, gap)

        max_horizontal_gap = max(
            max_horizontal_gap,
            h - horizontalCuts[-1]
        )

        max_vertical_gap = verticalCuts[0]

        for i in range(1, len(verticalCuts)):
            gap = verticalCuts[i] - verticalCuts[i - 1]
            max_vertical_gap = max(max_vertical_gap, gap)

        max_vertical_gap = max(
            max_vertical_gap,
            w - verticalCuts[-1]
        )

        return (max_horizontal_gap * max_vertical_gap) % MOD

The implementation begins by sorting both cut arrays. Sorting is necessary because the largest gap can only be identified correctly when cuts are processed in order.

The code then computes the largest horizontal interval. It first considers the distance from the top edge to the first cut. After that, it checks all consecutive gaps between cuts. Finally, it checks the distance from the last cut to the bottom edge.

The same logic is repeated for vertical cuts.

Once both maximum gaps are known, the algorithm multiplies them together to obtain the largest area. The modulo operation is applied at the end to satisfy the problem requirement.

Go Solution

package main

import "sort"

func maxArea(h int, w int, horizontalCuts []int, verticalCuts []int) int {
	const MOD int64 = 1_000_000_007

	sort.Ints(horizontalCuts)
	sort.Ints(verticalCuts)

	maxHorizontalGap := horizontalCuts[0]

	for i := 1; i < len(horizontalCuts); i++ {
		gap := horizontalCuts[i] - horizontalCuts[i-1]
		if gap > maxHorizontalGap {
			maxHorizontalGap = gap
		}
	}

	if h-horizontalCuts[len(horizontalCuts)-1] > maxHorizontalGap {
		maxHorizontalGap = h - horizontalCuts[len(horizontalCuts)-1]
	}

	maxVerticalGap := verticalCuts[0]

	for i := 1; i < len(verticalCuts); i++ {
		gap := verticalCuts[i] - verticalCuts[i-1]
		if gap > maxVerticalGap {
			maxVerticalGap = gap
		}
	}

	if w-verticalCuts[len(verticalCuts)-1] > maxVerticalGap {
		maxVerticalGap = w - verticalCuts[len(verticalCuts)-1]
	}

	area := (int64(maxHorizontalGap) * int64(maxVerticalGap)) % MOD

	return int(area)
}

The Go implementation follows the same algorithmic structure as the Python solution.

The main difference is integer overflow handling. Since the product of two gaps can exceed the range of a 32-bit integer, the multiplication is performed using int64.

Go also requires explicit sorting using sort.Ints.

Worked Examples

Example 1

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

Step 1: Sort the cuts

Type Sorted Cuts
Horizontal [1, 2, 4]
Vertical [1, 3]

Step 2: Compute horizontal gaps

Previous Boundary Current Boundary Gap
0 1 1
1 2 1
2 4 2
4 5 1

Maximum horizontal gap = 2

Step 3: Compute vertical gaps

Previous Boundary Current Boundary Gap
0 1 1
1 3 2
3 4 1

Maximum vertical gap = 2

Step 4: Compute area

2 * 2 = 4

Final answer:

4

Example 2

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

Step 1: Sort the cuts

Type Sorted Cuts
Horizontal [1, 3]
Vertical [1]

Step 2: Compute horizontal gaps

Previous Boundary Current Boundary Gap
0 1 1
1 3 2
3 5 2

Maximum horizontal gap = 2

Step 3: Compute vertical gaps

Previous Boundary Current Boundary Gap
0 1 1
1 4 3

Maximum vertical gap = 3

Step 4: Compute area

2 * 3 = 6

Final answer:

6

Example 3

h = 5
w = 4
horizontalCuts = [3]
verticalCuts = [3]

Step 1: Horizontal gaps

Previous Boundary Current Boundary Gap
0 3 3
3 5 2

Maximum horizontal gap = 3

Step 2: Vertical gaps

Previous Boundary Current Boundary Gap
0 3 3
3 4 1

Maximum vertical gap = 3

Step 3: Compute area

3 * 3 = 9

Final answer:

9

Complexity Analysis

Measure Complexity Explanation
Time O(m log m + n log n) Sorting dominates the runtime
Space O(1) or O(log n) Depends on the sorting implementation

The dominant cost comes from sorting the cut arrays. After sorting, we only perform linear scans to compute the maximum gaps.

The algorithm does not construct all cake pieces, which is what makes it efficient enough for the problem constraints.

Test Cases

from typing import List

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        MOD = 10**9 + 7

        horizontalCuts.sort()
        verticalCuts.sort()

        max_horizontal_gap = horizontalCuts[0]

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

        max_horizontal_gap = max(
            max_horizontal_gap,
            h - horizontalCuts[-1]
        )

        max_vertical_gap = verticalCuts[0]

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

        max_vertical_gap = max(
            max_vertical_gap,
            w - verticalCuts[-1]
        )

        return (max_horizontal_gap * max_vertical_gap) % MOD

sol = Solution()

assert sol.maxArea(5, 4, [1, 2, 4], [1, 3]) == 4
# Basic example from problem statement

assert sol.maxArea(5, 4, [3, 1], [1]) == 6
# Unsorted cuts

assert sol.maxArea(5, 4, [3], [3]) == 9
# Single cut in each direction

assert sol.maxArea(1000000000, 1000000000, [2], [2]) == 81
# Large dimensions with modulo handling

assert sol.maxArea(8, 10, [1, 7], [2, 9]) == 42
# Largest gaps occur near boundaries

assert sol.maxArea(6, 6, [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]) == 1
# Every piece has area 1

assert sol.maxArea(9, 8, [5], [3]) == 20
# Large center piece

assert sol.maxArea(7, 7, [1, 6], [1, 6]) == 25
# Largest piece in the middle

Test Case Summary

Test Why
(5,4,[1,2,4],[1,3]) Basic example
(5,4,[3,1],[1]) Ensures sorting is handled
(5,4,[3],[3]) Minimal number of cuts
Large dimensions Verifies modulo and overflow safety
Boundary-heavy cuts Ensures edge gaps are considered
Dense cuts Tests smallest possible segments
Single central cuts Verifies interior maximum piece
Symmetric cuts Tests middle-region maximum

Edge Cases

One important edge case occurs when the largest segment lies against the boundary of the cake rather than between two cuts. For example, if the first horizontal cut is very far from the top edge, the maximum gap may be horizontalCuts[0]. A buggy implementation that only checks consecutive cuts would miss this. The solution explicitly checks both outer boundaries.

Another important case is unsorted input. The problem does not guarantee that cuts are provided in sorted order. If we compute gaps without sorting first, we may get negative distances or incorrect maximums. The implementation sorts both arrays before any calculations.

A third important edge case involves integer overflow. The cake dimensions can reach 10^9, so the area may approach 10^18. This exceeds 32-bit integer limits. The Go solution uses int64 during multiplication, and the Python solution naturally handles large integers safely.

A final subtle edge case occurs when there is only one cut in a direction. In that scenario, there are only two segments, one on each side of the cut. The implementation correctly handles this because it separately checks the distance to both boundaries.