Number Of Rectangles That Can Form The Largest Square
EasyPrompt
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 != wi
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves calculating the maximum possible square side for each rectangle, storing these side lengths in a list, sorting the list, and then counting the occurrences of the largest value.
Algorithm
- Create an empty list,
sideLengths. - Iterate through each
rectanglein the inputrectanglesarray. - For each
rectangle, calculateside = min(rectangle[0], rectangle[1]). - Add
sideto thesideLengthslist. - Sort the
sideLengthslist in descending order. - Get the
maxLenwhich is the first element of the sorted list. - Initialize a
countto 0. - Iterate through the
sideLengthslist. If an element is equal tomaxLen, incrementcount. If it's smaller, break the loop (since the list is sorted). - Return
count.
Walkthrough
The core idea is to first transform the problem from dealing with rectangles to dealing with a simple list of numbers. For each rectangle [l, w], the largest square that can be cut has a side length of min(l, w). We compute this value for every rectangle and store it in an auxiliary array.
Once we have this array of possible side lengths, we can sort it in descending order. The largest possible side length, maxLen, will be the first element of the sorted array.
Finally, we iterate through the sorted array to count how many times maxLen appears. This count is our final answer.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public int countGoodRectangles(int[][] rectangles) { List<Integer> sideLengths = new ArrayList<>(); for (int[] rect : rectangles) { sideLengths.add(Math.min(rect[0], rect[1])); } Collections.sort(sideLengths, Collections.reverseOrder()); if (sideLengths.isEmpty()) { return 0; } int maxLen = sideLengths.get(0); int count = 0; for (int side : sideLengths) { if (side == maxLen) { count++; } else { // Since the list is sorted, we can stop early break; } } return count; }}Complexity
Time
O(N log N), where N is the number of rectangles. The dominant operation is sorting the list of side lengths.
Space
O(N), as we need an auxiliary list to store the side length for each of the N rectangles.
Trade-offs
Pros
Conceptually simple and breaks the problem down into distinct, easy-to-understand steps (calculate, sort, count).
Cons
Requires extra space to store the side lengths.
The sorting step makes it less efficient than linear time approaches, especially for large inputs.
This approach avoids sorting by iterating through the input array twice. The first pass finds the maximum possible square side length (maxLen), and the second pass counts how many rectangles can form a square of that size.
Algorithm
- Initialize
maxLen = 0. - First Pass: Iterate through each
rectangleinrectangles.- Calculate
side = min(rectangle[0], rectangle[1]). - Update
maxLen = max(maxLen, side).
- Calculate
- Initialize
count = 0. - Second Pass: Iterate through each
rectangleinrectangles.- Calculate
side = min(rectangle[0], rectangle[1]). - If
side == maxLen, incrementcount.
- Calculate
- Return
count.
Walkthrough
Instead of storing all possible side lengths, we can find the maximum side length in one pass and then count its occurrences in a second pass. This eliminates the need for sorting and extra storage.
First Pass: We iterate through all the rectangles, calculating min(l, w) for each. We maintain a variable maxLen and update it whenever we find a side length greater than the current maxLen.
Second Pass: After the first pass, maxLen holds the side length of the largest possible square. We iterate through the rectangles again. This time, we count how many rectangles have min(l, w) equal to maxLen.
class Solution { public int countGoodRectangles(int[][] rectangles) { int maxLen = 0; // First pass: find the maximum possible side length for (int[] rect : rectangles) { int side = Math.min(rect[0], rect[1]); if (side > maxLen) { maxLen = side; } } int count = 0; // Second pass: count rectangles that can form a square of maxLen for (int[] rect : rectangles) { if (Math.min(rect[0], rect[1]) == maxLen) { count++; } } return count; }}Complexity
Time
O(N), where N is the number of rectangles. We perform two separate passes over the array, each taking O(N) time. The total time is O(N) + O(N) = O(N).
Space
O(1), as we only use a few variables to store `maxLen` and `count`, regardless of the input size.
Trade-offs
Pros
More efficient than the sorting approach with a linear time complexity.
Uses constant extra space, making it memory-efficient.
Cons
Requires iterating through the input data twice, which is slightly less optimal than a single-pass solution.
This is the most efficient approach. It finds the maxLen and counts the rectangles in a single iteration over the input array, updating both values as it goes.
Algorithm
- Initialize
maxLen = 0andcount = 0. - Iterate through each
rectanglein therectanglesarray. - Calculate
side = min(rectangle[0], rectangle[1]). - If
side > maxLen:- Update
maxLen = side. - Reset
count = 1.
- Update
- Else if
side == maxLen:- Increment
count.
- Increment
- After the loop, return
count.
Walkthrough
We can optimize the two-pass approach into a single pass. We maintain two variables: maxLen for the largest side length found so far, and count for the number of rectangles that can form a square of that maxLen.
As we iterate through the rectangles, we calculate the potential side length side = min(l, w) for the current rectangle. We then compare side with our current maxLen:
- If
sideis greater thanmaxLen, it means we've found a new, larger maximum side length. We must updatemaxLento this newsideand reset ourcountto 1, as this is the first rectangle we've seen for this new maximum size. - If
sideis equal to the currentmaxLen, it means we've found another rectangle that can form a square of the same maximum size. We simply increment thecount. - If
sideis less thanmaxLen, this rectangle is not relevant to our count of the largest squares, so we ignore it.
This way, after iterating through the entire array just once, we will have the final correct count.
class Solution { public int countGoodRectangles(int[][] rectangles) { int maxLen = 0; int count = 0; for (int[] rect : rectangles) { int side = Math.min(rect[0], rect[1]); if (side > maxLen) { maxLen = side; count = 1; } else if (side == maxLen) { count++; } } return count; }}Complexity
Time
O(N), where N is the number of rectangles. We iterate through the array only once.
Space
O(1), as we only use a constant number of variables (`maxLen`, `count`).
Trade-offs
Pros
Most efficient approach with O(N) time complexity and O(1) space complexity.
Processes the data in a single pass, minimizing redundant computations.
Cons
The logic can be slightly more complex to reason about compared to the two-pass approach, as it involves updating two variables based on conditional logic within a single loop.
Solutions
Solution
class Solution { public int countGoodRectangles ( int [][] rectangles ) { int ans = 0 , mx = 0 ; for ( var e : rectangles ) { int x = Math . min ( e [ 0 ], e [ 1 ]); if ( mx < x ) { mx = x ; ans = 1 ; } else if ( mx == x ) { ++ ans ; } } return ans ; } }class Solution { public: int countGoodRectangles ( vector < vector < int >>& rectangles ) { int ans = 0 , mx = 0 ; for ( auto & e : rectangles ) { int x = min ( e [ 0 ], e [ 1 ]); if ( mx < x ) { mx = x ; ans = 1 ; } else if ( mx == x ) { ++ ans ; } } return ans ; } };class Solution : def countGoodRectangles ( self , rectangles : List [ List [ int ]]) -> int : ans = mx = 0 for l , w in rectangles : x = min ( l , w ) if mx < x : ans = 1 mx = x elif mx == x : ans += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.