algoadvance

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

Problem Statement

You are given an array rectangles where rectangles[i] = [li, wi] represents the length and width of the i-th rectangle.

A square can be formed with a side length of k if k <= li and k <= wi. The largest possible square has a side length equal to the minimum side length of any rectangle in the array.

Return the number of rectangles that can form the largest square.

Example 1:

Input: rectangles = [[5,8],[3,9],[5,12],[16,5]]
Output: 3
Explanation: The largest squares with side length 5 are formed by the rectangles [5,8], [5,12], and [16,5].

Example 2:

Input: rectangles = [[2,3],[3,7],[4,3],[3,7]]
Output: 3

Clarifying Questions

Before proceeding with coding, let’s clarify some questions to make sure the requirements are clear:

  1. Can the rectangles have different orientations (i.e., are [3, 4] and [4, 3] considered the same)?
  2. Are there any constraints on the values of li and wi or the number of rectangles?

Strategy

  1. Determine the maximum side length: Iterate through each rectangle and determine the minimum of its sides. Track the maximum of these minimum values, which will be the side length of the largest possible square.
  2. Count the rectangles: Iterate through the rectangles again to count how many have their minimum side at least as large as the maximum side length identified in step 1.

Code

Here’s the Java implementation:

public class Solution {
    public int countGoodRectangles(int[][] rectangles) {
        int maxSideLength = 0;
        int count = 0;

        // Find the maximum possible side length for a square
        for (int[] rectangle : rectangles) {
            int sideLength = Math.min(rectangle[0], rectangle[1]);
            maxSideLength = Math.max(maxSideLength, sideLength);
        }

        // Count the rectangles that can form the largest square with maxSideLength
        for (int[] rectangle : rectangles) {
            if (Math.min(rectangle[0], rectangle[1]) >= maxSideLength) {
                count++;
            }
        }

        return count;
    }
}

Time Complexity

The time complexity for this solution is O(n), where n is the number of rectangles. This is because we make two passes over the input array:

  1. The first pass to find the maximum possible side length.
  2. The second pass to count the rectangles that can form the largest square.

The space complexity is O(1) as we are using only a few extra variables.

This approach ensures we efficiently determine the correct number of rectangles that can form the largest possible square.

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