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 of5
. - For
[3,9]
, the largest square has a side length of3
. - For
[5,12]
, the largest square has a side length of5
. - For
[16,5]
, the largest square has a side length of5
.
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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.