Problem Description

You are given a list of rectangles, where each rectangle is represented as a pair [length, width]. A rectangle can form a square if and only if both its length and width are at least as large as the side of the square. Your task is to determine how many rectangles from the list can form the largest possible square (i.e., the square with the maximum possible side length that can be formed from any rectangle in the list).

• Each rectangle is described by two positive integers: length and width.
• You may use each rectangle at most once.
• Your answer should be the number of rectangles that can form a square with the largest possible side length.
• Input is a list of rectangle dimensions, e.g., [[5,8],[3,9],[5,12],[16,5]].

Thought Process

At first glance, you might think you need to consider all possible square sizes for each rectangle. However, since we only care about the largest square that can be formed, we can simplify the problem. For each rectangle, the largest square it can form is determined by the smaller of its length and width. So, for each rectangle, we record side = min(length, width). Our goal is then to find the maximum value of side across all rectangles, and count how many rectangles have this value.

This leads to a two-step approach:

1. Compute the largest square side possible for each rectangle.
2. Find the maximum among these sides, and count how many rectangles achieve this maximum.

Solution Approach

Let's break down the solution into clear steps:

• Step 1: For each rectangle, calculate the largest square side it can form. This is simply min(length, width).
• Step 2: Track the maximum square side found so far.
• Step 3: Count the number of rectangles that can form a square of this maximum side length.

To implement this, you can use a single loop:

• Initialize max_side to 0 and count to 0.
• For each rectangle, compute side = min(length, width).
• If side > max_side, set max_side = side and reset count = 1.
• If side == max_side, increment count by 1.
• After processing all rectangles, count holds the answer.

This method is efficient, requiring only a single pass through the rectangles.

Example Walkthrough

Let's walk through the example input [[5,8],[3,9],[5,12],[16,5]]:

• First rectangle: [5,8] → min(5,8) = 5
• Second rectangle: [3,9] → min(3,9) = 3
• Third rectangle: [5,12] → min(5,12) = 5
• Fourth rectangle: [16,5] → min(16,5) = 5

The possible square sides are: [5, 3, 5, 5]. The largest is 5. There are 3 rectangles that can form a square of side 5 (the first, third, and fourth rectangles).

Thus, the answer is 3.

Code Implementation

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

class Solution {
public:
    int countGoodRectangles(vector<vector<int>>& rectangles) {
        int max_side = 0, count = 0;
        for (const auto& rect : rectangles) {
            int side = min(rect[0], rect[1]);
            if (side > max_side) {
                max_side = side;
                count = 1;
            } else if (side == max_side) {
                count++;
            }
        }
        return count;
    }
};
      

class Solution {
    public int countGoodRectangles(int[][] rectangles) {
        int maxSide = 0, count = 0;
        for (int[] rect : rectangles) {
            int side = Math.min(rect[0], rect[1]);
            if (side > maxSide) {
                maxSide = side;
                count = 1;
            } else if (side == maxSide) {
                count++;
            }
        }
        return count;
    }
}
      

var countGoodRectangles = function(rectangles) {
    let maxSide = 0, count = 0;
    for (let rect of rectangles) {
        let side = Math.min(rect[0], rect[1]);
        if (side > maxSide) {
            maxSide = side;
            count = 1;
        } else if (side === maxSide) {
            count++;
        }
    }
    return count;
};
      

Time and Space Complexity

• Brute-force approach: If you were to try every possible square side for every rectangle, it would be O(n) since you only need to check min(length, width) for each rectangle. No nested loops are needed.
• Optimized approach: The approach above is already optimal. It requires a single pass through the list, so the time complexity is O(n), where n is the number of rectangles.
• Space complexity: The solution uses only a constant amount of extra space, so O(1).

Summary

The key insight is that for each rectangle, the largest square it can form is determined by its smallest side. By tracking the maximum possible square side and counting how many rectangles achieve this, we reduce the problem to a simple pass through the list. This approach is both elegant and efficient, making it ideal for both interviews and production code.