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
- Two rectangles have the same ratio exactly when the reduced fraction
(width / g, height / g)is identical, whereg = gcd(width, height). - Represent the reduced fraction as a tuple key and count how many rectangles fall into each group.
- A group of size
ccontributesC(c, 2) = c * (c - 1) / 2pairs. - 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 / hintroduces 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 * hor 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.