Code Implementation

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        MOD = 10**9 + 7
        horizontalCuts.sort()
        verticalCuts.sort()
        # Include the edges
        maxH = max(horizontalCuts[0], h - horizontalCuts[-1])
        for i in range(1, len(horizontalCuts)):
            maxH = max(maxH, horizontalCuts[i] - horizontalCuts[i-1])
        maxV = max(verticalCuts[0], w - verticalCuts[-1])
        for i in range(1, len(verticalCuts)):
            maxV = max(maxV, verticalCuts[i] - verticalCuts[i-1])
        return (maxH * maxV) % MOD
    

class Solution {
public:
    int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
        int MOD = 1e9 + 7;
        sort(horizontalCuts.begin(), horizontalCuts.end());
        sort(verticalCuts.begin(), verticalCuts.end());
        long maxH = max(horizontalCuts[0], h - horizontalCuts.back());
        for (int i = 1; i < horizontalCuts.size(); ++i) {
            maxH = max(maxH, (long)horizontalCuts[i] - horizontalCuts[i-1]);
        }
        long maxV = max(verticalCuts[0], w - verticalCuts.back());
        for (int i = 1; i < verticalCuts.size(); ++i) {
            maxV = max(maxV, (long)verticalCuts[i] - verticalCuts[i-1]);
        }
        return (int)((maxH * maxV) % MOD);
    }
};
    

class Solution {
    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        int MOD = 1_000_000_007;
        Arrays.sort(horizontalCuts);
        Arrays.sort(verticalCuts);
        long maxH = Math.max(horizontalCuts[0], h - horizontalCuts[horizontalCuts.length - 1]);
        for (int i = 1; i < horizontalCuts.length; ++i) {
            maxH = Math.max(maxH, horizontalCuts[i] - horizontalCuts[i-1]);
        }
        long maxV = Math.max(verticalCuts[0], w - verticalCuts[verticalCuts.length - 1]);
        for (int i = 1; i < verticalCuts.length; ++i) {
            maxV = Math.max(maxV, verticalCuts[i] - verticalCuts[i-1]);
        }
        return (int)((maxH * maxV) % MOD);
    }
}
    

var maxArea = function(h, w, horizontalCuts, verticalCuts) {
    const MOD = 1e9 + 7;
    horizontalCuts.sort((a,b) => a-b);
    verticalCuts.sort((a,b) => a-b);
    let maxH = Math.max(horizontalCuts[0], h - horizontalCuts[horizontalCuts.length - 1]);
    for (let i = 1; i < horizontalCuts.length; ++i) {
        maxH = Math.max(maxH, horizontalCuts[i] - horizontalCuts[i-1]);
    }
    let maxV = Math.max(verticalCuts[0], w - verticalCuts[verticalCuts.length - 1]);
    for (let i = 1; i < verticalCuts.length; ++i) {
        maxV = Math.max(maxV, verticalCuts[i] - verticalCuts[i-1]);
    }
    return (BigInt(maxH) * BigInt(maxV) % BigInt(MOD));
};
    

Problem Description

You are given a rectangular cake of size h x w. There are arrays horizontalCuts and verticalCuts representing the distances from the top and left edges of the cake where horizontal and vertical cuts are made, respectively. Your task is to find the area of the largest piece of cake that can be obtained after performing all the cuts. The answer should be returned modulo 10⁹ + 7.

• Each cut is a straight line, parallel to one of the sides, and all cuts happen at once.
• All cut positions are distinct and within the cake (not on the edges).
• You must not reuse or move any cut.
• There is always at least one valid solution.

Inputs:

• h: integer, height of the cake
• w: integer, width of the cake
• horizontalCuts: list of integers
• verticalCuts: list of integers

Thought Process

At first glance, the problem seems to require checking all possible cake pieces after every cut and calculating their areas. But with potentially many cuts, this brute-force approach would be inefficient. Instead, we can look for a pattern: after all cuts are made, the largest possible piece will always be a rectangle whose sides are determined by the largest gaps between consecutive horizontal and vertical cuts.

This insight shifts our focus from tracking all pieces to simply finding the largest "gap" in both dimensions. The largest piece's area will be the product of the largest horizontal gap and the largest vertical gap.

Solution Approach

• Step 1: Sort the Cuts
  • Sort both horizontalCuts and verticalCuts arrays in ascending order. This makes it easy to compute the distances between consecutive cuts.
• Step 2: Find the Maximum Gap
  • For horizontal cuts, the largest possible piece's height is the maximum difference between two consecutive cuts, as well as the distance from the top edge to the first cut and from the last cut to the bottom edge.
  • Similarly, for vertical cuts, the largest piece's width is the maximum difference between consecutive vertical cuts, plus the edges.
• Step 3: Calculate the Area
  • The area of the largest piece is the product of the largest height gap and the largest width gap.
  • Return the area modulo 10⁹ + 7 to prevent overflow.

This approach is efficient, as it only requires sorting and a single pass through each cuts array.

Example Walkthrough

Example Input:

• h = 5, w = 4
• horizontalCuts = [1,2,4]
• verticalCuts = [1,3]

1. Sort the cuts:
   • horizontalCuts = [1,2,4]
   • verticalCuts = [1,3]
2. Compute horizontal gaps:
   • From top to first cut: 1
   • Between 1 and 2: 1
   • Between 2 and 4: 2
   • From last cut to bottom: 5 - 4 = 1
   • Max horizontal gap: 2
3. Compute vertical gaps:
   • From left to first cut: 1
   • Between 1 and 3: 2
   • From last cut to right: 4 - 3 = 1
   • Max vertical gap: 2
4. Area = 2 * 2 = 4

Output: 4

Time and Space Complexity

• Brute-force Approach:
  • Would involve generating all possible rectangles from the cuts and checking their areas, leading to exponential time and space complexity.
• Optimized Approach (as above):
  • Sorting each cuts array: O(N log N) where N is the number of cuts.
  • Single pass to find maximum gaps: O(N).
  • Total Time Complexity: O(N log N) for sorting.
  • Space Complexity: O(1) extra space (if sorting in place), otherwise O(N) if copying arrays.

Summary

The problem reduces to finding the largest rectangle that can be formed after all cuts. By sorting the cuts and looking for the largest consecutive gaps in both directions, we can efficiently compute the answer. This solution is elegant because it avoids brute-force enumeration and leverages properties of sorted arrays and simple arithmetic, making it both fast and easy to implement.