2001. Number of Pairs of Interchangeable Rectangles - Explanation

1. Brute Force

Intuition

Two rectangles are interchangeable if they have the same aspect ratio (width divided by height). The simplest approach is to compare every pair of rectangles and check if their ratios match. For each pair where the ratios are equal, we count it as an interchangeable pair.

Algorithm

Initialize a counter res to 0.
For each rectangle i from 1 to n-1:
- For each rectangle j from 0 to i-1:
  - If rectangles[i][0] / rectangles[i][1] equals rectangles[j][0] / rectangles[j][1], increment res.
Return res.

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        res = 0
        for i in range(1, len(rectangles)):
            for j in range(i):
                if rectangles[i][0] / rectangles[i][1] == rectangles[j][0] / rectangles[j][1]:
                    res += 1
        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Hash Map (Two Pass)

Intuition

Instead of comparing every pair, we can group rectangles by their aspect ratio. Rectangles with the same ratio form a group, and any two rectangles in the same group are interchangeable. If a group has c rectangles, the number of pairs is c * (c-1) / 2 (choosing 2 from c). We use a hash map to count how many rectangles share each ratio.

Algorithm

Create a hash map count to store the frequency of each aspect ratio.
First pass: for each rectangle, compute its ratio and increment the count in the map.
Second pass: for each ratio with count c > 1, add c * (c-1) / 2 to the result.
Return the total count of interchangeable pairs.

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        count = {}
        for w, h in rectangles:
            count[w / h] = 1 + count.get(w / h, 0)

        res = 0
        for c in count.values():
            if c > 1:
                res += (c * (c - 1)) // 2
        return res

Time & Space Complexity

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

3. Hash Map (One Pass)

Intuition

We can optimize the two-pass approach into a single pass. As we process each rectangle, we check how many rectangles with the same ratio we have seen before. Each previously seen rectangle with the same ratio forms a new interchangeable pair with the current rectangle. This way, we count pairs incrementally as we go.

Algorithm

Create a hash map count to store the frequency of each aspect ratio.
Initialize res to 0.
For each rectangle:
- Compute its aspect ratio.
- Add the current count for this ratio to res (each previous rectangle with this ratio forms a pair).
- Increment the count for this ratio in the map.
Return res.

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        count = {}
        res = 0
        for w, h in rectangles:
            res += count.get(w / h, 0)
            count[w / h] = 1 + count.get(w / h, 0)
        return res

Time & Space Complexity

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

4. Greatest Common Divisor

Intuition

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.

Algorithm

Create a hash map count to store the frequency of each normalized ratio.
Initialize res to 0.
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.
Return res.

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

Time & Space Complexity

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

Common Pitfalls

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).