1725. Number Of Rectangles That Can Form The Largest Square LeetCode Solution

In this guide, you will get 1725. Number Of Rectangles That Can Form The Largest Square LeetCode Solution with the best time and space complexity. The solution to Number Of Rectangles That Can Form The Largest Square problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Number Of Rectangles That Can Form The Largest Square solution in C++
4. Number Of Rectangles That Can Form The Largest Square solution in Java
5. Number Of Rectangles That Can Form The Largest Square solution in Python
6. Additional Resources

Problem Statement of Number Of Rectangles That Can Form The Largest Square

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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

1725. Number Of Rectangles That Can Form The Largest Square LeetCode Solution in C++

class Solution {
 public:
  int countGoodRectangles(vector<vector<int>>& rectangles) {
    vector<int> minSides;

    for (const vector<int>& rectangle : rectangles) {
      const int x = rectangle[0];
      const int y = rectangle[1];
      minSides.push_back(min(x, y));
    }

    const int maxLen = ranges::max(minSides);
    return ranges::count(minSides, maxLen);
  }
};
/* code provided by PROGIEZ */

1725. Number Of Rectangles That Can Form The Largest Square LeetCode Solution in Java

class Solution {
  public int countGoodRectangles(int[][] rectangles) {
    int[] minSides = new int[rectangles.length];

    for (int i = 0; i < rectangles.length; ++i) {
      final int x = rectangles[i][0];
      final int y = rectangles[i][1];
      minSides[i] = Math.min(x, y);
    }

    final int maxLen = Arrays.stream(minSides).max().getAsInt();
    return (int) Arrays.stream(minSides).filter(minSide -> minSide == maxLen).count();
  }
}
// code provided by PROGIEZ

1725. Number Of Rectangles That Can Form The Largest Square LeetCode Solution in Python

class Solution:
  def countGoodRectangles(self, rectangles: list[list[int]]) -> int:
    minSides = [min(x, y) for x, y in rectangles]
    return minSides.count(max(minSides))
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.