We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Pairs of Interchangeable Rectangles

Difficulty: Medium

Problem Description

You are given n rectangles represented by a 0-indexed 2D integer array rectangles, where rectangles[i] = [width_i, height_i] denotes the width and height of the i-th rectangle. Two rectangles i and j (i < j) are considered interchangeable if they have the same width-to-height ratio. More formally, two rectangles are interchangeable if width_i/height_i == width_j/height_j (using decimal division, not integer division). Return the number of pairs of interchangeable rectangles in rectangles.

Key Insights

  • Rectangles can be represented by their width-to-height ratio.
  • Ratios can be simplified to avoid floating-point inaccuracies.
  • Using a hashmap (or dictionary) to count occurrences of each unique ratio allows for efficient pair counting.
  • The number of interchangeable pairs for a given ratio with count occurrences can be calculated using the formula: count * (count - 1) / 2.

Space and Time Complexity

Time Complexity: O(n) - We traverse the list of rectangles once to compute ratios and count them. Space Complexity: O(n) - In the worst case, we store all unique ratios in the hashmap.

Solution

To solve this problem, we will use a hashmap (or dictionary) to store the count of each unique width-to-height ratio. For each rectangle, we will compute the ratio in its simplest form using the greatest common divisor (GCD). By counting the occurrences of each ratio, we can then compute the total number of interchangeable pairs using combinatorial counting.

Code Solutions

from collections import defaultdict
from math import gcd

def interchangeableRectangles(rectangles):
    ratio_count = defaultdict(int)
    
    for width, height in rectangles:
        # Simplify the ratio by using GCD
        common_divisor = gcd(width, height)
        simplified_ratio = (width // common_divisor, height // common_divisor)
        ratio_count[simplified_ratio] += 1
    
    # Count pairs
    pairs = 0
    for count in ratio_count.values():
        if count > 1:
            pairs += count * (count - 1) // 2
            
    return pairs
← Back to All Questions