# Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts (Leetcode 1465)

Difficulty: Medium Link: Day3: June Leetcode Challenge 2021

## Problem Statement

Given a rectangular cake with height `h` and width `w`, and two arrays of integers `horizontalCuts` and `verticalCuts` where `horizontalCuts[i]` is the distance from the top of the rectangular cake to the `ith` horizontal cut and similarly, `verticalCuts[j]` is the distance from the left of the rectangular cake to the `jth` 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 huge number, return this modulo 10^9 + 7.

### Examples

``````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.
``````
``````Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = 
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.
``````
``````Input: h = 5, w = 4, horizontalCuts = , verticalCuts = 
Output: 9
``````

### Constraints

• `2 <= h, w <= 10^9`
• `1 <= horizontalCuts.length < min(h, 10^5)`
• `1 <= verticalCuts.length < min(w, 10^5)`
• `1 <= horizontalCuts[i] < h`
• `1 <= verticalCuts[i] < w`
• It is guaranteed that all elements in `horizontalCuts` are distinct.
• It is guaranteed that all elements in `verticalCuts` are distinct.

# Solution

### Intuition

We are try to find out every possible rectangle and find the rectangle with maximum area, but that would be very expensive for large values of h, w. If we think in terms of maximising the area, we can observe that the problem is indeed simple and we need to find the maximum gaps between the horizontal and vertical lines to form our area.

The key insight to the problem is that not all cuts (horizontal or vertical) matters. If we think about area then it is width * height and for area to be maximum, width and height should be maximum. While iterating lets say, on the horizontal cuts, the distance between two adjacent cuts would make up a rectangle with height horizontalCuts[i]- horizontalCuts[i-1]. We can find all gaps and maintain the max value (maxHeight). Similarly, iterating through the vertical cuts would help us find the maxWidth.

Also keep in mind the edge case for considering the border values for width and height. The initial width would form between 0 and verticalCuts while the extreme last width would be w – verticalCuts[n-1]. Similarly, for initial and last height which we can solve by initialising the maxHeight = max(horizontalCuts, w – horizontalCuts[n-1]) and maxWidth = max(verticalCuts, h – verticalCuts[n-1]).

### Algorithm

1. Sort both the horizontal and vertical cuts array.
2. Initialise a variable for maxWidth and iterate through the vertical cuts and find the maxWidth by maxWidth = max(maxWidth, verticalCuts[i] – verticalCuts[i-1]).
3. Repeat the step 2 for finding the maxHeight from horizontal cuts.
4. 4. Our maximum area is ( `maxHeight * maxWidth` ) % 10^9 + 7

#### Note

Also, since area can be huge, so do not forget to return your answer after modulo with 10^9 + 7 (I missed reading the last statement and wasted 10 minutes to figure out why the solution is not working for large h, w values :/ ).

## Complexity Analysis

We are sorting our horizontal cuts and vertical cuts which is a O(NLogN) operation. If we consider M as the length of horizontal cuts and N as the length of vertical cuts, then total complexity would be bounded by O(MLogM) + O(NLogN). After that we are just iterating them, which is economical than the sorting operation so we can ignore that. For space, we are just keeping two variable so it’s a constant space solution.

Time = O(MLogM) + O(NLogN) // M = Length of first array, N = Length of second array

Space = O(1)