Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
MedPrompt
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 theithhorizontal cut and similarly, andverticalCuts[j]is the distance from the left of the rectangular cake to thejthvertical 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 large 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.Example 3:
Input: h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
Output: 9
Constraints:
2 <= h, w <= 1091 <= horizontalCuts.length <= min(h - 1, 105)1 <= verticalCuts.length <= min(w - 1, 105)1 <= horizontalCuts[i] < h1 <= verticalCuts[i] < w- All the elements in
horizontalCutsare distinct. - All the elements in
verticalCutsare distinct.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach calculates the maximum gap between horizontal and vertical cuts without sorting the cut arrays first. It iterates through all possible pairs of cuts to find adjacent ones, which is inefficient.
Algorithm
- To find the maximum horizontal gap (
max_height):- Create a list
h_boundariescontaining0,h, and all elements fromhorizontalCuts. - Initialize
max_height = 0. - For each boundary
b1inh_boundaries:- Find the smallest boundary
b2inh_boundariesthat is greater thanb1. - If such a
b2exists, the gap isb2 - b1. Updatemax_height = max(max_height, b2 - b1).
- Find the smallest boundary
- Create a list
- Repeat the same process for
verticalCutsand the cake widthwto find the maximum vertical gap (max_width). - The final result is
(long)max_height * (long)max_width % (10^9 + 7).
Walkthrough
The core idea is that the maximum area is the product of the maximum horizontal gap and the maximum vertical gap. This approach finds these maximum gaps in a naive way. Instead of sorting the cuts to easily find adjacent ones, it iterates through all cuts to find the 'next' cut for each given cut. For the horizontal cuts, we first augment the array with the cake boundaries, 0 and h. Then, for each boundary b1 in this augmented list, we perform a full scan of the list to find the boundary b2 that is closest to b1 but still larger than b1. The difference b2 - b1 represents the height of a piece. We keep track of the maximum such height found across all b1. The same process is repeated for vertical cuts and boundaries to find the maximum width. This quadratic search for adjacent gaps is highly inefficient.
import java.util.ArrayList;import java.util.List; class Solution { public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) { long MOD = 1_000_000_007; // Create a list of all horizontal boundaries List<Integer> hBoundaries = new ArrayList<>(); hBoundaries.add(0); hBoundaries.add(h); for (int cut : horizontalCuts) { hBoundaries.add(cut); } // Find max horizontal gap by finding the next closest cut for each cut long maxH = 0; for (int b1 : hBoundaries) { long minDiff = Long.MAX_VALUE; for (int b2 : hBoundaries) { if (b2 > b1) { minDiff = Math.min(minDiff, b2 - b1); } } if (minDiff != Long.MAX_VALUE) { maxH = Math.max(maxH, minDiff); } } // Create a list of all vertical boundaries List<Integer> vBoundaries = new ArrayList<>(); vBoundaries.add(0); vBoundaries.add(w); for (int cut : verticalCuts) { vBoundaries.add(cut); } // Find max vertical gap similarly long maxW = 0; for (int b1 : vBoundaries) { long minDiff = Long.MAX_VALUE; for (int b2 : vBoundaries) { if (b2 > b1) { minDiff = Math.min(minDiff, b2 - b1); } } if (minDiff != Long.MAX_VALUE) { maxW = Math.max(maxW, minDiff); } } return (int) ((maxH * maxW) % MOD); }}Complexity
Time
O(m^2 + n^2), where `m` is the length of `horizontalCuts` and `n` is the length of `verticalCuts`. For each of the `m+2` horizontal boundaries, we iterate through all `m+2` boundaries to find the next one, leading to `O(m^2)` complexity. Similarly, it's `O(n^2)` for vertical cuts.
Space
O(m + n), where `m` is the number of horizontal cuts and `n` is the number of vertical cuts. This space is used to create new lists to hold all boundaries.
Trade-offs
Pros
Conceptually simple, as it directly implements the idea of finding the next adjacent cut through exhaustive search.
Cons
Highly inefficient due to the quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode for larger inputs.
Solutions
Solution
class Solution {public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) { final int mod = (int)1 e9 + 7; Arrays.sort(horizontalCuts); Arrays.sort(verticalCuts); int m = horizontalCuts.length; int n = verticalCuts.length; long x = Math.max(horizontalCuts[0], h - horizontalCuts[m - 1]); long y = Math.max(verticalCuts[0], w - verticalCuts[n - 1]); for (int i = 1; i < m; ++i) { x = Math.max(x, horizontalCuts[i] - horizontalCuts[i - 1]); } for (int i = 1; i < n; ++i) { y = Math.max(y, verticalCuts[i] - verticalCuts[i - 1]); } return (int)((x * y) % mod); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.