Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
Problem
A rectangular cake of size h × w. Given horizontalCuts (y-values) and verticalCuts (x-values), return the maximum piece area after all cuts, modulo 10^9+7.
h=5, w=4, horizontalCuts=[1,2,4], verticalCuts=[1,3]4def max_area(h, w, hc, vc):
MOD = 10**9 + 7
def biggest(arr, total):
a = sorted(arr); best = a[0]; prev = a[0]
for v in a[1:]:
best = max(best, v - prev); prev = v
return max(best, total - a[-1])
return biggest(hc, h) * biggest(vc, w) % MODfunction maxArea(h, w, hc, vc) {
const MOD = 1_000_000_007n;
function biggest(arr, total) {
const a = arr.slice().sort((x, y) => x - y);
let best = a[0], prev = a[0];
for (let i = 1; i < a.length; i++) { best = Math.max(best, a[i] - prev); prev = a[i]; }
return Math.max(best, total - a[a.length - 1]);
}
return Number(BigInt(biggest(hc, h)) * BigInt(biggest(vc, w)) % MOD);
}class Solution {
public int maxArea(int h, int w, int[] hc, int[] vc) {
long MOD = 1_000_000_007L;
return (int)(((long) gap(hc, h)) * gap(vc, w) % MOD);
}
int gap(int[] a, int total) {
Arrays.sort(a);
int best = a[0], prev = a[0];
for (int i = 1; i < a.length; i++) { best = Math.max(best, a[i] - prev); prev = a[i]; }
return Math.max(best, total - a[a.length - 1]);
}
}int maxArea(int h, int w, vector& hc, vector& vc) {
long long MOD = 1000000007LL;
auto gap = [](vector& a, int total) {
sort(a.begin(), a.end());
int best = a[0], prev = a[0];
for (int i = 1; i < (int)a.size(); i++) { best = max(best, a[i] - prev); prev = a[i]; }
return max(best, total - a.back());
};
return (int)((long long) gap(hc, h) * gap(vc, w) % MOD);
} Explanation
The cake gets sliced by horizontal and vertical cuts, and the final pieces are little rectangles. The neat insight is that the biggest piece is made by the widest horizontal gap times the widest vertical gap — the two directions are completely independent.
So we solve each direction the same way with the helper biggest. We sort the cut positions, then look at the distance between each cut and the one before it to find the largest spacing.
One detail: the gaps near the edges count too. That is why we also check total - a[-1] (the strip from the last cut to the far edge), and we start best at a[0] (the strip from edge 0 to the first cut).
Example: horizontalCuts = [1,2,4] with height 5. Sorted gaps are 1, 1, 2, plus the edge piece 5 - 4 = 1, so the tallest strip is 2. Doing the same for the verticals gives 2.
Multiply the two best gaps: 2 * 2 = 4. We take that modulo 10^9+7 because the area can get huge.