Skip to main content
Talentd

Number Of Rectangles That Can Form The Largest Square - Solution & Explanation

EasyArray17 min readAsked at: Allincall
Practice this problem

Problem Statement

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 <= 1000
  • rectangles[i].length == 2
  • 1 <= li, wi <= 109
  • li != 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.

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.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing the maximum side lengths.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Calculation of Maximum Square

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.

Using Sorting to Simplify Counting

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing the maximum side lengths.

Single Pass—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Calculation of Maximum SquareO(n)O(1)Best general solution; single pass through the array with constant memory
Using Sorting to Simplify CountingO(n log n)O(1)Useful if rectangle sizes are already being sorted or ordered for other operations

Video Solution

LeetCode 1725: Number Of Rectangles That Can Form The Largest Square • Practical Coders • 974 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Number Of Rectangles That Can Form The Largest Square with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays