# Number of Pairs of Interchangeable Rectangles
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-pairs-of-interchangeable-rectangles)
Canonical: https://scaleengineer.com/dsa/problems/number-of-pairs-of-interchangeable-rectangles
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Counting](https://scaleengineer.com/dsa/patterns/counting), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array, Hash Table
---
## 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`.

**Example 1:**

**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:**

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

**Constraints:**

* `n == rectangles.length`
* `1 <= n <= 105`
* `rectangles[i].length == 2`
* `1 <= widthi, heighti <= 105`

# Approaches
## Brute Force
This approach directly translates the problem statement into code. It involves checking every possible pair of rectangles to see if they are interchangeable. While simple to conceive and implement, its performance is poor for large datasets.
**Time:** O(n^2), where n is the number of rectangles. The nested loops result in a quadratic number of comparisons. · **Space:** O(1), as it only uses a few variables to store loop indices and the final count, regardless of the input size.
**Pros:** Simple to understand and implement.; Requires no extra space, making it very memory-efficient.
**Cons:** Extremely inefficient for large inputs due to its quadratic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints (n up to 10^5).
### Explanation
The brute-force method iterates through all unique pairs of rectangles. For each pair of rectangles, `i` and `j`, we compare their width-to-height ratios. A direct comparison using floating-point division (`width_i / height_i == width_j / height_j`) can be prone to precision errors. A more reliable method is to use integer arithmetic with cross-multiplication: `width_i * height_j == width_j * height_i`. Since the product of widths and heights can exceed the capacity of a standard 32-bit integer (up to `10^5 * 10^5 = 10^10`), we must use a 64-bit integer type (`long` in Java) for the calculation to prevent overflow. We maintain a counter, which is incremented for every pair that satisfies this condition.

```java
class Solution {
    public long interchangeableRectangles(int[][] rectangles) {
        long count = 0;
        int n = rectangles.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long w1 = rectangles[i][0];
                long h1 = rectangles[i][1];
                long w2 = rectangles[j][0];
                long h2 = rectangles[j][1];
                if (w1 * h2 == w2 * h1) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   Initialize a counter `count` to 0.
*   Use a nested loop to iterate through all pairs of indices `(i, j)` such that `0 <= i < j < n`, where `n` is the number of rectangles.
*   For each pair, get their dimensions: `w1, h1` for rectangle `i` and `w2, h2` for rectangle `j`.
*   To check for interchangeability (`w1/h1 == w2/h2`) without using floating-point numbers, use cross-multiplication: `w1 * h2 == w2 * h1`.
*   To avoid potential integer overflow, cast the dimensions to a 64-bit integer type (`long` in Java) before multiplying.
*   If the cross-multiplication products are equal, increment the `count`.
*   After the loops complete, return the final `count`.

## HashMap to Count Ratios
A more efficient approach involves grouping rectangles by their width-to-height ratio. By using a HashMap, we can count the occurrences of each ratio in a single pass. For each group of `k` rectangles with the same ratio, they form `k * (k-1) / 2` pairs. This method avoids the expensive quadratic pair-wise comparison.
**Time:** O(n), where n is the number of rectangles. We iterate through the array once, and each HashMap operation (get and put) takes, on average, O(1) time. · **Space:** O(U), where `U` is the number of unique ratios. In the worst-case scenario where all rectangles have different ratios, the space complexity is O(n).
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; Conceptually elegant, solving the problem by counting groups rather than individual pairs.
**Cons:** Requires extra space for the HashMap, which can be up to O(n) in the worst case.; Using `double` as a HashMap key can be risky due to floating-point precision issues, though it often works for this type of problem. A more robust (but slightly more complex) implementation would simplify the fraction `width/height` using the Greatest Common Divisor (GCD) and use the resulting pair or a string representation as the key.
### Explanation
Instead of comparing every rectangle with every other rectangle, we can optimize the process by grouping rectangles that have the same ratio. The problem then becomes counting the number of pairs we can form within each group.

We can iterate through the list of rectangles once. For each rectangle, we calculate its width-to-height ratio. We use a HashMap to keep track of how many times we've seen each specific ratio so far. 

When we encounter a rectangle with a certain ratio, we check the HashMap. If we have already seen `k` rectangles with this same ratio, it means our current rectangle can form `k` new interchangeable pairs. We add `k` to our total count of pairs. Then, we update the HashMap to reflect that we have now seen `k+1` rectangles with this ratio. This process is repeated for all rectangles, and the final accumulated count is the answer.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public long interchangeableRectangles(int[][] rectangles) {
        Map<Double, Long> ratioCounts = new HashMap<>();
        long count = 0;

        for (int[] rect : rectangles) {
            double ratio = (double) rect[0] / rect[1];
            long currentCount = ratioCounts.getOrDefault(ratio, 0L);
            count += currentCount;
            ratioCounts.put(ratio, currentCount + 1);
        }

        return count;
    }
}
```
### Algorithm
*   Initialize a total pair count `count` to 0.
*   Create a HashMap, `ratioCounts`, to store the frequency of each ratio. The key will be the `double` ratio, and the value will be its frequency (`long`).
*   Iterate through each `rectangle` in the input array `rectangles`.
*   For the current rectangle, calculate its width-to-height ratio as a `double`: `ratio = (double)width / height`.
*   Look up this `ratio` in the `ratioCounts` map to find how many rectangles with this same ratio have been seen before. Let this be `previousCount`.
*   The current rectangle can form a new pair with each of those `previousCount` rectangles. So, add `previousCount` to the total `count`.
*   Increment the frequency of the current `ratio` in the map. `ratioCounts.put(ratio, previousCount + 1)`.
*   After iterating through all rectangles, return the total `count`.

# Solutions
### Java

```java
class Solution {
public
  long interchangeableRectangles(int[][] rectangles) {
    long ans = 0;
    int n = rectangles.length + 1;
    Map<Long, Integer> cnt = new HashMap<>();
    for (var e : rectangles) {
      int w = e[0], h = e[1];
      int g = gcd(w, h);
      w /= g;
      h /= g;
      long x = (long)w * n + h;
      ans += cnt.getOrDefault(x, 0);
      cnt.merge(x, 1, Integer : : sum);
    }
    return ans;
  }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

```

### JavaScript

```javascript
/** * @param {number[][]} rectangles * @return {number} */ var interchangeableRectangles =
  function (rectangles) {
    const cnt = new Map();
    let ans = 0;
    for (let [w, h] of rectangles) {
      const g = gcd(w, h);
      w = Math.floor(w / g);
      h = Math.floor(h / g);
      const x = w * (rectangles.length + 1) + h;
      ans += cnt.get(x) | 0;
      cnt.set(x, (cnt.get(x) | 0) + 1);
    }
    return ans;
  };
function gcd(a, b) {
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}

```

### CPP

```cpp
class Solution {
public:
  long long interchangeableRectangles(vector<vector<int>> &rectangles) {
    long long ans = 0;
    int n = rectangles.size();
    unordered_map<long long, int> cnt;
    for (auto &e : rectangles) {
      int w = e[0], h = e[1];
      int g = gcd(w, h);
      w /= g;
      h /= g;
      long long x = 1ll * w * (n + 1) + h;
      ans += cnt[x];
      cnt[x]++;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int: ans = 0 cnt = Counter() for w, h in rectangles: g = gcd(w, h) w, h = w // g, h // g ans += cnt[(w, h)] cnt[(w, h)] += 1 return ans

```