Number of Pairs of Interchangeable Rectangles

How it works

Using floating-point division for ratios can lead to precision issues with very large numbers. A more robust approach is to reduce each ratio to its simplest form using the greatest common divisor (GCD). Two rectangles have the same ratio if and only if their reduced forms are identical. We can pack the reduced width and height into a single integer key for efficient hashing.

Steps

1. Create a hash map count to store the frequency of each normalized ratio.
2. Initialize res to 0.
3. For each rectangle:
   • Compute the GCD of width and height.
   • Divide both by the GCD to get the reduced form.
   • Create a unique hash key by combining the reduced width and height (e.g., using bit shifting).
   • Add the current count for this key to res.
   • Increment the count for this key in the map.
4. Return res.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Floating-Point Precision Errors

Using floating-point division to compute aspect ratios can lead to precision issues with large width/height values. Two ratios that should be equal may compare as unequal due to floating-point representation errors. The GCD-based approach avoids this by reducing ratios to their simplest integer form before comparison.

Integer Overflow in Pair Counting

When counting pairs using the formula c * (c - 1) / 2, the multiplication can overflow if c is large and you are using 32-bit integers. Ensure you use a 64-bit integer type (like long in Java or long long in C++) for the result and intermediate calculations.

Incorrect Pair Counting Formula

A common mistake is counting each pair twice by iterating over all i != j combinations, or forgetting to use the combination formula entirely. Remember that choosing 2 items from c items is c * (c - 1) / 2, not c * c or c * (c - 1).

from typing import List
from math import gcd
import math

class Solution:
    def hash(self, a: int, b: int) -> int:
        mask = a
        mask |= (b << 31)
        return mask

    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        res = 0
        count = {}
        for rect in rectangles:
            gcd = math.gcd(rect[0], rect[1])
            key = self.hash(rect[0] // gcd, rect[1] // gcd)
            res += count.get(key, 0)
            count[key] = count.get(key, 0) + 1
        return res

class Solution {
public:
    long long hash(int a, int b) {
        long long mask = a;
        mask |= ((long long)b << 31);
        return mask;
    }

    long long interchangeableRectangles(vector<vector<int>>& rectangles) {
        long long res = 0;
        unordered_map<long long, int> count;
        for (const auto& rect : rectangles) {
            int gcd = std::gcd(rect[0], rect[1]);
            long long key = hash(rect[0] / gcd, rect[1] / gcd);
            res += count[key];
            count[key]++;
        }
        return res;
    }
};