Number of Pairs of Interchangeable Rectangles

Medium
674.

Number of Pairs of Interchangeable Rectangles

Number of Pairs of Interchangeable Rectangles is a medium coding problem on arrays, hash table and math, asked in Amazon, Google and Walmart interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} rectangles
 * @return {number}
 */
var interchangeableRectangles = function(rectangles) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Pairs of Interchangeable Rectangles — Solution

Number of Pairs of Interchangeable Rectangles solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Number of Pairs of Interchangeable Rectangles is a medium coding problem on arrays, hash table and math, asked in Amazon, Google and Walmart interviews.

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

Hints for Number of Pairs of Interchangeable Rectangles

  1. Hint 1

    Comparing w1 / h1 == w2 / h2 in floating point is a correctness trap at these magnitudes.

  2. Hint 2

    Reduce each ratio by the greatest common divisor and use the reduced pair as an exact key.

  3. Hint 3

    Then the answer is the number of same-key pairs, which one pass with a tally gives.

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

  1. For each rectangle compute g = gcd(width, height) and form the key (width/g, height/g).
  2. Sweep the list; before recording a key, add its current tally to the answer.
  3. 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

Java

public static int interchangeableRectangles(int[][] rectangles) {
    Map<String, Integer> seen = new HashMap<>();
    int total = 0;
    for (int[] r : rectangles) {
        int a = r[0], b = r[1];
        while (b != 0) { int t = a % b; a = b; b = t; }
        String key = (r[0] / a) + "/" + (r[1] / a);
        int c = seen.getOrDefault(key, 0);
        total += c;
        seen.put(key, c + 1);
    }
    return total;
}

C++

int interchangeableRectangles(vector<vector<int>>& rectangles) {
    map<pair<int, int>, int> seen;
    int total = 0;
    for (auto& r : rectangles) {
        int a = r[0], b = r[1];
        while (b != 0) { int t = a % b; a = b; b = t; }
        pair<int, int> key = { r[0] / a, r[1] / a };
        total += seen[key];
        seen[key]++;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets