You are given an array rectangles where rectangles[i] = [li, wi] represents the ith rectangle of length li and width wi.
You can cut the ith rectangle to form a square with a side length of k if both k <= li and k <= wi. For example, if you have a rectangle [4,6], you can cut it to get a square with a side length of at most 4.
Let maxLen be the side length of the largest square you can obtain from any of the given rectangles.
Return the number of rectangles that can make a square with a side length of maxLen.
Example 1:
Input: rectangles = [[5,8],[3,9],[5,12],[16,5]] Output: 3 Explanation: The largest squares you can get from each rectangle are of lengths [5,3,5,5]. The largest possible square is of length 5, and you can get it out of 3 rectangles.
Example 2:
Input: rectangles = [[2,3],[3,7],[4,3],[3,7]] Output: 3
Constraints:
1 <= rectangles.length <= 1000rectangles[i].length == 21 <= li, wi <= 109li != wiProblem Overview: You are given a list of rectangles where each rectangle has a width and height. From each rectangle, you can cut a square whose side length equals min(width, height). The goal is to determine the maximum square side you can obtain and count how many rectangles can produce that square.
The key observation: every rectangle can contribute at most one square, and the largest square you can cut from a rectangle is limited by its smaller side. So the problem reduces to computing min(width, height) for each rectangle and counting how many rectangles achieve the maximum possible value.
Approach 1: Iterative Calculation of Maximum Square (O(n) time, O(1) space)
Scan the list of rectangles once. For each rectangle, compute side = min(width, height). Track two variables while iterating: the current maximum square size and how many rectangles achieve that size. If side > maxSide, update maxSide and reset the count to 1. If side == maxSide, increment the count. This works because the largest square possible overall must be the largest min(width, height) among all rectangles. The algorithm performs a single pass over the array, making it both optimal and straightforward.
This approach avoids extra data structures and performs constant work per rectangle. It is the cleanest implementation for interviews and production code because it directly models the problem's constraint: the square side is always limited by the rectangle's smaller dimension.
Approach 2: Using Sorting to Simplify Counting (O(n log n) time, O(1) extra space)
Another option is to compute min(width, height) for each rectangle and then sort these values. After sorting, the largest square size appears at the end of the array. Count how many times this maximum value occurs by scanning backward until the value changes. Sorting introduces O(n log n) time due to the ordering step, but the counting logic becomes very simple.
This method can be useful when you already plan to sort data for another reason or when solving variations that require ordered processing. The idea relies on standard sorting techniques applied to values derived from the array.
Recommended for interviews: The iterative single-pass solution is what interviewers expect. It runs in O(n) time with O(1) space and shows you recognized the key insight: the largest square from a rectangle equals its smaller side. Mentioning the sorting alternative demonstrates understanding of tradeoffs, but the linear scan highlights stronger algorithmic reasoning.
This approach involves iterating through each rectangle to determine the largest square it can form. The maximum size of this square is tracked and stored. Another pass is then made through the rectangles to count how many rectangles can form this largest square size. It consists of two primary operations: finding the maximum square side we can form and counting the rectangles that can achieve this size. This is efficient because it requires a constant amount of work per rectangle.
The function countGoodRectangles iterates through each rectangle, calculating the maximum square side it can form by taking the minimum of its length and width. If this square size exceeds the previous maxLen, update maxLen and reset the counter to 1. If it equals maxLen, increment the counter.
Time Complexity: O(n), where n is the number of rectangles. Each rectangle is checked once.
Space Complexity: O(1), as only a few variables are used for storaging.
This approach aims to first create an array of possible maximum square sides from each rectangle. Sorting this array helps in determining the maximal side length quickly. After identifying the maximum square size, we count how many times it occurs. This method leverages the power of sorting for potential clarity and ease of updates.
This function computes all possible maximum square sides for each rectangle, stores them in max_sides. It then directly determines the most frequent occurrence of the maximal side length using count, which outputs the result.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing the maximum side lengths.
| Approach | Complexity |
|---|---|
| Iterative Calculation of Maximum Square | Time Complexity: O(n), where n is the number of rectangles. Each rectangle is checked once. |
| Using Sorting to Simplify Counting | Time Complexity: O(n log n) due to sorting. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Calculation of Maximum Square | O(n) | O(1) | Best general solution; single pass through the array with constant memory |
| Using Sorting to Simplify Counting | O(n log n) | O(1) | Useful if rectangle sizes are already being sorted or ordered for other operations |
LeetCode 1725: Number Of Rectangles That Can Form The Largest Square • Practical Coders • 953 views views
Watch 9 more video solutions →Practice Number Of Rectangles That Can Form The Largest Square with our built-in code editor and test cases.
Practice on FleetCode