Number of Pairs of Interchangeable Rectangles Problem

Problem

You are given n rectangles represented by a 0-indexed 2D integer array rectangles, where rectangles[i] = [widthi, heighti] denotes the width and height of the ith rectangle.

Two rectangles i and j (i < j) are considered interchangeable if they have the same width-to-height ratio. More formally, two rectangles are interchangeable if widthi/heighti == widthj/heightj (using decimal division, not integer division).

Return the number of pairs of interchangeable rectangles in rectangles.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input:
rectangles = [[4,8],[3,6],[10,20],[15,30]]
Output:
 6
Explanation: The following are the interchangeable pairs of rectangles by index (0-indexed):
- Rectangle 0 with rectangle 1: 4/8 == 3/6.
- Rectangle 0 with rectangle 2: 4/8 == 10/20.
- Rectangle 0 with rectangle 3: 4/8 == 15/30.
- Rectangle 1 with rectangle 2: 3/6 == 10/20.
- Rectangle 1 with rectangle 3: 3/6 == 15/30.
- Rectangle 2 with rectangle 3: 10/20 == 15/30.

Example 2:

1
2
3
4
5

Input:
rectangles = [[4,5],[7,8]]
Output:
 0
Explanation: There are no interchangeable pairs of rectangles.

Solution

Method 1 – Hash Map for Ratio Counting

Intuition

Rectangles are interchangeable if their width-to-height ratios are equal. By reducing each ratio to its simplest form (using GCD), we can count how many rectangles share the same ratio. For each group of rectangles with the same ratio, the number of interchangeable pairs is the combination C(n, 2) = n*(n-1)/2.

Approach

  1. For each rectangle, compute the reduced ratio (width/gcd, height/gcd).
  2. Use a hash map to count occurrences of each unique ratio.
  3. For each ratio with count > 1, add count * (count - 1) / 2 to the answer.
  4. Return the total number of pairs.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    long long interchangeableRectangles(vector<vector<int>>& rects) {
        unordered_map<string, long long> cnt;
        for (auto& r : rects) {
            int g = gcd(r[0], r[1]);
            string key = to_string(r[0]/g) + "/" + to_string(r[1]/g);
            cnt[key]++;
        }
        long long ans = 0;
        for (auto& [k, v] : cnt) ans += v * (v - 1) / 2;
        return ans;
    }
    int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func interchangeableRectangles(rects [][]int) int64 {
    cnt := map[string]int64{}
    for _, r := range rects {
        g := gcd(r[0], r[1])
        key := fmt.Sprintf("%d/%d", r[0]/g, r[1]/g)
        cnt[key]++
    }
    var ans int64
    for _, v := range cnt {
        ans += v * (v - 1) / 2
    }
    return ans
}
func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public long interchangeableRectangles(int[][] rects) {
        Map<String, Long> cnt = new HashMap<>();
        for (int[] r : rects) {
            int g = gcd(r[0], r[1]);
            String key = (r[0]/g) + "/" + (r[1]/g);
            cnt.put(key, cnt.getOrDefault(key, 0L) + 1);
        }
        long ans = 0;
        for (long v : cnt.values()) ans += v * (v - 1) / 2;
        return ans;
    }
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun interchangeableRectangles(rects: Array<IntArray>): Long {
        val cnt = mutableMapOf<String, Long>()
        for (r in rects) {
            val g = gcd(r[0], r[1])
            val key = "${r[0]/g}/${r[1]/g}"
            cnt[key] = cnt.getOrDefault(key, 0L) + 1
        }
        var ans = 0L
        for (v in cnt.values) ans += v * (v - 1) / 2
        return ans
    }
    private fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from collections import defaultdict
def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a
class Solution:
    def interchangeableRectangles(self, rects: list[list[int]]) -> int:
        cnt: dict[tuple[int, int], int] = defaultdict(int)
        for w, h in rects:
            g = gcd(w, h)
            cnt[(w//g, h//g)] += 1
        ans = 0
        for v in cnt.values():
            ans += v * (v - 1) // 2
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

use std::collections::HashMap;
impl Solution {
    pub fn interchangeable_rectangles(rects: Vec<Vec<i32>>) -> i64 {
        fn gcd(mut a: i32, mut b: i32) -> i32 {
            while b != 0 {
                let t = b;
                b = a % b;
                a = t;
            }
            a
        }
        let mut cnt = HashMap::new();
        for r in rects.iter() {
            let g = gcd(r[0], r[1]);
            let key = (r[0]/g, r[1]/g);
            *cnt.entry(key).or_insert(0) += 1;
        }
        let mut ans = 0i64;
        for &v in cnt.values() {
            ans += v * (v - 1) / 2;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    interchangeableRectangles(rects: number[][]): number {
        const cnt = new Map<string, number>();
        for (const [w, h] of rects) {
            const g = gcd(w, h);
            const key = `${w/g}/${h/g}`;
            cnt.set(key, (cnt.get(key) ?? 0) + 1);
        }
        let ans = 0;
        for (const v of cnt.values()) ans += v * (v - 1) / 2;
        return ans;
    }
}
function gcd(a: number, b: number): number {
    while (b) [a, b] = [b, a % b];
    return a;
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of rectangles, as we process each rectangle once and hash map operations are O(1) on average.
  • 🧺 Space complexity: O(n), for storing the ratio counts in the hash map.