Number of pairs of interchangeable rectangles

Array Hash Table Math Counting Number Theory

52.4% acceptance

Feb 25, 2026

579

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn interchangeable_rectangles(rectangles: Vec<Vec<i32>>) -> i64 {
    use std::collections::HashMap;
    let mut map: HashMap<(i32, i32), i64> = HashMap::new();
    for r in &rectangles {
      let (w, h) = (r[0], r[1]);
      let g = gcd(w, h);
      *map.entry((w / g, h / g)).or_insert(0) += 1;
    }
    map.values().map(|&cnt| cnt * (cnt - 1) / 2).sum()
  }
}

fn gcd(a: i32, b: i32) -> i32 {
  if b == 0 { a } else { gcd(b, a % b) }
}