Number of Pairs of Interchangeable Rectangles — Medium Problem & Solution

Each entry rectangles[i] = [width, height] describes a rectangle. Two rectangles are interchangeable when they have the same width-to-height ratio.

Difficulty: Medium
Topics: Arrays, Math, Hash Table, Counting
Asked at: Amazon, Google, Walmart
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Each entry rectangles[i] = [width, height] describes a rectangle. Two rectangles are interchangeable when they have the same width-to-height ratio.

Return the number of pairs (i, j) with i < j that are interchangeable.

Example 1

Input: rectangles = [[4,8],[3,6],[10,20],[15,30]]
Output: 6
Explanation: All four share the ratio 1/2, giving every one of the six pairs.

Example 2

Input: rectangles = [[4,5],[7,8]]
Output: 0
Explanation: 4/5 and 7/8 differ.

Example 3

Input: rectangles = [[2,3],[4,6],[5,7]]
Output: 1
Explanation: Only the first two match, both reducing to 2/3.

Constraints

1 <= rectangles.length <= 1000
rectangles[i].length == 2
1 <= width, height <= 100000

How to solve Number of Pairs of Interchangeable Rectangles

Two ratios are equal exactly when their reduced fractions match, so dividing width and height by their gcd gives a canonical, exact key. The rest is counting pairs within each group.

Approach

For each rectangle compute g = gcd(width, height) and form the key (width/g, height/g).
Sweep the list; before recording a key, add its current tally to the answer.
Increment the tally.

Why it works

Reducing by the gcd yields the unique lowest-terms representative of a rational, so key equality is ratio equality with no rounding involved. Counting before inserting attributes each pair to its later index exactly once, which is the i < j requirement.

Complexity

Time — O(n log V)
Space — O(n)

Pitfalls

Floating-point division can make 10/20 and 15/30 compare unequal — or, worse, make genuinely different ratios compare equal.
Squashing the key into a single number such as w * 100000 + h works only if the reduced values stay in range; a pair or a string key is safer.
With 1000 rectangles the pair count reaches about 500000, which fits in a 32-bit integer, but a larger limit would not.

Reference solution

Python

from math import gcd
from typing import List

def interchangeableRectangles(rectangles: List[List[int]]) -> int:
    seen = {}
    total = 0
    for w, h in rectangles:
        g = gcd(w, h)
        key = (w // g, h // g)
        total += seen.get(key, 0)
        seen[key] = seen.get(key, 0) + 1
    return total

JavaScript

var interchangeableRectangles = function(rectangles) {
    var gcd = function(a, b) {
        while (b !== 0) {
            var t = a % b;
            a = b;
            b = t;
        }
        return a;
    };
    var seen = {}, total = 0;
    for (var i = 0; i < rectangles.length; i++) {
        var w = rectangles[i][0], h = rectangles[i][1];
        var g = gcd(w, h);
        var key = String(w / g) + "/" + String(h / g);
        if (seen[key] !== undefined) total += seen[key];
        seen[key] = (seen[key] === undefined ? 0 : seen[key]) + 1;
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue