Problem:

You are given a rectangular cake of size h x 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, and

• 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 109 + 7.

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.

Approach:

We need to find the maximum area of a piece of cake that we can get after cutting it at the positions mentioned in the horizontalCuts and verticalCuts arrays.

First, we can sort both the arrays in ascending order. This will give us the positions at which we will cut the cake.

Now, we need to find the maximum distance between consecutive elements in both the arrays.

For example, if we have horizontalCuts as [1,2,4], then the maximum distance between two consecutive elements will be max(horizontalCuts[i+1]-horizontalCuts[i]) for i=0 to i=n-2, where n is the length of the horizontalCuts array.

Similarly, if we have verticalCuts as [1,3], then the maximum distance between two consecutive elements will be max(verticalCuts[j+1]-verticalCuts[j]) for j=0 to j=m-2, where m is the length of the verticalCuts array.

Once we have these maximum distances, we can find the maximum area of the cake by multiplying these maximum distances.

The final answer will be the maximum area modulo 109 + 7.

Solution:

def maxArea(h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:

# Sort the horizontal and vertical cuts
horizontalCuts.sort()
verticalCuts.sort()

# Find the maximum distance between two consecutive horizontal cuts
maxHorDist = max([horizontalCuts[i+1] - horizontalCuts[i]
                  for i in range(len(horizontalCuts)-1)] + [horizontalCuts[0], h-horizontalCuts[-1]])

# Find the maximum distance between two consecutive vertical cuts
maxVerDist = max([verticalCuts[j+1] - verticalCuts[j]
                  for j in range(len(verticalCuts)-1)] + [verticalCuts[0], w-verticalCuts[-1]])

# Calculate the maximum area of the cake
maxArea = (maxVerDist * maxHorDist) % ((10**9) + 7)

return maxArea

Test the solution

print(maxArea(5, 4, [1,2,4], [1,3])) print(maxArea(5, 4, [3,1], [1]))

Output:

4

6

Time Complexity: O(NlogN), where N is the length of the horizontalCuts or verticalCuts array as we are sorting the arrays.

Space Complexity: O(1), constant space is used.

1