# Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts)
Canonical: https://scaleengineer.com/dsa/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [BNY Mellon](https://scaleengineer.com/companies/bny-mellon), [IXL](https://scaleengineer.com/companies/ixl)
---
## Problem
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, and
* `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_ `horizontalCuts` _and_ `verticalCuts`. Since the answer can be a large number, return this **modulo** `109 + 7`.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/image0.png) 

**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:**

![](https://assets.glich.co/dsa/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/image1.png) 

**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 <= 109`
* `1 <= horizontalCuts.length <= min(h - 1, 105)`
* `1 <= verticalCuts.length <= min(w - 1, 105)`
* `1 <= horizontalCuts[i] < h`
* `1 <= verticalCuts[i] < w`
* All the elements in `horizontalCuts` are distinct.
* All the elements in `verticalCuts` are distinct.

# Approaches
## 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.
**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.
**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.
### Explanation
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.

```java
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);
    }
}
```
### 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)`.

## Optimal Approach with Sorting
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.
**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.
**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.
### Explanation
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`.

```java
import java.util.Arrays;

class Solution {
    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        long MOD = 1_000_000_007;

        // Sort the cuts to easily find adjacent gaps
        Arrays.sort(horizontalCuts);
        Arrays.sort(verticalCuts);

        // Calculate maximum horizontal gap
        // Start with the gap from the top edge (0) to the first cut
        long maxH = horizontalCuts[0];
        for (int i = 1; i < horizontalCuts.length; i++) {
            maxH = Math.max(maxH, horizontalCuts[i] - horizontalCuts[i-1]);
        }
        // Consider the gap from the last cut to the bottom edge (h)
        maxH = Math.max(maxH, h - horizontalCuts[horizontalCuts.length - 1]);

        // Calculate maximum vertical gap
        // Start with the gap from the left edge (0) to the first cut
        long maxW = verticalCuts[0];
        for (int i = 1; i < verticalCuts.length; i++) {
            maxW = Math.max(maxW, verticalCuts[i] - verticalCuts[i-1]);
        }
        // Consider the gap from the last cut to the right edge (w)
        maxW = Math.max(maxW, w - verticalCuts[verticalCuts.length - 1]);

        // Calculate the max area and return modulo
        // Cast to long before multiplication to prevent overflow
        return (int) ((maxH * maxW) % MOD);
    }
}
```
### 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.

# Solutions
### Java

```java
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);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxArea(int h, int w, vector<int> &horizontalCuts,
              vector<int> &verticalCuts) {
    horizontalCuts.push_back(0);
    horizontalCuts.push_back(h);
    verticalCuts.push_back(0);
    verticalCuts.push_back(w);
    sort(horizontalCuts.begin(), horizontalCuts.end());
    sort(verticalCuts.begin(), verticalCuts.end());
    int x = 0, y = 0;
    for (int i = 1; i < horizontalCuts.size(); ++i) {
      x = max(x, horizontalCuts[i] - horizontalCuts[i - 1]);
    }
    for (int i = 1; i < verticalCuts.size(); ++i) {
      y = max(y, verticalCuts[i] - verticalCuts[i - 1]);
    }
    const int mod = 1e9 + 7;
    return (1ll * x * y) % mod;
  }
};

```

### Python

```python
class Solution:
    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)

```