Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts (Leetcode 1465)

Difficulty: Medium Link: Day3: June Leetcode Challenge 2021

Problem Statement

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 ith horizontal cut and similarly, 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 verticalCutsSince the answer can be a huge number, return this modulo 10^9 + 7.

Examples

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

Solution

Intuition

We are try to find out every possible rectangle and find the rectangle with maximum area, but that would be very expensive for large values of h, w. If we think in terms of maximising the area, we can observe that the problem is indeed simple and we need to find the maximum gaps between the horizontal and vertical lines to form our area.

The key insight to the problem is that not all cuts (horizontal or vertical) matters. If we think about area then it is width * height and for area to be maximum, width and height should be maximum. While iterating lets say, on the horizontal cuts, the distance between two adjacent cuts would make up a rectangle with height horizontalCuts[i]- horizontalCuts[i-1]. We can find all gaps and maintain the max value (maxHeight). Similarly, iterating through the vertical cuts would help us find the maxWidth.

Also keep in mind the edge case for considering the border values for width and height. The initial width would form between 0 and verticalCuts[0] while the extreme last width would be w – verticalCuts[n-1]. Similarly, for initial and last height which we can solve by initialising the maxHeight = max(horizontalCuts[0], w – horizontalCuts[n-1]) and maxWidth = max(verticalCuts[0], h – verticalCuts[n-1]).

Algorithm

  1. Sort both the horizontal and vertical cuts array.
  2. Initialise a variable for maxWidth and iterate through the vertical cuts and find the maxWidth by maxWidth = max(maxWidth, verticalCuts[i] – verticalCuts[i-1]).
  3. Repeat the step 2 for finding the maxHeight from horizontal cuts.
  4. 4. Our maximum area is ( maxHeight * maxWidth ) % 10^9 + 7

Note

Also, since area can be huge, so do not forget to return your answer after modulo with 10^9 + 7 (I missed reading the last statement and wasted 10 minutes to figure out why the solution is not working for large h, w values :/ ).

Swift

//Link: https://leetcode.com/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/
class Solution {
func maxArea(_ h: Int, _ w: Int, _ horizontalCuts: [Int], _ verticalCuts: [Int]) -> Int {
// first sort the cuts
let hcuts = horizontalCuts.sorted()
let vcuts = verticalCuts.sorted()
var maxWidth:Int = 0, maxHeight:Int = 0
// Find max gap b/w the vertical lines = Width
maxWidth = max(vcuts[0], w vcuts.last!)
for i in 1..<vcuts.count{
maxWidth = max(maxWidth, vcuts[i] vcuts[i1])
}
// Max gap b/w horizontal line = Height
maxHeight = max(hcuts[0], h hcuts.last!)
for i in 1..<hcuts.count{
maxHeight = max(maxHeight, hcuts[i] hcuts[i1])
}
// calculate the area
// since area would be huge return this modulo 10^9 + 7.
return (maxWidth * maxHeight) % 1000000007
}
}
view raw max_area_cake.swift hosted with ❤ by GitHub

Python

class Solution:
def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
# Start by sorting the inputs
horizontalCuts.sort()
verticalCuts.sort()
# Consider the edges first
max_height = max(horizontalCuts[0], h horizontalCuts[1])
for i in range(1, len(horizontalCuts)):
# horizontalCuts[i] – horizontalCuts[i – 1] represents the distance between
# two adjacent edges, and thus a possible height
max_height = max(max_height, horizontalCuts[i] horizontalCuts[i 1])
# Consider the edges first
max_width = max(verticalCuts[0], w verticalCuts[1])
for i in range(1, len(verticalCuts)):
# verticalCuts[i] – verticalCuts[i – 1] represents the distance between
# two adjacent edges, and thus a possible width
max_width = max(max_width, verticalCuts[i] verticalCuts[i 1])
# Python doesn't need to worry about overflow – don't forget the modulo though!
return (max_height * max_width) % (10**9 + 7)
view raw max_area_cake.py hosted with ❤ by GitHub

Java

class Solution {
// We will use long instead of int to prevent overflow
public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
// Start by sorting the inputs
Arrays.sort(horizontalCuts);
Arrays.sort(verticalCuts);
int n = horizontalCuts.length;
int m = verticalCuts.length;
// Consider the edges first
long maxHeight = Math.max(horizontalCuts[0], h horizontalCuts[n 1]);
for (int i = 1; i < n; i++) {
// horizontalCuts[i] – horizontalCuts[i – 1] represents the distance between
// two adjacent edges, and thus a possible height
maxHeight = Math.max(maxHeight, horizontalCuts[i] horizontalCuts[i 1]);
}
// Consider the edges first
long maxWidth = Math.max(verticalCuts[0], w verticalCuts[m 1]);
for (int i = 1; i < m; i++){
// verticalCuts[i] – verticalCuts[i – 1] represents the distance between
// two adjacent edges, and thus a possible width
maxWidth = Math.max(maxWidth, verticalCuts[i] verticalCuts[i 1]);
}
// Be careful of overflow, and don't forget the modulo!
return (int) ((maxWidth * maxHeight) % (1e9 + 7));
}
}
view raw max_area_cake.java hosted with ❤ by GitHub

Complexity Analysis

We are sorting our horizontal cuts and vertical cuts which is a O(NLogN) operation. If we consider M as the length of horizontal cuts and N as the length of vertical cuts, then total complexity would be bounded by O(MLogM) + O(NLogN). After that we are just iterating them, which is economical than the sorting operation so we can ignore that. For space, we are just keeping two variable so it’s a constant space solution.

Time = O(MLogM) + O(NLogN) // M = Length of first array, N = Length of second array

Space = O(1)

Leave a Reply

Your email address will not be published. Required fields are marked *