Number Of Rectangles That Can Form The Largest Square Solution
Number Of Rectangles That Can Form The Largest Square solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Number Of Rectangles That Can Form The Largest Square is an easy coding problem on arrays and counting, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Counting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
rectangles[i] = [l, w] is a rectangle of length l and width w. You may cut a square out of a rectangle as long as its side is at most both l and w — so the biggest square rectangle i can give has side min(l, w).
Let maxLen be the largest square side that any rectangle can give. Return how many rectangles can give a square of side maxLen.
Example 1
Input: rectangles = [[4,9],[7,3],[9,4],[4,6]]
Output: 3
Explanation: The best squares have sides 4, 3, 4 and 4, so maxLen = 4 and three rectangles reach it.
Example 2
Input: rectangles = [[2,3],[6,5],[3,9]]
Output: 1
Example 3
Input: rectangles = [[10,1000000000]]
Output: 1
Constraints
1 <= rectangles.length <= 1000rectangles[i].length == 21 <= l, w <= 10^9l != w
Hints for Number Of Rectangles That Can Form The Largest Square
Hint 1
Each rectangle contributes exactly one number: the shorter of its two sides.
Hint 2
You need the maximum of those numbers and how often it occurs.
Hint 3
Both can be tracked in a single pass: reset the count when a new maximum appears.
How to solve Number Of Rectangles That Can Form The Largest Square
Reduce each rectangle to min(l, w), the side of the largest square it can give; the answer is how many times the maximum of those values occurs.
Approach
- Keep
best = 0andcount = 0. - For each rectangle compute
side = min(l, w). - If
side > best, setbest = sideandcount = 1; ifside == best, incrementcount. - Return
count.
Why it works
A rectangle can give a square of side maxLen exactly when its shorter side is at least maxLen, and since maxLen is the largest shorter side, that means exactly equal. The running maximum with a reset counter counts those rectangles in one pass.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Use the shorter side — the longer side does not limit the square.
- Reset the count to 1, not 0, when a new maximum appears.
- Sides reach 10^9, which still fits a 32-bit int; no sums are needed.
Reference solution
Python
from typing import List
def countGoodRectangles(rectangles: List[List[int]]) -> int:
sides = [min(l, w) for l, w in rectangles]
return sides.count(max(sides))Java
public static int countGoodRectangles(int[][] rectangles) {
int best = 0, count = 0;
for (int[] r : rectangles) {
int side = Math.min(r[0], r[1]);
if (side > best) {
best = side;
count = 1;
} else if (side == best) {
count++;
}
}
return count;
}C++
int countGoodRectangles(vector<vector<int>>& rectangles) {
int best = 0, count = 0;
for (auto& r : rectangles) {
int side = min(r[0], r[1]);
if (side > best) {
best = side;
count = 1;
} else if (side == best) {
count++;
}
}
return count;
}JavaScript
var countGoodRectangles = function(rectangles) {
var best = 0, count = 0;
for (var i = 0; i < rectangles.length; i++) {
var side = Math.min(rectangles[i][0], rectangles[i][1]);
if (side > best) {
best = side;
count = 1;
} else if (side === best) {
count++;
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays