# Number Of Rectangles That Can Form The Largest Square
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-of-rectangles-that-can-form-the-largest-square)
Canonical: https://scaleengineer.com/dsa/problems/number-of-rectangles-that-can-form-the-largest-square
**Data structures:** Array
---
## 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 <= 1000`
* `rectangles[i].length == 2`
* `1 <= li, wi <= 109`
* `li != wi`

# Approaches
## Store and Sort Approach
This approach involves calculating the maximum possible square side for each rectangle, storing these side lengths in a list, sorting the list, and then counting the occurrences of the largest value.
**Time:** O(N log N), where N is the number of rectangles. The dominant operation is sorting the list of side lengths. · **Space:** O(N), as we need an auxiliary list to store the side length for each of the N rectangles.
**Pros:** Conceptually simple and breaks the problem down into distinct, easy-to-understand steps (calculate, sort, count).
**Cons:** Requires extra space to store the side lengths.; The sorting step makes it less efficient than linear time approaches, especially for large inputs.
### Explanation
The core idea is to first transform the problem from dealing with rectangles to dealing with a simple list of numbers. For each rectangle `[l, w]`, the largest square that can be cut has a side length of `min(l, w)`. We compute this value for every rectangle and store it in an auxiliary array.

Once we have this array of possible side lengths, we can sort it in descending order. The largest possible side length, `maxLen`, will be the first element of the sorted array.

Finally, we iterate through the sorted array to count how many times `maxLen` appears. This count is our final answer.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int countGoodRectangles(int[][] rectangles) {
        List<Integer> sideLengths = new ArrayList<>();
        for (int[] rect : rectangles) {
            sideLengths.add(Math.min(rect[0], rect[1]));
        }

        Collections.sort(sideLengths, Collections.reverseOrder());

        if (sideLengths.isEmpty()) {
            return 0;
        }

        int maxLen = sideLengths.get(0);
        int count = 0;
        for (int side : sideLengths) {
            if (side == maxLen) {
                count++;
            } else {
                // Since the list is sorted, we can stop early
                break;
            }
        }
        return count;
    }
}
```
### Algorithm
- Create an empty list, `sideLengths`.
- Iterate through each `rectangle` in the input `rectangles` array.
- For each `rectangle`, calculate `side = min(rectangle[0], rectangle[1])`.
- Add `side` to the `sideLengths` list.
- Sort the `sideLengths` list in descending order.
- Get the `maxLen` which is the first element of the sorted list.
- Initialize a `count` to 0.
- Iterate through the `sideLengths` list. If an element is equal to `maxLen`, increment `count`. If it's smaller, break the loop (since the list is sorted).
- Return `count`.

## Two-Pass Linear Scan
This approach avoids sorting by iterating through the input array twice. The first pass finds the maximum possible square side length (`maxLen`), and the second pass counts how many rectangles can form a square of that size.
**Time:** O(N), where N is the number of rectangles. We perform two separate passes over the array, each taking O(N) time. The total time is O(N) + O(N) = O(N). · **Space:** O(1), as we only use a few variables to store `maxLen` and `count`, regardless of the input size.
**Pros:** More efficient than the sorting approach with a linear time complexity.; Uses constant extra space, making it memory-efficient.
**Cons:** Requires iterating through the input data twice, which is slightly less optimal than a single-pass solution.
### Explanation
Instead of storing all possible side lengths, we can find the maximum side length in one pass and then count its occurrences in a second pass. This eliminates the need for sorting and extra storage.

**First Pass:** We iterate through all the rectangles, calculating `min(l, w)` for each. We maintain a variable `maxLen` and update it whenever we find a side length greater than the current `maxLen`.

**Second Pass:** After the first pass, `maxLen` holds the side length of the largest possible square. We iterate through the rectangles again. This time, we count how many rectangles have `min(l, w)` equal to `maxLen`.

```java
class Solution {
    public int countGoodRectangles(int[][] rectangles) {
        int maxLen = 0;
        // First pass: find the maximum possible side length
        for (int[] rect : rectangles) {
            int side = Math.min(rect[0], rect[1]);
            if (side > maxLen) {
                maxLen = side;
            }
        }

        int count = 0;
        // Second pass: count rectangles that can form a square of maxLen
        for (int[] rect : rectangles) {
            if (Math.min(rect[0], rect[1]) == maxLen) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize `maxLen = 0`.
- **First Pass:** Iterate through each `rectangle` in `rectangles`.
  - Calculate `side = min(rectangle[0], rectangle[1])`.
  - Update `maxLen = max(maxLen, side)`.
- Initialize `count = 0`.
- **Second Pass:** Iterate through each `rectangle` in `rectangles`.
  - Calculate `side = min(rectangle[0], rectangle[1])`.
  - If `side == maxLen`, increment `count`.
- Return `count`.

## Single-Pass Optimization
This is the most efficient approach. It finds the `maxLen` and counts the rectangles in a single iteration over the input array, updating both values as it goes.
**Time:** O(N), where N is the number of rectangles. We iterate through the array only once. · **Space:** O(1), as we only use a constant number of variables (`maxLen`, `count`).
**Pros:** Most efficient approach with O(N) time complexity and O(1) space complexity.; Processes the data in a single pass, minimizing redundant computations.
**Cons:** The logic can be slightly more complex to reason about compared to the two-pass approach, as it involves updating two variables based on conditional logic within a single loop.
### Explanation
We can optimize the two-pass approach into a single pass. We maintain two variables: `maxLen` for the largest side length found so far, and `count` for the number of rectangles that can form a square of that `maxLen`.

As we iterate through the rectangles, we calculate the potential side length `side = min(l, w)` for the current rectangle. We then compare `side` with our current `maxLen`:
- If `side` is greater than `maxLen`, it means we've found a new, larger maximum side length. We must update `maxLen` to this new `side` and reset our `count` to 1, as this is the first rectangle we've seen for this new maximum size.
- If `side` is equal to the current `maxLen`, it means we've found another rectangle that can form a square of the same maximum size. We simply increment the `count`.
- If `side` is less than `maxLen`, this rectangle is not relevant to our count of the largest squares, so we ignore it.

This way, after iterating through the entire array just once, we will have the final correct count.

```java
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;
    }
}
```
### Algorithm
- Initialize `maxLen = 0` and `count = 0`.
- Iterate through each `rectangle` in the `rectangles` array.
- Calculate `side = min(rectangle[0], rectangle[1])`.
- If `side > maxLen`:
  - Update `maxLen = side`.
  - Reset `count = 1`.
- Else if `side == maxLen`:
  - Increment `count`.
- After the loop, return `count`.

# Solutions
### Java

```java
class Solution { public int countGoodRectangles ( int [][] rectangles ) { int ans = 0 , mx = 0 ; for ( var e : rectangles ) { int x = Math . min ( e [ 0 ], e [ 1 ]); if ( mx < x ) { mx = x ; ans = 1 ; } else if ( mx == x ) { ++ ans ; } } return ans ; } }
```

### CPP

```cpp
class Solution { public: int countGoodRectangles ( vector < vector < int >>& rectangles ) { int ans = 0 , mx = 0 ; for ( auto & e : rectangles ) { int x = min ( e [ 0 ], e [ 1 ]); if ( mx < x ) { mx = x ; ans = 1 ; } else if ( mx == x ) { ++ ans ; } } return ans ; } };
```

### Python

```python
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
```