Problem Description

You are given n rectangles, where each rectangle is defined by its width and height. The rectangles are stored in a 2D array called rectangles, where rectangles[i] = [width_i, height_i] represents the width and height of the i-th rectangle.

Two rectangles are considered interchangeable if they have the same width-to-height ratio. In other words, rectangles i and j (where i < j) are interchangeable if width_i/height_i == width_j/height_j using decimal division.

Your task is to count how many pairs of interchangeable rectangles exist in the given array.

For example:

• A rectangle with width 4 and height 8 has a ratio of 4/8 = 0.5
• A rectangle with width 2 and height 4 has a ratio of 2/4 = 0.5
• These two rectangles would be interchangeable and form one pair

The solution uses the mathematical approach of reducing each ratio to its simplest form by dividing both width and height by their greatest common divisor (GCD). This allows for accurate comparison of ratios without floating-point precision issues. A hash table tracks rectangles with the same simplified ratio, and for each new rectangle with a matching ratio, the count of existing rectangles with that ratio gives the number of new pairs formed.

Intuition

The key insight is that comparing floating-point ratios directly can lead to precision errors. For instance, 1/3 and 2/6 should be equal, but floating-point division might give slightly different results due to rounding errors.

To avoid this issue, we need a way to represent each ratio uniquely and accurately. The mathematical approach is to reduce each fraction to its simplest form. For example, 4/8, 2/4, and 1/2 all represent the same ratio and should be reduced to 1/2.

We achieve this by finding the greatest common divisor (GCD) of the width and height, then dividing both by this GCD. After simplification, rectangles with the same ratio will have identical (width, height) pairs. For instance:

• Rectangle [4, 8] → GCD = 4 → Simplified to (1, 2)
• Rectangle [10, 20] → GCD = 10 → Simplified to (1, 2)
• Rectangle [3, 6] → GCD = 3 → Simplified to (1, 2)

All three rectangles reduce to the same simplified form (1, 2), indicating they're interchangeable.

For counting pairs, when we encounter a rectangle with a ratio we've seen before, it can form pairs with all previously seen rectangles having the same ratio. If we've already seen k rectangles with a particular ratio, a new rectangle with that ratio forms k new pairs. This is why we maintain a counter: as we process each rectangle, we add the current count for its ratio to our answer, then increment the count for future rectangles.

Learn more about Math patterns.

Solution Approach

The implementation follows these steps:

1. Initialize variables:

   • ans = 0 to store the total number of interchangeable pairs
   • cnt = Counter() - a hash table to track the count of each simplified ratio

2. Process each rectangle: For each rectangle [w, h] in the input:

   a. Calculate the GCD: Find g = gcd(w, h) to determine the greatest common divisor of width and height

   b. Simplify the ratio: Divide both dimensions by the GCD to get the simplified form:

   • w = w // g
   • h = h // g

   c. Count pairs: Before adding the current rectangle, check how many rectangles with the same simplified ratio (w, h) we've already seen. Each of these can form a pair with the current rectangle, so add cnt[(w, h)] to our answer

   d. Update counter: Increment the count for this simplified ratio: cnt[(w, h)] += 1

3. Return the result: After processing all rectangles, ans contains the total number of interchangeable pairs

Example walkthrough: Consider rectangles [[4,8], [3,6], [10,20], [15,30]]:

• Rectangle [4,8]: GCD=4, simplified to (1,2), pairs=0, update cnt[(1,2)]=1
• Rectangle [3,6]: GCD=3, simplified to (1,2), pairs=1 (forms 1 pair with first), update cnt[(1,2)]=2
• Rectangle [10,20]: GCD=10, simplified to (1,2), pairs=2 (forms 2 pairs with first two), update cnt[(1,2)]=3
• Rectangle [15,30]: GCD=15, simplified to (1,2), pairs=3 (forms 3 pairs with first three), update cnt[(1,2)]=4
• Total pairs = 0 + 1 + 2 + 3 = 6

The time complexity is O(n × log(min(w, h))) where the log factor comes from the GCD calculation, and space complexity is O(n) for the hash table.

Example Walkthrough

Let's walk through a small example with rectangles [[4,8], [6,3], [2,4], [9,12]].

Step 1: Process rectangle [4,8]

• Calculate GCD(4,8) = 4
• Simplify: 4÷4 = 1, 8÷4 = 2 → simplified ratio is (1,2)
• Check counter: cnt[(1,2)] = 0, so no pairs formed yet
• Update counter: cnt[(1,2)] = 1
• Running total pairs = 0

Step 2: Process rectangle [6,3]

• Calculate GCD(6,3) = 3
• Simplify: 6÷3 = 2, 3÷3 = 1 → simplified ratio is (2,1)
• Check counter: cnt[(2,1)] = 0, so no pairs formed
• Update counter: cnt[(2,1)] = 1
• Running total pairs = 0

Step 3: Process rectangle [2,4]

• Calculate GCD(2,4) = 2
• Simplify: 2÷2 = 1, 4÷2 = 2 → simplified ratio is (1,2)
• Check counter: cnt[(1,2)] = 1 (we've seen this ratio once before!)
• This rectangle forms 1 pair with the first rectangle [4,8]
• Update counter: cnt[(1,2)] = 2
• Running total pairs = 0 + 1 = 1

Step 4: Process rectangle [9,12]

• Calculate GCD(9,12) = 3
• Simplify: 9÷3 = 3, 12÷3 = 4 → simplified ratio is (3,4)
• Check counter: cnt[(3,4)] = 0, so no pairs formed
• Update counter: cnt[(3,4)] = 1
• Running total pairs = 1

Final Result: 1 interchangeable pair exists (rectangles [4,8] and [2,4])

The key insight: When we encounter a simplified ratio we've seen k times before, the current rectangle forms k new pairs with those previous rectangles.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log M)

For each of the n rectangles, the algorithm performs:

• Computing the GCD of width w and height h using the Euclidean algorithm, which takes O(log M) time where M is the maximum value between width and height
• Integer division operations to normalize the rectangle dimensions: O(1)
• Dictionary lookup and update operations: O(1) on average
• Counter increment operation: O(1)

Since we iterate through all n rectangles and the GCD computation dominates with O(log M) time per rectangle, the overall time complexity is O(n × log M).

Space Complexity: O(n)

The space is used for:

• The Counter dictionary cnt which stores normalized rectangle ratios as keys
• In the worst case, all rectangles have unique normalized ratios (no interchangeable pairs)
• This means the dictionary could store up to n unique entries

Therefore, the space complexity is O(n) where n is the number of rectangles.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Floating-Point Precision Issues

A common mistake is directly comparing floating-point ratios instead of using the GCD approach:

Incorrect approach:

def interchangeableRectangles(self, rectangles):
    total_pairs = 0
    ratio_counter = Counter()
  
    for width, height in rectangles:
        # WRONG: Using floating-point division
        ratio = width / height  
        total_pairs += ratio_counter[ratio]
        ratio_counter[ratio] += 1
  
    return total_pairs

Why it fails: Floating-point arithmetic can introduce precision errors. For example:

• 4/14 might produce 0.2857142857142857
• 2/7 might produce 0.2857142857142857 or 0.28571428571428575
• These should be equal but might not match due to precision issues

Solution: Always use the GCD approach to reduce ratios to their simplest integer form (width//gcd, height//gcd).

2. Integer Division Confusion

Using integer division (//) to calculate the ratio directly:

Incorrect approach:

ratio = width // height  # WRONG: Loses precision

Why it fails: Integer division loses all decimal information. Rectangles [3,2] and [5,3] would both have ratio 1, but they're not actually interchangeable (1.5 ≠ 1.667).

3. Not Handling Edge Cases

Failing to consider special cases like:

• Very large numbers that might cause overflow in some languages
• Rectangles where width or height could be 1 (though the problem constraints typically prevent zero values)

Solution: The GCD approach naturally handles these cases by keeping numbers as small as possible through reduction.

4. Incorrect Pair Counting Logic

A subtle but critical mistake is counting pairs incorrectly:

Incorrect approach:

for width, height in rectangles:
    g = gcd(width, height)
    normalized = (width // g, height // g)
    ratio_counter[normalized] += 1
    total_pairs += ratio_counter[normalized] - 1  # WRONG ORDER

Why it fails: This increments the counter before calculating pairs, leading to off-by-one errors. You must add the current count (number of existing rectangles with this ratio) before incrementing.

Correct order:

1. Add ratio_counter[normalized] to total (these are new pairs formed)
2. Then increment ratio_counter[normalized] += 1