Pankaj Tanwar
Published on

Number Of Rectangles That Can Form The Largest Square.

––– views

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

Tweet this article