Sourav Dey
Sourav's Digital πŸ“˜ Notebook

Sourav's Digital πŸ“˜ Notebook

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

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

2nd July 2022 | πŸ—“ Daily LeetCode Challenge - #2

Sourav Dey's photo
Sourav Dey
Β·Jul 3, 2022Β·

2 min read

Subscribe to my newsletter and never miss my upcoming articles

Play this article

Table of contents

  • About the Series
  • Problem Statement
  • Video Explanation
  • Solution
  • You can find me on the web 🌍

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

Sketch-annotation-element-stroke-line-arrow-spiral-up.png

Solution

Algorithm

  1. Push 0 and h in the horizontalCuts.
  2. Sort the horizontalCuts array in Ascending Order.
  3. Take the maximum difference between the cuts by iterating on the list of horizontalCuts
  4. Push 0 and h in the horizontalCuts.
  5. Sort the horizontalCuts array in Ascending Order.
  6. Take the maximum difference between the cuts by iterating on the list of horizontalCuts
  7. Multiply both the max values and return the modulo 10^9 + 7
  8. 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

Did you find this article valuable?

Support Sourav Dey by becoming a sponsor. Any amount is appreciated!

See recent sponsors |Β Learn more about Hashnode Sponsors
Β 
Share this