Number of Pairs of Interchangeable Rectangles — LeetCode 2001 Python Solution

The problem

You are given n rectangles represented by a 0-indexed 2D integer array rectangles, where rectangles[i] = [widthi, heighti] denotes the width and height of the ith rectangle. Two rectangles i and j (i < j) are considered interchangeable if they have the same width-to-height ratio.

Example

Input

rectangles = [[4,8],[3,6],[10,20],[15,30]]

Output

6

Explanation

The following are the interchangeable pairs of rectangles by index (0-indexed):

Python solution

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        ans = 0
        cnt = Counter()
        for w, h in rectangles:
            g = gcd(w, h)
            w, h = w // g, h // g
            ans += cnt[(w, h)]
            cnt[(w, h)] += 1
        return ans

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 2001. Number of Pairs of Interchangeable Rectangles is filed here because LeetCode tags it Math and Number Theory, which is the vocabulary this hub collects.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems