#1725

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Number Of Rectangles That Can Form The Largest Square

Determine how many rectangles can be trimmed to form the largest possible square using an array-driven solution strategy.

array

Problem Statement

Given an array rectangles where rectangles[i] = [li, wi] represents the length and width of the ith rectangle, determine the maximum square size obtainable from any rectangle. A rectangle can be cut into a square of side length k if k <= li and k <= wi.

Your task is to find how many rectangles can produce the largest possible square from the given set. The output should be the count of rectangles that can generate a square with the maximum side length.

Examples

Example 1

Input: rectangles = [[5,8],[3,9],[5,12],[16,5]]

Output: 3

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

Example details omitted.

Constraints

1 <= rectangles.length <= 1000
rectangles[i].length == 2
1 <= li, wi <= 109
li != wi

Solution Approach

Compute Maximum Square Side for Each Rectangle

Iterate through each rectangle and calculate the largest square it can produce as min(length, width). Store these values in an array for easy comparison.

Identify the Largest Square Side Across All Rectangles

Scan the array of maximum square sides to determine the overall largest square side possible. This represents the target square size to count against.

Count Rectangles Matching the Largest Square Side

Loop through the array of maximum square sides and increment a counter for each rectangle whose maximum square side equals the largest found. Return this count as the final answer.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each rectangle is processed once for max side computation and once for counting. Space complexity is O(1) if counting is done in-place, or O(n) if storing all max sides separately.

What Interviewers Usually Probe

Checks if candidate immediately identifies min(length, width) as the key to largest square computation.
Observes whether candidate can efficiently track the largest square while iterating through rectangles.
Tests whether candidate handles multiple rectangles producing the same largest square correctly.

Common Pitfalls or Variants

Common pitfalls

Forgetting to take min(length, width) and incorrectly using max or sum.
Not correctly counting all rectangles that match the largest square size.
Using nested loops unnecessarily instead of a single pass for max and count.

Follow-up variants

Return the indices of rectangles that can form the largest square instead of the count.
Allow rectangles to be rotated and compute largest square accordingly.
Find the second largest square and count rectangles that can form it.

FAQ

What is the main formula to determine the largest square from a rectangle?

Use min(length, width) for each rectangle to find the largest square side it can form.

Can rectangles with equal sides be ignored in this problem?

No, rectangles with equal sides are valid but the problem constraint li != wi means none are perfect squares initially.

How does the array-driven solution prevent unnecessary complexity?

By iterating through rectangles once to find max sides and once to count matches, we avoid nested loops or sorting.

What should I do if multiple rectangles yield the same largest square?

Count all rectangles whose min(length, width) equals the largest square side; this gives the correct total.

Is there a variant where rectangle rotation matters?

Yes, allowing rotation changes which min(length, width) is used and may affect which rectangles form the largest square.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

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 ans

Continue Practicing

#1726 tuple with same product #1723 find minimum time to finish all jobs #1727 largest submatrix with rearrangements