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 and similarly, andverticalCuts[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 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] < whorizontalCuts are distinct.verticalCuts are distinct.This approach involves sorting the cut arrays and finding the maximum gaps between consecutive cuts, including the edges of the cake. Once the maximum horizontal and vertical gaps are identified, the maximum possible area of a piece of cake can be obtained by multiplying these two maximum gaps.
The function begins by sorting the horizontal and vertical cuts. It then calculates the maximum gap between each pair of consecutive cuts along with the initial and final edge to get the maximum possible length or width. This ensures we consider the pieces that extend to the end of the cake as well. The maximum area is found by multiplying these maximum gaps and returning the result modulo 10^9 + 7.
C++
Java
C
C#
JavaScript
Time Complexity: O(n log n + m log m), where n and m are the sizes of the horizontalCuts and verticalCuts arrays, due to sorting.
Space Complexity: O(1) additional space is used, as computations are done in-place.
This approach uses dynamic programming to store previously calculated results for maximum gaps between cuts, optimizing repeated calculations by using memoization. This is particularly useful when recalculating maximum differences thousands of times for larger input sizes.
The Python DP solution stores results of maximum gap calculations in a dictionary (memo) to avoid repeated computation. It defines a helper function getMaxGap() for finding the largest segment gap using the memoization pattern. This stores every result fetched per list, speeding up subsequent gap queries.
JavaScript
Time Complexity: O(n log n + m log m) for sorting; O(n + m) in constant time queries after sorting using memo.
Space Complexity: O(n + m) for memoization storage.
| Approach | Complexity |
|---|---|
| Sort and Find Maximum Gaps | Time Complexity: O(n log n + m log m), where n and m are the sizes of the horizontalCuts and verticalCuts arrays, due to sorting. |
| Dynamic Programming Approach (Memoization) | Time Complexity: O(n log n + m log m) for sorting; O(n + m) in constant time queries after sorting using memo. |
Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts | Leetcode 1465 | Live coding • Coding Decoded • 6,533 views views
Watch 9 more video solutions →Practice Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts with our built-in code editor and test cases.
Practice on FleetCode