Number of Rectangles That Can Form the Largest Square

You are given an array rectangles where rectangles[i] = [l_i, w_i] represents a rectangle with length l_i and width w_i. You can cut a square from any rectangle as long as the square's side length does not exceed either dimension. Find the largest square side length you can cut from any rectangle, then return how many rectangles can produce a square of that size.

This is LeetCode 1725: Number of Rectangles That Can Form the Largest Square, and it is a clean single-pass problem once you see the core observation.

Why this problem matters

This problem is a great warm-up for recognizing when a two-pass approach (find the max, then count it) can be collapsed into a single pass. That optimization shows up in dozens of problems: find the maximum subarray, find the majority element, find the longest consecutive sequence. The pattern of tracking both "the best value so far" and "how many times you have seen it" in one loop is a reusable building block worth drilling.

It also reinforces the idea of reducing a 2D problem to a 1D problem. Each rectangle has two dimensions, but the relevant information is a single number: min(l, w). Spotting that reduction is the key insight.

The key insight

The largest square you can cut from a rectangle with dimensions l by w has side length min(l, w). You are limited by the shorter side. Once you compute min(l, w) for every rectangle, the problem reduces to: find the maximum value in an array and count how many times it appears.

You can do this in one pass. Track the current maximum side length and a count. For each rectangle, compute min(l, w). If it is larger than the current max, update the max and reset the count to 1. If it equals the current max, increment the count. If it is smaller, skip it.

The solution

def countGoodRectangles(rectangles):
    max_len = 0
    count = 0
    for l, w in rectangles:
        side = min(l, w)
        if side > max_len:
            max_len = side
            count = 1
        elif side == max_len:
            count += 1
    return count

Here is what each piece does:

1. max_len tracks the largest square side found so far. count tracks how many rectangles can produce that square.
2. For each rectangle, compute side = min(l, w), which is the biggest square that fits inside it.
3. If side beats the current best, we have found a new largest square. Reset count to 1 and update max_len.
4. If side ties the current best, increment count.
5. After processing all rectangles, count holds the answer.

Visual walkthrough

Let's trace through rectangles = [[5,8],[3,9],[5,12],[16,5]] step by step. For each rectangle, we compute min(l, w) and update our running max and count.

Three out of four rectangles can form a 5x5 square. Only [3, 9] falls short because min(3, 9) = 3, which is less than 5. The answer is 3.

Complexity analysis

Time: One loop through all n rectangles. Each iteration does a constant amount of work (one min, one comparison). Total: O(n).

Space: Two integer variables (max_len and count). No extra data structures. Total: O(1).

This is optimal. You must look at every rectangle at least once to know which ones contribute the largest square, so O(n) is the lower bound.

The building blocks

1. Reduce dimensions with min/max

The pattern of collapsing a multi-dimensional input into a single relevant value appears in many problems. Here, each [l, w] pair reduces to min(l, w). In other problems, you might compute max(a, b), abs(a - b), or a + b to extract the quantity you actually care about. The idea is the same: identify which single number captures the constraint, then work with that.

for l, w in rectangles:
    side = min(l, w)

2. Track max and count in one pass

Instead of first finding the maximum and then counting it in a second pass, you can do both simultaneously. When you see a new max, reset the count. When you see a tie, increment the count. This pattern works anywhere you need "find the best value and how many times it occurs."

max_val = 0
count = 0
for val in values:
    if val > max_val:
        max_val = val
        count = 1
    elif val == max_val:
        count += 1

Edge cases

• All rectangles are squares [[5,5],[3,3],[5,5]]: min(l, w) equals both dimensions. The algorithm works identically. Result: max side = 5, count = 2.
• Single rectangle [[7,4]]: only one rectangle, so it always produces the largest square. min(7, 4) = 4, count = 1.
• All rectangles have the same min side [[3,10],[5,3],[3,3]]: all reduce to 3. The count equals the number of rectangles (3).
• Very large rectangles [[10000, 1]]: min(10000, 1) = 1. A long, thin rectangle can only produce a tiny square.
• One dimension equals the other [[4,4]]: a perfect square. min(4, 4) = 4. Works fine.

From understanding to recall

You have seen how this problem boils down to one min call per rectangle and a running max with a count. The logic is short. But in an interview, the small details matter: initializing max_len and count correctly, handling the "greater than" versus "equal to" branches, and remembering to reset the count (not increment it) when a new max appears.

Spaced repetition makes these details automatic. You practice writing the single-pass max-count loop from scratch at increasing intervals. After a few rounds, you do not need to think about the branches. You just write them.

The "track max and count in one pass" pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Contains Duplicate - Another array problem where the core operation is scanning for a specific property across all elements
• Maximum Subarray - Uses a similar "track the best so far" pattern, but with a running sum instead of a running count
• Best Time to Buy and Sell Stock - Single-pass tracking of a running minimum and best profit, the same "one loop, two variables" template

CodeBricks breaks the Number of Rectangles That Can Form the Largest Square problem into its dimension reduction and max-count tracking building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a "find the best and count it" question shows up in your interview, you do not hesitate. You just write it.