.

Examples

Example 1

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4 
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green piece of cake has the maximum area.

Example 2

Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
Output: 6
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green and yellow pieces of cake have the maximum area.

Example 3

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

Constraints

All the elements in horizontalCuts are distinct.
All the elements in verticalCuts are distinct.

Solution

Method 1 - Sorting and Gap Calculation

Intuition

We want the largest rectangular piece formed by the cuts. The height of any piece is a gap between two consecutive horizontal cut positions (including edges 0 and h). Similarly, the width is a gap between two consecutive vertical cuts (including edges 0 and w). The maximum area is simply maxHeightGap * maxWidthGap. Sorting lets us compute these gaps in one linear scan per list.

Approach

Related Tags