LeetCode #1465: Maximum Area of Cake After Cuts

#javascript #algorithms

LeetCode Question - 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts 🍰

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

Earlier in this series: LeetCode #1710: Maximum Units on a Truck.

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

Video Explanation

Watch on YouTube

Solution

Algorithm

Push 0 and h in the horizontalCuts.
Sort the horizontalCuts array in Ascending Order.
Take the maximum difference between the cuts by iterating on the list of horizontalCuts
Push 0 and h in the horizontalCuts.
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

Originally published on July 2, 2022 at souravdey.space.

DEV Community