Number of Pairs of Interchangeable Rectangles

Number of Pairs of Interchangeable Rectangles

What is this problem about?

The Number of Pairs of Interchangeable Rectangles problem gives you rectangles defined by [width, height]. Two rectangles are interchangeable if they have the same aspect ratio (width/height). Count the number of distinct pairs of interchangeable rectangles. This coding problem uses GCD-based ratio normalization and combination counting.

Why is this asked in interviews?

Amazon asks this to test aspect ratio normalization with GCD and the standard combination counting formula. Normalizing (w,h) to (w/gcd, h/gcd) gives a canonical form for each aspect ratio. Grouping by canonical form and applying C(m,2) counts pairs. The array, math, number theory, hash table, and counting interview pattern is directly demonstrated.

Algorithmic pattern used

GCD normalization + frequency count. For each rectangle [w,h], compute g = gcd(w,h) and normalize to (w/g, h/g). Build a frequency map. For each frequency m, add m*(m-1)/2 to the result. Return total.

Example explanation

Rectangles: [[4,8],[3,6],[10,20],[15,30],[3,3]]. Normalized: (1,2),(1,2),(1,2),(1,2),(1,1).

• (1,2): frequency=4. Pairs = C(4,2) = 6.
• (1,1): frequency=1. Pairs = 0. Total = 6.

Common mistakes candidates make

• Dividing by floating-point ratio (e.g., w/h as float) — use GCD-based integer normalization.
• Using w/h and h/w interchangeably (must have consistent (w/g, h/g) ordering).
• Off-by-one: C(m,2) = m*(m-1)/2, not m*(m+1)/2.
• Not handling square rectangles correctly.

Interview preparation tip

Aspect ratio normalization via GCD is the core technique for "equivalent rectangle" problems. Always normalize to the reduced form (w/gcd, h/gcd) as a tuple key. The combination count m*(m-1)/2 for m elements in a group is a fundamental pattern appearing in many pair-counting problems. After mastering this, extend to "count triples with equal aspect ratio" by using C(m,3) = m*(m-1)*(m-2)/6.