Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

Problem Statement

You are provided with the dimensions of a rectangular cake, specifically its height h and width w. Additionally, two lists of integer values, horizontalCuts and verticalCuts, are given. Each value in horizontalCuts represents the measured distance from the top edge of the cake to where a horizontal cut is made. Similarly, each value in verticalCuts signifies the distance from the left edge of the cake to where a vertical cut is made.

Your task is to determine the maximum possible area of any single piece of cake that results from making all these cuts. Because these areas can potentially be very large, return the result modulo 10^9 + 7.

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

• 2 <= h, w <= 109
• 1 <= horizontalCuts.length <= min(h - 1, 105)
• 1 <= verticalCuts.length <= min(w - 1, 105)
• 1 <= horizontalCuts[i] < h
• 1 <= verticalCuts[i] < w
• All the elements in horizontalCuts are distinct.
• All the elements in verticalCuts are distinct.

Approach and Intuition

To find the maximum area of a piece of cake after performing the cuts as described above, one effective method involves the following steps:

1. First, sort the lists horizontalCuts and verticalCuts. This will help to order the cuts sequentially from the top of the cake to the bottom and from left to right, respectively.

2. In order to calculate the maximum possible area, you need to consider the gaps between successive cuts and between the edges of the cake and the nearest cuts. This means appending the values h to horizontalCuts and w to verticalCuts to account for the edges of the cake.

3. Calculate the maximum gap between successive horizontal cuts and between successive vertical cuts. This involves determining the difference between consecutive elements in the sorted horizontalCuts and verticalCuts, and the difference between the first cut and the edge of the cake (and similarly for the last cut). The maximum of these values would represent the height and width of the largest possible piece of cake:

   • For the width, iterate through verticalCuts after sorting and find the maximum difference between subsequent cuts or between the first cut and left edge, and the last cut and the right edge.

   • Similarly, for the height, iterate through horizontalCuts to find the maximum gaps after sorting.

4. The area of the largest piece is then the product of these maximum gaps in both the vertical and horizontal directions.

5. Finally, since the product may be a very large number, return the resulting area modulo 10^9 + 7 as required by the problem constraints.

This approach efficiently leverages sort operations and linear scans to determine the maximum piece size, ensuring that the problem can handle the upper limits of cake dimensions and cuts as constrained by the problem statement.

Solutions

class Solution {
    public int maxArea(int height, int width, int[] hCuts, int[] vCuts) {
        Arrays.sort(hCuts);
        Arrays.sort(vCuts);
        int hLength = hCuts.length;
        int vLength = vCuts.length;

        long maxH = Math.max(hCuts[0], height - hCuts[hLength - 1]);
        for (int i = 1; i < hLength; i++) {
            maxH = Math.max(maxH, hCuts[i] - hCuts[i - 1]);
        }

        long maxW = Math.max(vCuts[0], width - vCuts[vLength - 1]);
        for (int i = 1; i < vLength; i++) {
            maxW = Math.max(maxW, vCuts[i] - vCuts[i - 1]);
        }

        return (int) ((maxW * maxH) % 1000000007);
    }
}

class Solution:
    def calculateMaxArea(self, height: int, width: int, hCuts: List[int], vCuts: List[int]) -> int:
        hCuts.sort()
        vCuts.sort()

        tallest = max(hCuts[0], height - hCuts[-1])
        for j in range(1, len(hCuts)):
            tallest = max(tallest, hCuts[j] - hCuts[j - 1])

        broadest = max(vCuts[0], width - vCuts[-1])
        for j in range(1, len(vCuts)):
            broadest = max(broadest, vCuts[j] - vCuts[j - 1])

        return (tallest * broadest) % 1000000007