algoadvance

You are given an array of rectangles where rectangles[i] = [li, wi] represents the dimensions of the i-th rectangle on a flat plane.

You can rotate the rectangle any number of times, i.e., swap its width and height. Your task is to determine the largest square side length that can be obtained from the given rectangles and count how many rectangles can make such a square.

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

Clarifying Questions

  1. Can the rectangles have equal lengths and widths (i.e., already squares)?
    • Yes, rectangles can already be squares.
  2. Are all dimensions positive integers?
    • Yes, all dimensions are positive integers.
  3. What is the range of the dimensions of the rectangles?
    • The dimensions range from 1 to 10^5.
  4. How many rectangles can we expect in the input?
    • The number of rectangles, n, can be up to 1000.

Strategy

  1. Determine the largest possible square side length for each rectangle.
    • For a rectangle [li, wi], the largest side length of a square that can be formed is min(li, wi).
  2. Track the maximum square side length.
    • As we go through each rectangle, we keep track of the largest square side length encountered.
  3. Count the rectangles that can form the largest square.
    • Once the maximum square side length is determined, count how many rectangles can achieve that square side length.

Code

def countGoodRectangles(rectangles):
    max_side_length = 0
    count = 0
    
    for l, w in rectangles:
        square_side = min(l, w)
        if square_side > max_side_length:
            max_side_length = square_side
            count = 1
        elif square_side == max_side_length:
            count += 1
            
    return count

# Example usage:
rectangles = [[5,8], [3,9], [5,12], [16,5]]
print(countGoodRectangles(rectangles))  # Output: 3

Time Complexity

Explanation

  1. Iteration through rectangles:
    • For each rectangle, compute the potential side length of the square (min(l, w)).
    • Track the maximum side length.
    • If a new maximum is found, reset the count.
    • If the current side length matches the maximum, increment the count.
  2. Return the count of rectangles that can form the largest square.

Try our interview co-pilot at AlgoAdvance.com