Leetcode 1725. Number Of Rectangles That Can Form The Largest Square

Problem:

Given an array of rectangles, each represented by its length and width, we need to find the maximum square side that can be obtained by cutting the given rectangles. Then, we need to count how many rectangles can be cut into squares of that maximum side.

Example:

Consider the following input:

1rectangles = [[5,8],[3,9],[5,12],[16,5]]

For each rectangle, we can find the largest square by taking the minimum of length and width:

• For [5,8], the largest square has a side length of 5.
• For [3,9], the largest square has a side length of 3.
• For [5,12], the largest square has a side length of 5.
• For [16,5], the largest square has a side length of 5.

The largest square side is 5, and there are 3 rectangles that can be cut into squares with side length 5. Thus, the output should be 3.

Approach:

To solve this problem, we can iterate through all the given rectangles and store the maximum square side as we go. We can also maintain a counter for the number of rectangles that can produce the maximum square side. Then, we simply return the counter as the final output.

Python Solution:

1class Solution:
2    def countGoodRectangles(self, rectangles):
3        max_side = 0
4        count = 0
5        
6        for rec in rectangles:
7            min_side = min(rec) # find the largest square of current rectangle
8            
9            if min_side > max_side: # update the maximum square side
10                max_side = min_side
11                count = 1
12            elif min_side == max_side: # increment the counter if the current rectangle produces the max square side
13                count += 1
14                
15        return count

Java Solution:

1class Solution {
2    public int countGoodRectangles(int[][] rectangles) {
3        int maxSide = 0;
4        int count = 0;
5
6        for (int[] rec : rectangles) {
7            int minSide = Math.min(rec[0], rec[1]); // find the largest square of current rectangle
8
9            if (minSide > maxSide) { // update the maximum square side
10                maxSide = minSide;
11                count = 1;
12            } else if (minSide == maxSide) { // increment the counter if the current rectangle produces the max square side
13                count++;
14            }
15        }
16        return count;
17    }
18}

JavaScript Solution:

1class Solution {
2    countGoodRectangles(rectangles) {
3        let maxSide = 0;
4        let count = 0;
5
6        for (const rec of rectangles) {
7            const minSide = Math.min(rec[0], rec[1]); // find the largest square of current rectangle
8
9            if (minSide > maxSide) { // update the maximum square side
10                maxSide = minSide;
11                count = 1;
12            } else if (minSide == maxSide) { // increment the counter if the current rectangle produces the max square side
13                count++;
14            }
15        }
16        return count;
17    }
18}

C++ Solution:

1class Solution {
2public:
3    int countGoodRectangles(vector<vector<int>>& rectangles) {
4        int maxSide = 0;
5        int count = 0;
6
7        for (const vector<int>& rec : rectangles) {
8            int minSide = min(rec[0], rec[1]); // find the largest square of current rectangle
9
10            if (minSide > maxSide) { // update the maximum square side
11                maxSide = minSide;
12                count = 1;
13            } else if (minSide == maxSide) { // increment the counter if the current rectangle produces the max square side
14                count++;
15            }
16        }
17        return count;
18    }
19};

C# Solution:

1public class Solution {
2    public int CountGoodRectangles(int[][] rectangles) {
3        int maxSide = 0;
4        int count = 0;
5
6        foreach (int[] rec in rectangles) {
7            int minSide = Math.Min(rec[0], rec[1]); // find the largest square of current rectangle
8
9            if (minSide > maxSide) { // update the maximum square side
10                maxSide = minSide;
11                count = 1;
12            } else if (minSide == maxSide) { // increment the counter if the current rectangle produces the max square side
13                count++;
14            }
15        }
16        return count;
17    }
18}

In conclusion, given an array of rectangles, we can find the maximum square side that can be obtained by cutting the rectangles by iterating through the array and storing the maximum square side and count of rectangles that can be cut into squares with that side length. Our solutions in Python, Java, JavaScript, C++, and C# all follow this approach, resulting in an efficient and effective method to solve this problem.