Number Of Rectangles That Can Form The Largest Square solution and explanation
9 more videos on this problem
LeetCode 1725: Number Of Rectangles That Can Form The Largest SquarePractical Coders · 9:09 · 974 views
leetcode - 1725 Number if Rectangles That Can Form The Largest SquarelitCode · 14:25 · 887 views
1725. Number Of Rectangles That Can Form The Largest Square (Leetcode Easy)Programming Live with Larry · 4:44 · 718 views
1725. Number Of Rectangles That Can Form The Largest Square|LeetCode | Python | Java | EnglishŞahin Oğur · 12:52 · 457 views
LeetCode 1725. [easy] Number Of Rectangles That Can Form The Largest SquareFrancesco Manicardi · 3:06 · 316 views
LeetCode 1725 | Number Of Rectangles That Can Form The Largest Square | Array | JavaSleepy Cracker · 2:17 · 278 views
C++ WalkThrough - Leetcode #1725 Number Of Rectangles That Can form The Largest SquareJoshProgramin · 7:32 · 201 views
1725. Number of Rectangles That Can Form the Largest Square| Recursion |JAVA| Leetcode|DSAmoodyCode · 17:07 · 159 views
1725. Number Of Rectangles That Can Form The Largest Square with Python | Leetcode with PythonArsalan Ahmed · 9:36 · 106 views
1725 Number Of Rectangles That Can Form The Largest SquareMath Geeks · 1:21 · 93 views
The problem
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
Approach overview
Problem 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.
Approach 1: Iterative Calculation of Maximum Square
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.
def countGoodRectangles(rectangles):
maxLen = 0
count = 0
for l, w in rectangles:
side = min(l, w)
if side > maxLen:
maxLen = side
count = 1
elif side == maxLen:
count += 1
return count
rectangles = [[5,8],[3,9],[5,12],[16,5]]
print(countGoodRectangles(rectangles))public 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;
}
public static void main(String[] args) {
int[][] rectangles = {{5,8},{3,9},{5,12},{16,5}};
Solution sol = new Solution();
System.out.println(sol.countGoodRectangles(rectangles));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int countGoodRectangles(vector<vector<int>>& rectangles) {
int maxLen = 0;
int count = 0;
for (auto& rect : rectangles) {
int side = min(rect[0], rect[1]);
if (side > maxLen) {
maxLen = side;
count = 1;
} else if (side == maxLen) {
count++;
}
}
return count;
}
int main() {
vector<vector<int>> rectangles = {{5,8},{3,9},{5,12},{16,5}};
cout << countGoodRectangles(rectangles) << endl;
return 0;
}function countGoodRectangles(rectangles) {
let maxLen = 0;
let count = 0;
for (const [l, w] of rectangles) {
const side = Math.min(l, w);
if (side > maxLen) {
maxLen = side;
count = 1;
} else if (side === maxLen) {
count++;
}
}
return count;
}
const rectangles = [[5,8],[3,9],[5,12],[16,5]];
console.log(countGoodRectangles(rectangles));#include <stdio.h>
int countGoodRectangles(int rectangles[][2], int rectanglesSize) {
int maxLen = 0;
int count = 0;
for (int i = 0; i < rectanglesSize; ++i) {
int side = rectangles[i][0] < rectangles[i][1] ? rectangles[i][0] : rectangles[i][1];
if (side > maxLen) {
maxLen = side;
count = 1;
} else if (side == maxLen) {
count++;
}
}
return count;
}
int main() {
int rectangles[4][2] = {{5,8},{3,9},{5,12},{16,5}};
printf("%d", countGoodRectangles(rectangles, 4));
return 0;
}using System;
public class Solution {
public int CountGoodRectangles(int[][] rectangles) {
int maxLen = 0;
int count = 0;
foreach (var rect in rectangles) {
int side = Math.Min(rect[0], rect[1]);
if (side > maxLen) {
maxLen = side;
count = 1;
} else if (side == maxLen) {
count++;
}
}
return count;
}
public static void Main() {
int[][] rectangles = new int[][] { new int[] {5,8}, new int[] {3,9}, new int[] {5,12}, new int[] {16,5} };
Solution sol = new Solution();
Console.WriteLine(sol.CountGoodRectangles(rectangles));
}
}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.
Approach 2: Using Sorting to Simplify Counting
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.
def countGoodRectangles(rectangles):
max_sides = [min(l, w) for l, w in rectangles]
max_side = max(max_sides)
return max_sides.count(max_side)
rectangles = [[5,8],[3,9],[5,12],[16,5]]
print(countGoodRectangles(rectangles))import java.util.*;
public class Solution {
public int countGoodRectangles(int[][] rectangles) {
int[] maxSides = new int[rectangles.length];
for (int i = 0; i < rectangles.length; i++) {
maxSides[i] = Math.min(rectangles[i][0], rectangles[i][1]);
}
Arrays.sort(maxSides);
int maxSide = maxSides[maxSides.length - 1];
int count = 0;
for (int side : maxSides) {
if (side == maxSide) {
count++;
}
}
return count;
}
public static void main(String[] args) {
int[][] rectangles = {{5,8},{3,9},{5,12},{16,5}};
Solution sol = new Solution();
System.out.println(sol.countGoodRectangles(rectangles));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int countGoodRectangles(vector<vector<int>>& rectangles) {
vector<int> maxSides;
for (auto& rect : rectangles) {
maxSides.push_back(min(rect[0], rect[1]));
}
sort(maxSides.begin(), maxSides.end());
int maxSide = maxSides[maxSides.size() - 1];
return count(maxSides.rbegin(), maxSides.rend(), maxSide);
}
int main() {
vector<vector<int>> rectangles = {{5,8},{3,9},{5,12},{16,5}};
cout << countGoodRectangles(rectangles) << endl;
return 0;
}function countGoodRectangles(rectangles) {
let maxSides = rectangles.map(([l, w]) => Math.min(l, w));
maxSides.sort((a, b) => a - b);
const maxSide = maxSides[maxSides.length - 1];
return maxSides.filter(side => side === maxSide).length;
}
const rectangles = [[5,8],[3,9],[5,12],[16,5]];
console.log(countGoodRectangles(rectangles));#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int countGoodRectangles(int rectangles[][2], int rectanglesSize) {
int* maxSides = malloc(rectanglesSize * sizeof(int));
for (int i = 0; i < rectanglesSize; i++) {
maxSides[i] = rectangles[i][0] < rectangles[i][1] ? rectangles[i][0] : rectangles[i][1];
}
qsort(maxSides, rectanglesSize, sizeof(int), compare);
int maxSide = maxSides[rectanglesSize - 1];
int count = 0;
for (int i = rectanglesSize - 1; i >= 0 && maxSides[i] == maxSide; i--) {
count++;
}
free(maxSides);
return count;
}
int main() {
int rectangles[4][2] = {{5,8},{3,9},{5,12},{16,5}};
printf("%d\n", countGoodRectangles(rectangles, 4));
return 0;
}using System;
using System.Linq;
public class Solution {
public int CountGoodRectangles(int[][] rectangles) {
int[] maxSides = rectangles.Select(rect => Math.Min(rect[0], rect[1])).ToArray();
Array.Sort(maxSides);
int maxSide = maxSides[^1];
return maxSides.Count(side => side == maxSide);
}
public static void Main() {
int[][] rectangles = new int[][] { new int[] {5,8}, new int[] {3,9}, new int[] {5,12}, new int[] {16,5} };
Solution sol = new Solution();
Console.WriteLine(sol.CountGoodRectangles(rectangles));
}
}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 3: Single Pass
We define a variable ans to record the count of squares with the current maximum side length, and another variable mx to record the current maximum side length.
We traverse the array rectangles. For each rectangle [l, w], we take x = min(l, w). If mx < x, it means we have found a larger side length, so we update mx to x and update ans to 1. If mx = x, it means we have found a side length equal to the current maximum side length, so we increase ans by 1.
Finally, we return ans.
The time complexity is O(n), where n is the length of the array rectangles. The space complexity is O(1).
function countGoodRectangles(rectangles: number[][]): number {
let [ans, mx] = [0, 0];
for (const [l, w] of rectangles) {
const x = Math.min(l, w);
if (mx < x) {
mx = x;
ans = 1;
} else if (mx === x) {
++ans;
}
}
return ans;
}func countGoodRectangles(rectangles [][]int) (ans int) {
mx := 0
for _, e := range rectangles {
x := min(e[0], e[1])
if mx < x {
mx = x
ans = 1
} else if mx == x {
ans++
}
}
return
}Complexity comparison
| 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. |
| Single Pass | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Number Of Rectangles That Can Form The Largest Square easy or hard?
Number Of Rectangles That Can Form The Largest Square is classified as an Easy problem. The key step is recognizing that the largest square from a rectangle is determined by its smaller dimension, which leads to a straightforward linear scan solution.
Number Of Rectangles That Can Form The Largest Square Python/Java solution
In Python or Java, iterate through the rectangles list and compute min(width, height) for each pair. Track the maximum side length and how many rectangles produce it. Both implementations run in O(n) time with O(1) additional space.
How to solve Number Of Rectangles That Can Form The Largest Square in O(n)?
Iterate through the rectangles array and compute side = min(width, height) for each rectangle. Maintain two variables: maxSide and count. If side exceeds maxSide, update maxSide and reset count to 1; if side equals maxSide, increment count. After processing all rectangles, count represents how many rectangles can form the largest square.
What is the best approach for Number Of Rectangles That Can Form The Largest Square?
The best approach is a single-pass greedy scan. For each rectangle, compute min(width, height) to determine the largest square it can produce. Track the maximum square side and count how many rectangles achieve that value. This solution runs in O(n) time and O(1) space.
Is Number Of Rectangles That Can Form The Largest Square asked at Google/Amazon/Meta?
Array-based greedy counting problems like this appear frequently in coding interviews at large tech companies such as Amazon, Google, and Meta. While this exact question is relatively simple, it tests basic array traversal, reasoning about constraints, and recognizing key observations quickly.
What data structure is used in Number Of Rectangles That Can Form The Largest Square?
The primary data structure is a simple array containing rectangle dimensions. The algorithm processes each element sequentially and does not require additional structures such as hash maps or heaps, keeping memory usage constant.
What is the time complexity of Number Of Rectangles That Can Form The Largest Square?
The optimal solution runs in O(n) time because it iterates through the rectangles once and performs constant work per element. Space complexity is O(1) since only a few variables are used to track the maximum square side and its count.