Leetcode 1725: Number Of Rectangles That Can Form The Largest Square
You are given an array
rectangles where each element rectangles[i] = [li, wi] represents a rectangle with length li and width wi. You can cut a square from the rectangle as long as the side of the square is less than or equal to both the length and width of the rectangle. Your task is to find the largest possible square that can be cut from any of the given rectangles, and then return how many rectangles can produce that largest square.Problem
Approach
Steps
Complexity
Input: You are given an array `rectangles`, where each element represents a rectangle's length and width. Each rectangle is represented as a list of two integers.
Example: Input: rectangles = [[6, 9], [3, 8], [5, 7], [12, 6]]
Constraints:
• 1 <= rectangles.length <= 1000
• rectangles[i].length == 2
• 1 <= li, wi <= 10^9
• li != wi
Output: Return the number of rectangles that can form a square with the largest possible side length.
Example: Output: 2
Constraints:
• The output is an integer representing the count of rectangles capable of forming the largest square.
Goal: The goal is to find the largest square that can be formed from any of the given rectangles and then determine how many rectangles can form that square.
Steps:
• 1. For each rectangle, determine the largest square that can be cut from it. This is done by taking the minimum of its length and width.
• 2. Track the largest square found so far, and count how many rectangles can produce this square.
• 3. Return the count of rectangles that can form the largest square.
Goal: The solution should efficiently handle up to 1000 rectangles and side lengths and widths as large as 10^9.
Steps:
• 1 <= rectangles.length <= 1000
• 1 <= li, wi <= 10^9
• li != wi
Assumptions:
• Each rectangle is non-degenerate, meaning both the length and width are non-zero.
• Input: Input: rectangles = [[6, 9], [3, 8], [5, 7], [12, 6]]
• Explanation: The largest squares from the rectangles have side lengths [6, 3, 5, 6]. The largest square has side length 6, and two rectangles can form a square of side 6, so the output is 2.
• Input: Input: rectangles = [[7, 8], [5, 5], [9, 10], [6, 6]]
• Explanation: The largest squares from the rectangles have side lengths [7, 5, 9, 6]. The largest square has side length 9, and only one rectangle can form a square of side 9, so the output is 1.
Approach: The approach involves finding the maximum side length of the square that can be formed from each rectangle and then counting how many rectangles can form the largest square.
Observations:
• The largest square that can be cut from a rectangle is limited by the smaller of its two sides (length or width).
• We can track the largest square side by comparing the minimum of length and width for each rectangle, then count how many rectangles share that maximum square size.
Steps:
• 1. Initialize a variable `maxSquareSide` to track the largest square side length found.
• 2. Iterate over each rectangle, compute the minimum of its length and width, and update `maxSquareSide` accordingly.
• 3. Maintain a count of how many rectangles can form a square of side `maxSquareSide`.
• 4. Return the count of rectangles that can form the largest square.
Empty Inputs:
• An empty list of rectangles is not a valid input as there should be at least one rectangle.
Large Inputs:
• The solution should efficiently handle cases where the number of rectangles is close to 1000.
Special Values:
• The rectangles with equal side lengths (e.g., a square) will always form a square of that side length.
Constraints:
• The solution must handle the large range of side lengths (up to 10^9).
int countGoodRectangles(vector<vector<int>>& rectangles) {
unordered_map<int,int>mp;
int ans=0;
for(auto i:rectangles){
int m=min(i[0],i[1]);
ans=max(ans,m);
mp[m]++;
}
return mp[ans];
}
1 : Function Definition
int countGoodRectangles(vector<vector<int>>& rectangles) {
The function `countGoodRectangles` is defined, taking a vector of rectangles as input. Each rectangle is represented as a vector of two integers, where each element is a side length.
2 : Variable Declaration
unordered_map<int,int>mp;
An unordered map `mp` is declared to store the frequency of each possible side length. The key is the side length, and the value is the count of rectangles with that side length.
3 : Variable Initialization
int ans=0;
An integer `ans` is initialized to 0. This variable will store the side length of the largest square that can be formed from the rectangles.
4 : Loop Start
for(auto i:rectangles){
A loop is started to iterate over each rectangle in the `rectangles` vector.
5 : Calculate Minimum Side
int m=min(i[0],i[1]);
For each rectangle, the minimum of the two side lengths is calculated and stored in `m`. This represents the maximum possible square side length that can fit within this rectangle.
6 : Update Maximum Side Length
ans=max(ans,m);
The `ans` variable is updated to store the maximum square side length found so far.
7 : Update Frequency Map
mp[m]++;
The frequency of the current minimum side length `m` is incremented in the unordered map `mp`.
8 : Return Result
return mp[ans];
The function returns the count of rectangles that have the maximum possible square side length `ans`.
Best Case: O(n), where n is the number of rectangles.
Average Case: O(n), since we examine each rectangle and its sides once.
Worst Case: O(n), as we iterate through all rectangles.
Description: The time complexity is linear with respect to the number of rectangles.
Best Case: O(1), as we only need a few variables.
Worst Case: O(n), for storing the count of rectangles and the largest square side.
Description: The space complexity is constant, aside from the input array.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus