Number of Pairs of Interchangeable Rectangles - Video Solutions

Problem Overview: You receive a list of rectangles where each rectangle is defined by [width, height]. Two rectangles are interchangeable if their width-to-height ratios are equal. The task is to count how many pairs (i, j) exist such that both rectangles share the same ratio.

The key observation is that interchangeable rectangles share the same proportional relationship between width and height. Instead of comparing every pair directly, convert each rectangle into a ratio representation and count how often each ratio appears.

Approach 1: Brute Force Pair Comparison (O(n²) time, O(1) space)

Compare every pair of rectangles using two nested loops. For rectangles (w1, h1) and (w2, h2), check whether w1 * h2 == w2 * h1. Cross multiplication avoids floating-point precision issues. Each valid comparison increments the answer. This approach requires checking n(n-1)/2 pairs, which becomes too slow for large inputs. It’s useful only as a baseline to understand the ratio condition.

Approach 2: Hash Map for Ratio Counting (O(n) time, O(n) space)

Instead of comparing rectangles directly, compute the ratio w / h for each rectangle and store its frequency in a hash map. As you iterate through the array, check how many times the same ratio has already appeared. Every previous rectangle with that ratio forms a valid pair with the current one. Increment the result by the stored count, then update the frequency. This transforms the pair-counting problem into a frequency accumulation problem using a hash table. The iteration over the array happens once, making the solution linear.

Approach 3: Simplified Ratio Using GCD (O(n) time, O(n) space)

Floating-point ratios may introduce precision issues when stored as hash keys. A safer technique is to reduce each ratio using the greatest common divisor. Compute g = gcd(width, height), then normalize the rectangle to (width/g, height/g). This reduced pair uniquely represents the ratio. Store it in a hash map and count pairs the same way as the previous approach. This method relies on basic math and number theory concepts to create stable keys.

Recommended for interviews: The hash map counting approach with ratio normalization is the expected solution. It demonstrates understanding of ratio equivalence, efficient pair counting, and proper use of hashing. Brute force confirms the underlying relationship, but the O(n) hash-based method shows the optimization interviewers look for.