Number Of Pairs Of Interchangeable Rectangles

TARGET DECK: Leetcode FILE TAGS: Medium

---

Intuition

• Use a HashMap to store the count of how many rectangles are interchangeable.
• Then, use Combination to sum the pairwise count.
  • Notice that you may use the formula $\frac{n!}{k!(n-k)!}$.
  • Alternatively, you may use the pairwise formula, in which you ask:
    • How many ways are there to sit n people into 2 chairs?: $n\times (n-1)$:
      • permutations formula with k = 2, so:
        • $\frac{n!}{(n-2)!}=n\times (n-1)$
    • Then, we don’t care about duplicate seating’s, so we divide that permutation by k! (so 2), which gives the formula:
      • $\frac{n\times (n-1)}{2}$

Complexity

Runtime

$O(N)$ to loop through all the rectangles

Space

$O(N)$ to store count of at most N interchangeable rectangles (wherein each rectangle has a different $\frac{w_i}{h_i}$)

Code

Using Pairwise Formula

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        hm = defaultdict(int)
        for (w, h) in rectangles:
            hm[w / h] += 1
        
        res = 0
        for c in hm.values():
            res += (c * (c - 1)) // 2
 
        return res

Using Combinations Library

from math import comb
class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        hm = defaultdict(int)
        for (w, h) in rectangles:
            hm[w / h] += 1
        
        res = 0
        for c in hm.values():
            res += comb(c, 2)
            
        return res

Cards

START Basic Front: Number Of Pairs Of Interchangeable Rectangles Back: Use Pairwise formula to count number of pairs of each interchangeable rectangle.

END

---

References

• Number Of Pairs Of Interchangeable Rectangles