Solution: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
Tags: algorithms, javascript, java, python
Published: 2021-06-03 08:16:36

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/discuss/1248591).*

---

#### [Leetcode Problem #1465 (*Medium*): Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts](https://leetcode.com/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Given a rectangular cake with height `h` and width `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, `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 huge number, return this modulo `10^9 + 7`.

---

#### ***Examples:***
>
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.
Visual:|![Example 1 Visual](https://assets.leetcode.com/uploads/2020/05/14/leetcode_max_area_2.png)
>
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.
Visual:|![Example 2 Visual](https://assets.leetcode.com/uploads/2020/05/14/leetcode_max_area_3.png)
>
Example 3:||
|---:|---|
Input:| h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
Output:| 9

---

#### ***Constraints:***
>
 - `2 <= h, w <= 10^9`
 - `1 <= horizontalCuts.length < min(h, 10^5)`
 - `1 <= verticalCuts.length < min(w, 10^5)`
 - `1 <= horizontalCuts[i] < h`
 - `1 <= verticalCuts[i] < w`
 - It is guaranteed that all elements in `horizontalCuts` are distinct.
 - It is guaranteed that all elements in `verticalCuts` are distinct.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

The trick to this problem is realizing that if the horizontal slices and vertical slices are perpendicular, then all vertical slices cross all horizontal slices. This means that we just need to find the largest of each, and the cross-section should be the largest slice.

To find the largest slice of each, we need to first **sort** the horizontal cuts (**hc**) and vertical cuts (**vc**), then iterate through both sets and keep track of the maximum difference found between two consecutive cuts (**maxh**, **maxv**). We need to not forget to include the two end cuts, which are found using **0** and **h**/**w**, as well.

Once we have the largest difference for both, we can just **return** the product of these two numbers, **modulo 1e9+7**.

 - _**Time Complexity: O(N * log(N) + M * log(M))**  where **N** is the length of **hc** and **M** is the length of **vc**_
 - _**Space Complexity: O(1)**_

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var maxArea = function(h, w, hc, vc) {
    hc.sort((a,b) => a - b)
    vc.sort((a,b) => a - b)
    let maxh = Math.max(hc[0], h - hc[hc.length-1]),
        maxv = Math.max(vc[0], w - vc[vc.length-1])
    for (let i = 1; i < hc.length; i++)
        maxh = Math.max(maxh, hc[i] - hc[i-1])
    for (let i = 1; i < vc.length; i++)
        maxv = Math.max(maxv, vc[i] - vc[i-1])
    return BigInt(maxh) * BigInt(maxv) % 1000000007n
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def maxArea(self, h: int, w: int, hc: List[int], vc: List[int]) -> int:
        hc.sort()
        vc.sort()
        maxh, maxv = max(hc[0], h - hc[-1]), max(vc[0], w - vc[-1])
        for i in range(1, len(hc)):
            maxh = max(maxh, hc[i] - hc[i-1])
        for i in range(1, len(vc)):
            maxv = max(maxv, vc[i] - vc[i-1])
        return (maxh * maxv) % 1000000007
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int maxArea(int h, int w, int[] hc, int[] vc) {
        Arrays.sort(hc);
        Arrays.sort(vc);
        int maxh = Math.max(hc[0], h - hc[hc.length-1]),
            maxv = Math.max(vc[0], w - vc[vc.length-1]);
        for (int i = 1; i < hc.length; i++)
            maxh = Math.max(maxh, hc[i] - hc[i-1]);
        for (int i = 1; i < vc.length; i++)
            maxv = Math.max(maxv, vc[i] - vc[i-1]);
        return (int)((long)maxh * maxv % 1000000007);
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int maxArea(int h, int w, vector<int>& hc, vector<int>& vc) {
        sort(hc.begin(), hc.end());
        sort(vc.begin(), vc.end());
        int maxh = max(hc[0], h - hc.back()),
            maxv = max(vc[0], w - vc.back());
        for (int i = 1; i < hc.size(); i++)
            maxh = max(maxh, hc[i] - hc[i-1]);
        for (int i = 1; i < vc.size(); i++)
            maxv = max(maxv, vc[i] - vc[i-1]);
        return (int)((long)maxh * maxv % 1000000007);
    }
};
```