- Published on

# Number Of Rectangles That Can Form The Largest Square.

- Authors
- Name
- Pankaj Tanwar
- @the2ndfloorguy

Hey-yo, It's day #13 of my coding diary.

**Problem of the day** - Number Of Rectangles That Can Form The Largest Square

**Tag** - Easy

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`

.As I read the problem statement, I could feel my approach running into my mind. It was pretty straight forward.

- loop over the rectangles array and store the max possible length of square from each rectangle (which would be the minimum of rectangles' length)
- Keep on pushing the square length to array and keep tracking the maximum of all squares
- Finally, just check how many times the maximum square came and return that output

**My code (version 1) was this** -

`class Solution {public: int countGoodRectangles(vector<vector<int>>& rectangles) { vector<int> squares; int maximum_size = INT_MIN; int res = 0; for(auto rect: rectangles) { int sq = min(rect[0], rect[1]); squares.push_back(sq); maximum_size = max(maximum_size, sq); } for(auto val: squares) { if(val == maximum_size) res++; } return res; }};`

Upon submission, runtime and memory stats opened my eyes. It was super slow and using extra memory.

I began finding the bottleneck in order to improve my code. I was able to think of -

- Maintaining an extra array (
`squares`

), just to find the count of maximum length square was the dumbest thing I could do. - If I can somehow, reduce it to one for loop only, I can save enough on runtime.

After some sketches on my rough book, I was able to come up with this solution -

```
class Solution {public: int countGoodRectangles(vector<vector<int>>& rectangles) { int maximum_size = INT_MIN; int res = 0; for(auto rect: rectangles) { int sq = min(rect[0], rect[1]); if(maximum_size == sq) res++; if(sq > maximum_size) { maximum_size = sq; res = 1; } }
return res; }};
```

Voilà. I just removed `one extra array`

and `an extra for loop`

. Run time and memory usage leetcode stats are pretty good now.

You might like previous editions of my coding diary