Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

Med

#1353Time: 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.2 companies

Patterns

Algorithms

Data structures

Companies

Prompt

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 i^th horizontal cut and similarly, and
verticalCuts[j] is the distance from the left of the rectangular cake to the j^th 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 10⁹ + 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 <= 10⁹
1 <= horizontalCuts.length <= min(h - 1, 10⁵)
1 <= verticalCuts.length <= min(w - 1, 10⁵)
1 <= horizontalCuts[i] < h
1 <= verticalCuts[i] < w
All the elements in horizontalCuts are distinct.
All the elements in verticalCuts are 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_boundaries containing 0, h, and all elements from horizontalCuts.
- Initialize max_height = 0.
- For each boundary b1 in h_boundaries:
  - Find the smallest boundary b2 in h_boundaries that is greater than b1.
  - If such a b2 exists, the gap is b2 - b1. Update max_height = max(max_height, b2 - b1).
Repeat the same process for verticalCuts and the cake width w to 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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {6        long MOD = 1_000_000_007;7 8        // Create a list of all horizontal boundaries9        List<Integer> hBoundaries = new ArrayList<>();10        hBoundaries.add(0);11        hBoundaries.add(h);12        for (int cut : horizontalCuts) {13            hBoundaries.add(cut);14        }15 16        // Find max horizontal gap by finding the next closest cut for each cut17        long maxH = 0;18        for (int b1 : hBoundaries) {19            long minDiff = Long.MAX_VALUE;20            for (int b2 : hBoundaries) {21                if (b2 > b1) {22                    minDiff = Math.min(minDiff, b2 - b1);23                }24            }25            if (minDiff != Long.MAX_VALUE) {26                maxH = Math.max(maxH, minDiff);27            }28        }29 30        // Create a list of all vertical boundaries31        List<Integer> vBoundaries = new ArrayList<>();32        vBoundaries.add(0);33        vBoundaries.add(w);34        for (int cut : verticalCuts) {35            vBoundaries.add(cut);36        }37 38        // Find max vertical gap similarly39        long maxW = 0;40        for (int b1 : vBoundaries) {41            long minDiff = Long.MAX_VALUE;42            for (int b2 : vBoundaries) {43                if (b2 > b1) {44                    minDiff = Math.min(minDiff, b2 - b1);45                }46            }47            if (minDiff != Long.MAX_VALUE) {48                maxW = Math.max(maxW, minDiff);49            }50        }51 52        return (int) ((maxH * maxW) % MOD);53    }54}

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.

This approach correctly identifies that the maximum area is the product of the maximum gap between horizontal cuts and the maximum gap between vertical cuts. It efficiently finds these maximum gaps by first sorting the cut positions.

Algorithm

Sort the horizontalCuts array.
Find the maximum horizontal gap (max_height). This is the maximum of:
- The first cut's distance from the top edge: horizontalCuts[0] - 0.
- The distance between any two adjacent cuts: horizontalCuts[i] - horizontalCuts[i-1].
- The last cut's distance from the bottom edge: h - horizontalCuts[m-1].
Sort the verticalCuts array.
Find the maximum vertical gap (max_width) using the same logic with verticalCuts and width w.
Calculate the result: (long)max_height * (long)max_width % (10^9 + 7). Use long for multiplication to prevent overflow.

Walkthrough

The key insight is that the maximum area of a piece of cake is determined by the product of the largest gap between horizontal cuts and the largest gap between vertical cuts. These two calculations are independent. To find the largest horizontal gap, we need to consider all the horizontal lines: the top edge of the cake (at position 0), the bottom edge (at position h), and all the given horizontal cuts. The gaps are the distances between consecutive horizontal lines. The most efficient way to find these gaps is to first sort the horizontalCuts array. After sorting, we can iterate through the array once to find the maximum difference between adjacent elements. We must also account for the gap between the top edge and the first cut, and the gap between the last cut and the bottom edge. A similar procedure is applied to the verticalCuts to find the maximum width. Finally, we multiply these two maximum values (taking care of potential integer overflow by using a long) and take the result modulo 10^9 + 7.

1import java.util.Arrays;2 3class Solution {4    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {5        long MOD = 1_000_000_007;6 7        // Sort the cuts to easily find adjacent gaps8        Arrays.sort(horizontalCuts);9        Arrays.sort(verticalCuts);10 11        // Calculate maximum horizontal gap12        // Start with the gap from the top edge (0) to the first cut13        long maxH = horizontalCuts[0];14        for (int i = 1; i < horizontalCuts.length; i++) {15            maxH = Math.max(maxH, horizontalCuts[i] - horizontalCuts[i-1]);16        }17        // Consider the gap from the last cut to the bottom edge (h)18        maxH = Math.max(maxH, h - horizontalCuts[horizontalCuts.length - 1]);19 20        // Calculate maximum vertical gap21        // Start with the gap from the left edge (0) to the first cut22        long maxW = verticalCuts[0];23        for (int i = 1; i < verticalCuts.length; i++) {24            maxW = Math.max(maxW, verticalCuts[i] - verticalCuts[i-1]);25        }26        // Consider the gap from the last cut to the right edge (w)27        maxW = Math.max(maxW, w - verticalCuts[verticalCuts.length - 1]);28 29        // Calculate the max area and return modulo30        // Cast to long before multiplication to prevent overflow31        return (int) ((maxH * maxW) % MOD);32    }33}

Complexity

Time

O(m log m + n log n), where `m` is the length of `horizontalCuts` and `n` is the length of `verticalCuts`. The complexity is dominated by the sorting operations. The subsequent linear scans to find the max gap take O(m) and O(n) time.

Space

O(log m + log n) or O(m + n). This depends on the space complexity of the sorting algorithm used. In Java, `Arrays.sort` for primitive types is an in-place quicksort that takes O(log N) space on average.

Trade-offs

Pros

Highly efficient and optimal for the given constraints.
The logic is clean and directly solves the problem by breaking it down into two independent subproblems.

Cons

The logic might be slightly less intuitive for a beginner compared to a pure brute-force approach.

Solutions

Solution

1class Solution {2public3  int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {4    final int mod = (int)1 e9 + 7;5    Arrays.sort(horizontalCuts);6    Arrays.sort(verticalCuts);7    int m = horizontalCuts.length;8    int n = verticalCuts.length;9    long x = Math.max(horizontalCuts[0], h - horizontalCuts[m - 1]);10    long y = Math.max(verticalCuts[0], w - verticalCuts[n - 1]);11    for (int i = 1; i < m; ++i) {12      x = Math.max(x, horizontalCuts[i] - horizontalCuts[i - 1]);13    }14    for (int i = 1; i < n; ++i) {15      y = Math.max(y, verticalCuts[i] - verticalCuts[i - 1]);16    }17    return (int)((x * y) % mod);18  }19}

1class Solution {2public:3  int maxArea(int h, int w, vector<int> &horizontalCuts,4              vector<int> &verticalCuts) {5    horizontalCuts.push_back(0);6    horizontalCuts.push_back(h);7    verticalCuts.push_back(0);8    verticalCuts.push_back(w);9    sort(horizontalCuts.begin(), horizontalCuts.end());10    sort(verticalCuts.begin(), verticalCuts.end());11    int x = 0, y = 0;12    for (int i = 1; i < horizontalCuts.size(); ++i) {13      x = max(x, horizontalCuts[i] - horizontalCuts[i - 1]);14    }15    for (int i = 1; i < verticalCuts.size(); ++i) {16      y = max(y, verticalCuts[i] - verticalCuts[i - 1]);17    }18    const int mod = 1e9 + 7;19    return (1ll * x * y) % mod;20  }21};

1class Solution:2    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int: horizontalCuts . extend([0, h]) verticalCuts . extend([0, w]) horizontalCuts . sort() verticalCuts . sort() x = max(b - a for a, b in pairwise(horizontalCuts)) y = max(b - a for a, b in pairwise(verticalCuts)) return (x * y) % (10 ** 9 + 7)

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.

← Previous

Previous problem

Next problem