Day 3: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

Problem Link:

https://leetcode.com/explore/challenge/card/june-leetcoding-challenge-2021/603/week-1-june-1st-june-7th/3766/

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.

Example 1:

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

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.

My Solution:

class Solution:
    def maxArea(self, h: int, w: int, hc: List[int], vc: List[int]) -> int:
        hc.sort()
        vc.sort()
        maxh, maxv = max(hc[0], h - hc[-1]), max(vc[0], w - vc[-1])
        for i in range(len(hc)):
            maxh = max(maxh, hc[i] - hc[i-1])
        for i in range(len(vc)):
            maxv = max(maxv, vc[i] - vc[i-1])
        return (maxh * maxv) % 1000000007

Explanation:

The idea of this problem is to realize that all vertical slices cross all horizontal slices. This means that we just need to find the largest of each, and the cross-section should be the largest slice.

To find the largest slice of each, we need to first sort the horizontal cuts (hc) and vertical cuts (vc), then iterate through both and keep track of the maximum difference found between two consecutive cuts (maxh, maxv).

Note: Do not forget to include the two end cuts, which are found using 0 and h/w.

Once we have the largest difference for both, we can just return the product of these two numbers, modulo 1e9+7.

• Time Complexity: O(N * log(N) + M * log(M)) where N is the length of hc and M is the length of vc
• Space Complexity: O(1)

That’s it!

If you are interested in solving more problems, do follow me and join me on this journey.

See you tomorrow!

Cheers!