LeetCode 1725: Number Of Rectangles That Can Form The Largest Square

Explanation

To solve this problem, we need to find the maximum side length possible for a square that can be formed from the given rectangles and then count how many rectangles can form a square of that side length. We can achieve this by iterating through all the rectangles, finding the minimum side length of each rectangle, and then keeping track of the maximum of these minimum side lengths. Finally, we count how many rectangles have a side length equal to the maximum side length found.

• Algorithm:

  1. Initialize maxLen to store the maximum side length found.
  2. Iterate through all rectangles and find the minimum side length of each rectangle.
  3. Update maxLen with the maximum of the minimum side lengths found.
  4. Iterate through the rectangles again and count how many rectangles have a side length equal to maxLen.
  5. Return the count as the result.

• Time Complexity: O(n) where n is the number of rectangles.

• Space Complexity: O(1) as we are using constant extra space.

class Solution {
    public int countGoodRectangles(int[][] rectangles) {
        int maxLen = 0;
        int count = 0;
        
        for (int[] rect : rectangles) {
            int minSide = Math.min(rect[0], rect[1]);
            maxLen = Math.max(maxLen, minSide);
        }
        
        for (int[] rect : rectangles) {
            if (Math.min(rect[0], rect[1]) == maxLen) {
                count++;
            }
        }
        
        return count;
    }
}