1725. Number Of Rectangles That Can Form The Largest Square
Problem Description
In the given problem, we are presented with an array named rectangles
, where each element rectangles[i]
represents the dimensions of the i
th rectangle as a pair [l_i, w_i]
indicating its length l_i
and width w_i
.
We are allowed to make cuts to these rectangles in order to form squares. A square can be formed from a rectangle if its side length k
is less than or equal to both the length and the width of the rectangle. For instance, from a rectangle [4,6]
, we can cut out a square with a maximum side length of 4
.
The objective is to find the side length of the largest square, maxLen
, that can be formed from these rectangles. Then we need to count the number of rectangles in the array that are capable of forming a square with this maximum side length.
To summarize, the task is to first determine the largest possible square side length that can be cut out from any of the rectangles, and then to count how many rectangles in the list are large enough to provide a square of that size.
Intuition
The solution involves a straightforward approach. Here's the process to understand how the solution works:
-
Initialize two variables
ans
andmx
to keep track of the count of rectangles that can produce the largest square, and to store the maximum square side length, respectively. -
Traverse through each rectangle in the
rectangles
array and for each rectangle, determine the side length of the largest possible square, which would be the minimum of the length and width of the rectangle as we are bound by the lesser dimension. This value is stored in a temporary variablet
. -
If we find a square side length
t
greater than the currentmx
, we know that we have found a new, larger square side length. So, we updatemx
to this new maximum side lengtht
, and resetans
to1
since this is the first rectangle that can form a square of side lengtht
. -
If
t
is equal tomx
, it means the current rectangle can also form a square of the largest side length found so far. Therefore, we incrementans
by1
to reflect this additional rectangle. -
If
t
is less thanmx
, we do nothing, as the rectangle cannot produce a square of side lengthmaxLen
. -
Once all rectangles have been processed,
ans
will contain the final count of rectangles that can produce squares of side lengthmx
, and we returnans
.
This solution works well because it efficiently iterates through the list only once, determines the maximum square side length in the process, and simultaneously counts the qualifying rectangles.
Solution Approach
The solution takes advantage of simple mathematical concepts and logical comparison within a single-pass for-loop to achieve the desired result.
Here's a step-by-step breakdown of the implementation details with reference to the solution code:
-
Initialize two variables,
ans
to store the number of rectangles that can form the largest square, initially set to 0, andmx
to store the maximum square side length possible, also initially set to 0.ans = mx = 0
-
We begin iterating over each rectangle provided in the
rectangles
list. Within the loop, we're performing the following steps for each rectangle:for l, w in rectangles:
-
Calculate the largest possible square side length
t
from the current rectangle by taking the minimum of its lengthl
and widthw
. This relies on the constraint that a square's side length must be less than or equal to the lengths of both sides of the rectangle.t = min(l, w)
-
Compare the calculated square side length
t
with the maximum found so far,mx
. Ift
is greater, we've discovered a new maximum square size. We then updatemx
to this new value, and setans
to 1 since this is the first occurrence of such a large square.if mx < t: mx, ans = t, 1
-
If
t
equals the current maximummx
, it means another rectangle was found which can form a square of the same maximum size. Hence we incrementans
by 1 without changingmx
.elif mx == t: ans += 1
-
If
t
is less thanmx
, that indicates the current rectangle cannot contribute to a square of side lengthmx
, so no operation is performed. -
After the loop completes, the variable
ans
contains the count of rectangles which can form the largest square, and this value is returned.return ans
In terms of algorithms and data structures, this solution is a straight-forward linear scan (O(n) complexity) without the need for any additional complex data structures. The use of basic variables and a single for-loop makes the code efficient and easy to understand. This elegant simplicity arises from the observation that we're interested only in the counts related to the maximum square size which can be maintained and updated on-the-fly as we inspect each rectangle.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider the following array of rectangles: rectangles = [[3, 5], [6, 6], [5, 2], [4, 4]]
. We need to determine the largest square side length we can cut from any rectangle and then count how many rectangles can form a square of that size.
-
We initialize
ans
andmx
to0
. These will keep track of the count and size of the largest square, respectively. -
We begin iterating over each rectangle:
-
For the first rectangle
[3, 5]
, the largest square side lengtht
we can cut ismin(3, 5) = 3
. Since3
is greater than the currentmx
(0), we updatemx
to3
and setans
to1
. -
Moving on to the second rectangle
[6, 6]
,t = min(6, 6) = 6
. This is greater than the currentmx
(3), somx
is updated to6
andans
is reset to1
. -
For the third rectangle
[5, 2]
,t = min(5, 2) = 2
. This is less than the currentmx
(6), so no changes are made tomx
orans
. -
The last rectangle
[4, 4]
also provides a square witht = min(4, 4) = 4
, which is still less than ourmx
(6), so again no changes are made tomx
orans
.
-
-
After completing the loop,
mx
is6
andans
is1
, since only one rectangle,[6, 6]
, could produce a square with the largest possible side length. Hence, the function would return1
.
This example demonstrates the straightforward linear scan through the array and the simple tracking of the maximum square side length and the count of rectangles that could form a square of that maximum size.
Solution Implementation
1from typing import List
2
3class Solution:
4 def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
5 # Initialize maximum square length and count of good rectangles
6 max_square_length = 0
7 good_rectangles_count = 0
8
9 # Loop through each rectangle to find the maximum square length
10 for length, width in rectangles:
11 # Find the smaller of the two sides to get the largest possible square
12 side_length = min(length, width)
13
14 # If the current square length is greater than the previous maximum,
15 # update max_square_length and reset good_rectangles_count
16 if side_length > max_square_length:
17 max_square_length = side_length
18 good_rectangles_count = 1
19 # If the current square length is equal to the maximum,
20 # increment the count of good rectangles
21 elif side_length == max_square_length:
22 good_rectangles_count += 1
23
24 # Return the total count of rectangles that can produce the largest square
25 return good_rectangles_count
26
1class Solution {
2 public int countGoodRectangles(int[][] rectangles) {
3 int countOfMaxSquares = 0; // This will keep track of how many maximum squares we can cut.
4 int maxSize = 0; // This will keep the maximum square size we can get.
5
6 // Loop through each rectangle.
7 for (int[] rectangle : rectangles) {
8 // Find the size of the largest square that fits within the rectangle.
9 // This is the smaller side of the rectangle.
10 int largestSquareSize = Math.min(rectangle[0], rectangle[1]);
11
12 // If we found a larger square size than we've seen so far,
13 // update the maximum size and reset the count of max squares.
14 if (maxSize < largestSquareSize) {
15 maxSize = largestSquareSize;
16 countOfMaxSquares = 1;
17 } else if (maxSize == largestSquareSize) {
18 // If we found a square with a size equal to the current maximum,
19 // increment the count of max size squares.
20 ++countOfMaxSquares;
21 }
22 }
23
24 // After checking all rectangles, return the count of the largest squares.
25 return countOfMaxSquares;
26 }
27}
28
1#include <vector> // Include necessary library for vector
2#include <algorithm> // Include for access to the min function
3
4class Solution {
5public:
6 int countGoodRectangles(std::vector<std::vector<int>>& rectangles) {
7 int maxSquareLen = 0; // Variable to store the maximum square length
8 int goodRectanglesCount = 0; // Variable to count the number of good rectangles
9
10 // Iterate over each rectangle in the input vector
11 for (const std::vector<int>& rect : rectangles) {
12 // Calculate the maximum square length that can be cut out of the current rectangle
13 int squareLen = std::min(rect[0], rect[1]);
14
15 // If the current square length is greater than maxSquareLen, update maxSquareLen
16 // and reset goodRectanglesCount since we have found a larger square
17 if (squareLen > maxSquareLen) {
18 maxSquareLen = squareLen;
19 goodRectanglesCount = 1; // Start counting from one as this is the new largest square
20 }
21 // If the current square length is equal to maxSquareLen, increment the count
22 else if (squareLen == maxSquareLen) {
23 ++goodRectanglesCount;
24 }
25 }
26
27 // After iterating through all rectangles, return the count of good rectangles
28 return goodRectanglesCount;
29 }
30};
31
1// Function to count the number of rectangles that can form a square with the largest side
2function countGoodRectangles(rectangles: number[][]): number {
3 let maxSquareSide = 0; // Initialize a variable to keep track of the maximum square side length
4 let squareCount = 0; // Initialize a counter to keep track of the number of squares with maxSquareSide
5
6 // Loop through each rectangle
7 for (let [length, width] of rectangles) {
8 // Find the minimum side to determine the size of the largest square
9 let largestSquareSide = Math.min(length, width);
10
11 // If the current square's side is equal to the maximum found so far, increment the count
12 if (largestSquareSide == maxSquareSide) {
13 squareCount++;
14 } else if (largestSquareSide > maxSquareSide) {
15 // If current square's side is larger, update the maximum side and reset the count
16 maxSquareSide = largestSquareSide;
17 squareCount = 1;
18 }
19 }
20
21 // After looping through all rectangles, return the count of squares with the largest side
22 return squareCount;
23}
24
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(n)
, where n
is the number of rectangles in the input list rectangles
. This is because the code iterates through each rectangle exactly once, and for each rectangle, it performs a constant number of operations: calculating the minimum of the length and width, comparison, and possibly incrementing the answer or updating the maximum length of a square.
Space Complexity
The space complexity of the code is O(1)
. This is because the code only uses a fixed amount of additional space: two variables (ans
and mx
). The amount of space used does not depend on the input size, so the space complexity is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a min heap?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!