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

MEDIUM

Description

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

Checkout 2 different approaches to solve Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts. Click on different approaches to view the approach and algorithm in detail.

Brute-force Calculation of Gaps

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).

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 Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

Algorithms:

Sorting

Patterns:

Greedy

Data Structures:

Array

Companies:

BNY Mellon |IXL |