Swift Leetcode Series: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

Swift Solution for Leetcode 1465

The Swift Nerd

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

You can read the full story on The Swift Nerd blog with the link above.

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

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[0] 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[0], w — horizontalCuts[n-1]) and maxWidth = max(verticalCuts[0], h — verticalCuts[n-1]).

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).

Time = O(MLogM) + O(NLogN)

Space = O(1)

Thank you for reading. If you liked this article and found it useful, share and spread it like wildfire!

You can find me on TheSwiftNerd | LinkedIn | Github