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 _thenumber of rectangles that can make a square with a side length of _maxLen.

Examples

Example 1

1
2
3
4

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

1
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 <= 10^9
  • li != wi

Solution

Method 1 – Find Max and Count

Intuition

For each rectangle, the largest square you can cut has side length equal to the minimum of its two sides. We find the maximum such value among all rectangles, then count how many rectangles can form a square of that size.

Approach

  1. For each rectangle, compute min(l, w).
  2. Find the maximum value among all these minimums (maxLen).
  3. Count how many rectangles have min(l, w) == maxLen.
  4. Return the count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int countGoodRectangles(vector<vector<int>>& rectangles) {
        int maxLen = 0, ans = 0;
        for (auto& r : rectangles) {
            int side = min(r[0], r[1]);
            if (side > maxLen) { maxLen = side; ans = 1; }
            else if (side == maxLen) ++ans;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func countGoodRectangles(rectangles [][]int) int {
    maxLen, ans := 0, 0
    for _, r := range rectangles {
        side := r[0]
        if r[1] < side { side = r[1] }
        if side > maxLen {
            maxLen, ans = side, 1
        } else if side == maxLen {
            ans++
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int countGoodRectangles(int[][] rectangles) {
        int maxLen = 0, ans = 0;
        for (int[] r : rectangles) {
            int side = Math.min(r[0], r[1]);
            if (side > maxLen) {
                maxLen = side; ans = 1;
            } else if (side == maxLen) {
                ans++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun countGoodRectangles(rectangles: Array<IntArray>): Int {
        var maxLen = 0
        var ans = 0
        for (r in rectangles) {
            val side = minOf(r[0], r[1])
            if (side > maxLen) {
                maxLen = side; ans = 1
            } else if (side == maxLen) {
                ans++
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def countGoodRectangles(self, rectangles: list[list[int]]) -> int:
        maxLen = 0
        ans = 0
        for l, w in rectangles:
            side = min(l, w)
            if side > maxLen:
                maxLen = side
                ans = 1
            elif side == maxLen:
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn count_good_rectangles(rectangles: Vec<Vec<i32>>) -> i32 {
        let mut max_len = 0;
        let mut ans = 0;
        for r in rectangles {
            let side = r[0].min(r[1]);
            if side > max_len {
                max_len = side;
                ans = 1;
            } else if side == max_len {
                ans += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    countGoodRectangles(rectangles: number[][]): number {
        let maxLen = 0, ans = 0;
        for (const [l, w] of rectangles) {
            const side = Math.min(l, w);
            if (side > maxLen) {
                maxLen = side; ans = 1;
            } else if (side === maxLen) {
                ans++;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of rectangles. We scan the list once.
  • 🧺 Space complexity: O(1), as we use only a constant amount of extra space.