LeetCode Question - 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts π°
2nd July 2022 | π Daily LeetCode Challenge - #2
About the Series
Problem-solving is a key skill set for any tech-related stuff you might be working on.
When it comes to developers it's one of the most crucial skills which is needed in almost any day-to-day code you might be writing.
So, this series of blogs is all about practicing Daily LeetCode Challenges & Problem-solving. π
Problem Statement
Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts π°
You are given a rectangular cake of size
h x w
and two arrays of integershorizontalCuts
andverticalCuts
where:
horizontalCuts[i]
is the distance from the top of the rectangular cake to theith
horizontal cut and similarly, andverticalCuts[j]
is the distance from the left of the rectangular cake to thejth
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
andverticalCuts
. Since the answer can be a large number, return thismodulo 109 + 7
Video Explanation
Solution
Algorithm
- Push
0
andh
in thehorizontalCuts
. - Sort the
horizontalCuts
array in Ascending Order. - Take the maximum difference between the cuts by iterating on the list of
horizontalCuts
- Push
0
andh
in thehorizontalCuts
. - Sort the
horizontalCuts
array in Ascending Order. - Take the maximum difference between the cuts by iterating on the list of
horizontalCuts
- Multiply both the max values and return the modulo
10^9 + 7
- Now, we got the largest piece of Cake π°
Code in JS π§βπ»
/**
* @param {number} h
* @param {number} w
* @param {number[]} horizontalCuts
* @param {number[]} verticalCuts
* @return {number}
*/
var maxArea = function (h, w, horizontalCuts, verticalCuts) {
horizontalCuts.push(0, h);
horizontalCuts.sort((a, b) => a - b);
var maxH = 0;
verticalCuts.push(0, w);
verticalCuts.sort((a, b) => a - b);
var maxW = 0;
for (var i = 1; i < horizontalCuts.length; i++) {
maxH = Math.max(maxH, horizontalCuts[i] - horizontalCuts[i - 1]);
}
for (var j = 1; j < verticalCuts.length; j++) {
maxW = Math.max(maxW, verticalCuts[j] - verticalCuts[j - 1]);
}
return (BigInt(maxH) * BigInt(maxW)) % BigInt(1e9 + 7);
};
Time Complexity : O(nlogn)
Space Complexity: O(1)
You can find me on the web π
Add your solution or approach in the comments below.
Show your love by Sharing the blog. π€
βThe best way to predict the future is to create it.β
~ Peter Drucker