Leetcode #1465: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

Link to the Problem

Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

Thought Process

Each cut in the cake, divides the cake into pieces with certain height and certain width. We want to maximize the area, so the best piece would the one with maximum height among all pieces and maximum width among all pieces.

So the only task for us is to find what would be the height and width of each piece after all cuts and then find the piece with maximum height and width. Area of the piece is simply the multiplication of the height and the width.

Leetcode #1465: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts - Diagram to assist visualization, Problem Solving, Leetcode, Leetcode Solutions, Crack Coding Interview, Coding Interview, Data Structures and Algorithms
Leetcode #1465: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts – Diagram to assist visualization

Algorithm

  1. Get maximum height of a piece among all pieces.
    1. Sort the horizontal cuts array so that each horizontal cut would result in pieces of certain height.
    2. Find the max among them.
  2. Similarly for the width.
  3. Multiply height and width.

Code

class Solution {
const int mod = (1e9)+7; // As the question expects.
int getMax(int length, vector<int> &cuts) {
sort(cuts.begin(), cuts.end()); // Sort so that we will easily get the thickness
// of each piece after cutting it.
int n = cuts.size();
int maxCut = max(length-cuts[n-1], // Thickness of the last piece.
cuts[0]); // Thickness of the first piece.
for (int i=1; i<n; i++) { // For each cut -
maxCut = max(maxCut, cuts[i]-cuts[i-1]); // Thickness of each piece.
}
return maxCut;
}
public:
int maxArea(int height, int width, vector<int>& h, vector<int>& w) {
long maxHeight = getMax(height, h);
long maxWidth = getMax(width, w);
return (int)(maxHeight * maxWidth % mod);
}
};
view raw Leetcode_1465.cpp hosted with ❤ by GitHub

Is there anything that is still unclear? Let me know in the comments and I can elaborate further.

Don’t forget like & share the post, and subscribe to the blog to get notifications whenever solution to a new problem is added.

Happy Coding!

Similar Problems

Leetcode #492: Construct the Rectangle



Related Posts


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s