LeetCode Solutions Blog

Number of Pairs of Interchangeable Rectangles

Number: 2129

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an array of rectangles where each rectangle is represented by its [width, height], count the number of pairs (i, j) with i < j such that the two rectangles have the same width-to-height ratio.

Key Insights

Two rectangles are interchangeable if width/height ratios are identical.
To avoid floating point precision issues, the ratio can be represented as a reduced fraction.
Use a hash map (dictionary) to count occurrences of each ratio.
For each group of rectangles with the same ratio, the number of pairs is computed using the combination formula: n*(n-1)/2.

Space and Time Complexity

Time Complexity: O(n * log(max(width, height))) due to the gcd computation for each rectangle. Space Complexity: O(n) for storing counts in the hash map.

Solution

We iterate through each rectangle and use the greatest common divisor (gcd) to reduce the ratio (width, height) to its simplest form. This reduced form is used as a key in a hash map. After counting the occurrences for each unique ratio, we compute the number of pairs using the formula n*(n-1)/2 for each ratio count greater than one. The summation of all these pairs is the answer.

Code Solutions

# Import gcd from math module for reducing fractions
from math import gcd
from collections import defaultdict

def interchangeableRectangles(rectangles):
    # Dictionary to count occurrences of each reduced ratio
    ratio_counts = defaultdict(int)
    
    # Iterate over each rectangle
    for width, height in rectangles:
        # Calculate greatest common divisor to reduce the fraction
        common_divisor = gcd(width, height)
        # Create a tuple representing the reduced ratio
        reduced_ratio = (width // common_divisor, height // common_divisor)
        # Increment the count for this ratio
        ratio_counts[reduced_ratio] += 1
    
    # Initialize result counter
    result = 0
    # Calculate number of interchangeable pairs for each ratio group
    for count in ratio_counts.values():
        if count > 1:
            result += count * (count - 1) // 2
    return result

# Example usage:
rectangles = [[4,8],[3,6],[10,20],[15,30]]
print(interchangeableRectangles(rectangles))  # Expected output: 6