46. Number of Rectangles That Can Form Largest Square

You are given an array rectangles where rectangles[i]=[li,wi]. You can cut the i-th rectangle to make a square with side min(li,wi). Return the number of rectangles that can form the largest possible square.

Input: A 2D array rectangles where each element is [length, width].

Output: Integer — count of rectangles that can produce the largest square.

Examples

Input: [[5,8],[3,9],[5,12],[16,5]]
Output: 3
Explanation: Max square side = max(min(r)) = max(5,3,5,5) = 5. Rectangles with min>=5: [5,8],[5,12],[16,5] → 3.

Input: [[2,3],[3,7],[4,3],[3,7]]
Output: 3
Explanation: min values: 2,3,3,3. Max=3. Count with min>=3: 3.

Input: [[1,1]]
Output: 1
Explanation: Only one rectangle, max square side=1. Count=1.

Constraints

• 1<=rectangles.length<=1000
• 1<=li,wi<=10^9
• rectangles[i].length==2

Asked by