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.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. Since the answer can be a large number, return it modulo 109 + 7.
Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4
Explanation: The figure represents the given rectangular cake. Red lines are the cuts. The green piece has the maximum area of 4.
Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
Output: 6
Explanation: The figure represents the given rectangular cake. Red lines are the cuts. The green and yellow pieces have the maximum area of 6.
Input: h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
Output: 9
Explanation: The figure represents the given rectangular cake. Red lines are the cuts. The largest piece has an area of 9.
horizontalCuts are distinct.verticalCuts are distinct.The maximum piece area is determined by the largest horizontal gap between consecutive cuts (including cake edges) and the largest vertical gap. Sorting the cut positions and computing max consecutive differences yields these gaps. Their product gives the maximum area.
horizontalCuts, then sort. Similarly, add (0 and w) to verticalCuts and sort.horizontalCuts to find the maximum difference between adjacent values — this is the largest horizontal segment height (maxH).verticalCuts to find the maximum difference between adjacent values — this is the largest vertical segment width (maxW).(maxH * maxW) % (109 + 7) and return the result.#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
long long maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
horizontalCuts.push_back(0);
horizontalCuts.push_back(h);
sort(horizontalCuts.begin(), horizontalCuts.end());
long long maxH = 0;
for (int i = 1; i < horizontalCuts.size(); i++) {
maxH = max(maxH, (long long)horizontalCuts[i] - horizontalCuts[i-1]);
}
verticalCuts.push_back(0);
verticalCuts.push_back(w);
sort(verticalCuts.begin(), verticalCuts.end());
long long maxW = 0;
for (int i = 1; i < verticalCuts.size(); i++) {
maxW = max(maxW, (long long)verticalCuts[i] - verticalCuts[i-1]);
}
long long mod = 1000000007;
return (maxH * maxW) % mod;
}
};import java.util.*;
class Solution {
public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
List<Integer> hList = new ArrayList<>();
for (int cut : horizontalCuts) {
hList.add(cut);
}
hList.add(0);
hList.add(h);
Collections.sort(hList);
long maxH = 0;
for (int i = 1; i < hList.size(); i++) {
maxH = Math.max(maxH, (long)hList.get(i) - hList.get(i-1));
}
List<Integer> vList = new ArrayList<>();
for (int cut : verticalCuts) {
vList.add(cut);
}
vList.add(0);
vList.add(w);
Collections.sort(vList);
long maxW = 0;
for (int i = 1; i < vList.size(); i++) {
maxW = Math.max(maxW, (long)vList.get(i) - vList.get(i-1));
}
long mod = 1000000007;
return (int)((maxH * maxW) % mod);
}
}class Solution:
def maxArea(self, h, w, horizontalCuts, verticalCuts):
horizontalCuts.extend([0, h])
horizontalCuts.sort()
maxH = 0
for i in range(1, len(horizontalCuts)):
maxH = max(maxH, horizontalCuts[i] - horizontalCuts[i-1])
verticalCuts.extend([0, w])
verticalCuts.sort()
maxW = 0
for i in range(1, len(verticalCuts)):
maxW = max(maxW, verticalCuts[i] - verticalCuts[i-1])
return (maxH * maxW) % (10**9 + 7)class Solution {
maxArea(h, w, horizontalCuts, verticalCuts) {
horizontalCuts.push(0, h);
horizontalCuts.sort((a, b) => a - b);
let maxH = 0;
for (let i = 1; i < horizontalCuts.length; i++) {
maxH = Math.max(maxH, horizontalCuts[i] - horizontalCuts[i-1]);
}
verticalCuts.push(0, w);
verticalCuts.sort((a, b) => a - b);
let maxW = 0;
for (let i = 1; i < verticalCuts.length; i++) {
maxW = Math.max(maxW, verticalCuts[i] - verticalCuts[i-1]);
}
const mod = 1000000007n;
return Number((BigInt(maxH) * BigInt(maxW)) % mod);
}
}Time Complexity: O(n log n + m log m), where n = horizontalCuts.length and m = verticalCuts.length. Sorting both arrays dominates the runtime, followed by linear scans.
Space Complexity: O(n + m) for storing the modified cut arrays (including edges). Sorting may use additional space depending on the language's implementation.
Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.