algoadvance

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

Problem Statement

You are given an array of rectangles represented by a 2D array rectangles where rectangles[i] = [li, wi] denotes the length and width of the i-th rectangle. You need to find the number of rectangles that can form the largest square.

A rectangle can form a square if and only if at least one of its sides is the length of the largest square possible.

Clarifying Questions

  1. Input Sizes: What is the maximum number of rectangles we can expect in the rectangles array?
  2. Equal Length and Width: If a rectangle has dimensions [3, 3], does it count as forming a square of size 3?
  3. Side Restrictions: Should we consider both length and width for forming the largest square, or is it only the smaller side of the rectangle that should be considered?

Example

Given rectangles = [[2, 3], [3, 7], [4, 3], [3, 3]], the output should be 3. This is because the largest square possible is of side 3, and there are three rectangles that can form this square: [3, 7], [4, 3], [3, 3].

Strategy

  1. Finding the Maximum Square Size: Determine the maximum side length that can form a square. This would be the minimum of li and wi for each rectangle.
  2. Counting Rectangles: Count how many rectangles have this maximum possible side length.

Time Complexity

The time complexity for this approach is O(n), where n is the number of rectangles. We iterate through the list twice: once to find the maximum side length and once to count the rectangles that can form a square with that side length.

Code

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

class Solution {
public:
    int countGoodRectangles(vector<vector<int>>& rectangles) {
        int maxLen = 0;
        
        // Step 1: Find the longest possible side length of a square
        for (const auto& rectangle : rectangles) {
            int sideLen = min(rectangle[0], rectangle[1]);
            maxLen = max(maxLen, sideLen);
        }
        
        // Step 2: Count how many rectangles can form the largest square
        int count = 0;
        for (const auto& rectangle : rectangles) {
            if (min(rectangle[0], rectangle[1]) == maxLen) {
                ++count;
            }
        }
        
        return count;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> rectangles1 = \{\{2, 3}, {3, 7}, {4, 3}, {3, 3}};
    cout << sol.countGoodRectangles(rectangles1) << endl; // Output: 3

    vector<vector<int>> rectangles2 = \{\{5, 8}, {3, 9}, {5, 12}, {16, 5}};
    cout << sol.countGoodRectangles(rectangles2) << endl; // Output: 3
    
    return 0;
}

Explanation of the Code

  1. Finding the Largest Square Side: We first iterate through all rectangles to find the maximum possible side length using min(li, wi).
  2. Counting Rectangles: Next, we iterate again to count how many rectangles can form a square of this maximum side length.
  3. Result: We return the count obtained from the second step.

This approach ensures we efficiently find and count the rectangles capable of forming the largest possible square.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI