#2001

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Number of Pairs of Interchangeable Rectangles

Count all pairs of rectangles that share the exact width-to-height ratio using efficient array scanning and hash lookup.

array hash table math counting number theory

Problem Statement

You are given a list of rectangles represented as a 2D array rectangles, where each rectangle is defined by its width and height. Two rectangles are interchangeable if they have the same width-to-height ratio, using decimal division for precision.

Return the total number of pairs (i, j) with i < j where rectangles[i] and rectangles[j] are interchangeable. Each rectangle may appear in multiple pairs if its ratio matches multiple other rectangles.

Examples

Example 1

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

Output: 6

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

Rectangle 0 with rectangle 1: 4/8 == 3/6.
Rectangle 0 with rectangle 2: 4/8 == 10/20.
Rectangle 0 with rectangle 3: 4/8 == 15/30.
Rectangle 1 with rectangle 2: 3/6 == 10/20.
Rectangle 1 with rectangle 3: 3/6 == 15/30.
Rectangle 2 with rectangle 3: 10/20 == 15/30.

Example 2

Input: rectangles = [[4,5],[7,8]]

Output: 0

There are no interchangeable pairs of rectangles.

Constraints

n == rectangles.length
1 <= n <= 105
rectangles[i].length == 2
1 <= widthi, heighti <= 105

Solution Approach

Compute Ratios and Use Hash Map

Iterate over each rectangle, compute its width divided by height as a decimal, and store the count of each unique ratio in a hash map. This prepares for pair counting without nested loops.

Count Pairs Incrementally

For each rectangle, if its ratio is already in the hash map, increment the total pairs by the current count of that ratio. Then update the hash map count. This counts all valid pairs efficiently.

Return Total Pair Count

After processing all rectangles, return the accumulated pair count. This uses O(n) time for array scanning and hash operations, avoiding explicit O(n^2) comparisons.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) due to a single pass through the rectangles and O(1) hash operations per rectangle. Space complexity is O(n) for storing ratio counts in the hash map.

What Interviewers Usually Probe

Look for candidates to optimize from O(n^2) pair checking to hash-based counting.
Expect discussion on precision when dividing integers to form accurate ratios.
Check whether candidates consider edge cases with identical width or height values.

Common Pitfalls or Variants

Common pitfalls

Using integer division instead of decimal division when calculating ratios, leading to incorrect pair counting.
Nested loops for pair comparison, which causes timeouts on large inputs.
Failing to correctly increment pair counts based on existing ratio counts in the hash map.

Follow-up variants

Count pairs of rectangles that are exact matches in width and height instead of ratios.
Return the list of all interchangeable rectangle index pairs rather than just the count.
Handle rectangles where dimensions are very large, requiring careful numeric precision for ratios.

FAQ

What is the key pattern to solve Number of Pairs of Interchangeable Rectangles efficiently?

Use array scanning plus a hash map to track width-to-height ratios, incrementing counts as you encounter repeated ratios.

Why is integer division incorrect for this problem?

Integer division truncates decimals, which can make distinct ratios appear equal and miscount interchangeable pairs.

Can I use nested loops to check all rectangle pairs?

Technically yes, but it leads to O(n^2) time complexity and will likely time out on large inputs.

How does a hash map help in counting pairs?

It stores the number of times each ratio occurs, allowing you to calculate new pairs in O(1) per rectangle.

What constraints should I consider for width and height values?

Width and height values are up to 10^5, so using proper numeric types and decimal division is necessary to avoid precision issues.

terminal

Solution

Solution 1: Mathematics + Hash Table

In order to uniquely represent a rectangle, we need to simplify the width-to-height ratio of the rectangle to a simplest fraction. Therefore, we can find the greatest common divisor of the width-to-height ratio of each rectangle, and then simplify the width-to-height ratio to the simplest fraction. Next, we use a hash table to count the number of rectangles for each simplest fraction, and then calculate the combination of the number of rectangles for each simplest fraction to get the answer.

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#1994 the number of good subsets #2748 number of beautiful pairs #3044 most frequent prime