⚡Flashcard Drill➔
NeetCode #117LC-2001MediumArrays & Hashing
← Back to All Problems

#117 · #2001 · Number of Pairs of Interchangeable Rectangles(可互换矩形的组数)

📌 Problem Statement & Constraints

You are given n rectangles, each [width_i, height_i]. Two rectangles are interchangeable if their width-to-height ratios are equal. Count the number of pairs (i, j) with i < j that are interchangeable. Constraints: 1 <= n <= 10^5, 1 <= width_i, height_i <= 10^5.

💡 Core Algorithmic Approaches

  1. Two rectangles have the same ratio exactly when the reduced fraction (width / g, height / g) is identical, where g = gcd(width, height).
  2. Represent the reduced fraction as a tuple key and count how many rectangles fall into each group.
  3. A group of size c contributes C(c, 2) = c * (c - 1) / 2 pairs.
  4. Using the reduced integer pair avoids floating-point comparison errors entirely.

💻 Benchmark Python3 Implementation

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        from collections import defaultdict
        from math import gcd
        cnt = defaultdict(int)
        for w, h in rectangles:
            g = gcd(w, h)
            cnt[(w // g, h // g)] += 1     # reduced fraction as the key
        return sum(c * (c - 1) // 2 for c in cnt.values())

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log V): each gcd is O(log V), and the summation is over the groups.
💾 Space Complexity
O(n) for the groups.

⚠️ Interview Pitfalls & Follow-ups

  • Comparing floats: w / h introduces rounding, and two mathematically equal ratios can differ in the last bit. Use reduced integer pairs.
  • Forgetting to reduce the fraction: (2, 4) and (1, 2) must map to the same key.
  • Counting ordered pairs: the requirement is i < j, so use the combination formula.
  • Using w * h or the sum as the key: those are not invariants of the ratio.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems