Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Counting, Number Theory

Solution

LeetCode 2001 - Number of Pairs of Interchangeable Rectangles

Problem Understanding

This problem asks us to count how many pairs of rectangles are interchangeable. Each rectangle is represented by two integers, width and height. Two rectangles are considered interchangeable if their width-to-height ratios are exactly the same.

In mathematical terms, rectangles i and j are interchangeable when:

$$\frac{width_i}{height_i} = \frac{width_j}{height_j}$$

The important detail is that this comparison uses real division, not integer division. For example, the ratios 4/8, 3/6, and 10/20 are all equal to 0.5, so all of those rectangles belong to the same interchangeable group.

The input is a 2D array called rectangles, where each element contains two integers:

rectangles[i][0] represents the width
rectangles[i][1] represents the height

The output should be the total number of valid pairs (i, j) such that i < j and both rectangles have the same ratio.

The constraints are extremely important here:

The number of rectangles can be as large as 10^5
Widths and heights can also be up to 10^5

These limits immediately tell us that a quadratic solution will not work efficiently. An O(n^2) approach would require comparing every rectangle with every other rectangle, which could result in about 10^10 comparisons in the worst case.

Another subtle issue is ratio representation. Using floating point numbers directly can introduce precision problems. For example, two mathematically equal ratios might not produce identical floating point representations due to rounding behavior. A safer approach is to reduce each ratio to its simplest fractional form using the greatest common divisor, or GCD.

Several edge cases are worth considering upfront. Many rectangles may share the same ratio, which can produce a very large number of pairs. Rectangles may also have completely unique ratios, resulting in zero valid pairs. Another important case is when widths and heights are large but still reducible to the same simplified fraction.

Approaches

Brute Force Approach

The most direct solution is to compare every pair of rectangles.

For every rectangle i, we compare it with every rectangle j > i. We compute both ratios and check whether they are equal. If they are equal, we increment the answer.

This approach is correct because it explicitly checks every possible pair, so no valid pair can be missed.

However, the time complexity is O(n^2). With up to 100000 rectangles, this becomes far too slow. Even optimized implementations cannot handle billions of comparisons within the typical LeetCode time limits.

Another issue is floating point comparison. Directly comparing decimal ratios can lead to precision bugs.

Optimal Hash Map Approach

The key observation is that rectangles with the same reduced ratio belong to the same group.

For example:

4/8 reduces to 1/2
10/20 reduces to 1/2
15/30 reduces to 1/2

Instead of comparing every pair directly, we can normalize each ratio into its reduced fractional form using the GCD.

As we process rectangles one by one:

We compute the reduced ratio
We count how many times this ratio has already appeared
Every previous occurrence forms a new interchangeable pair with the current rectangle

A hash map allows us to track ratio frequencies efficiently.

This transforms the solution from quadratic time to linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Compares every pair directly
Optimal	O(n)	O(n)	Uses normalized ratios and a hash map

Algorithm Walkthrough

Create a hash map called ratio_count.

The key will represent a reduced ratio, stored as a tuple (reduced_width, reduced_height). The value will represent how many rectangles with this ratio have already been seen. 2. Initialize a variable pairs to 0.

This variable stores the total number of interchangeable pairs. 3. Iterate through each rectangle in the input array.

For every rectangle, extract its width and height. 4. Compute the greatest common divisor of the width and height.

The GCD allows us to reduce the fraction to its simplest form.

For example:

(4, 8) becomes (1, 2)
(10, 20) becomes (1, 2)

Divide both width and height by the GCD.

This produces the normalized ratio representation. 6. Use the reduced pair as the hash map key.

Since all equivalent ratios reduce to the same pair, this guarantees consistent grouping. 7. Check how many times this ratio has already appeared.

Suppose the ratio has appeared k times before. Then the current rectangle forms exactly k new interchangeable pairs. 8. Add k to the answer.

Every previous rectangle with the same ratio pairs with the current rectangle. 9. Increment the frequency of the current ratio in the hash map.

This ensures future rectangles can form pairs with it. 10. Continue until all rectangles have been processed. 11. Return the total pair count.

Why it works

The algorithm works because every interchangeable pair must share the same reduced ratio. By reducing every width-height pair into canonical form, all equivalent rectangles map to the same hash map key.

When processing a rectangle, the hash map already contains the number of earlier rectangles with the same ratio. Each of those rectangles forms exactly one valid pair with the current rectangle. Since every pair is counted once when the later rectangle is processed, the final answer is correct.

Python Solution

from typing import List
from collections import defaultdict
from math import gcd

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        ratio_count = defaultdict(int)
        pairs = 0

        for width, height in rectangles:
            divisor = gcd(width, height)

            reduced_width = width // divisor
            reduced_height = height // divisor

            ratio = (reduced_width, reduced_height)

            pairs += ratio_count[ratio]

            ratio_count[ratio] += 1

        return pairs

The solution begins by importing defaultdict and gcd. The hash map stores how many times each reduced ratio has appeared.

For every rectangle, we compute the GCD and reduce the ratio into its simplest form. Using a tuple ensures that ratios like 1/2 and 2/4 are represented identically.

Before updating the map, we add the current frequency to the answer. This counts all previously seen rectangles that share the same ratio.

Finally, we increment the ratio frequency so future rectangles can pair with the current one.

Go Solution

package main

func gcd(a int, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func interchangeableRectangles(rectangles [][]int) int64 {
	ratioCount := make(map[[2]int]int64)

	var pairs int64 = 0

	for _, rectangle := range rectangles {
		width := rectangle[0]
		height := rectangle[1]

		divisor := gcd(width, height)

		reducedWidth := width / divisor
		reducedHeight := height / divisor

		ratio := [2]int{reducedWidth, reducedHeight}

		pairs += ratioCount[ratio]

		ratioCount[ratio]++
	}

	return pairs
}

The Go solution follows the same logic as the Python implementation. Since Go does not have tuples as map keys, a fixed-size array [2]int is used instead.

The return type is int64 because the number of pairs can become very large. In the worst case, if all 100000 rectangles share the same ratio, the number of pairs is:

$$\frac{100000 \times 99999}{2}$$

This exceeds the range of a 32-bit integer.

Worked Examples

Example 1

Input:

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

All rectangles reduce to ratio (1,2).

Step	Rectangle	Reduced Ratio	Existing Count	New Pairs Added	Total Pairs
1	[4,8]	(1,2)	0	0	0
2	[3,6]	(1,2)	1	1	1
3	[10,20]	(1,2)	2	2	3
4	[15,30]	(1,2)	3	3	6

Final answer:

Example 2

Input:

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

Reduced ratios:

(4,5)
(7,8)

Step	Rectangle	Reduced Ratio	Existing Count	New Pairs Added	Total Pairs
1	[4,5]	(4,5)	0	0	0
2	[7,8]	(7,8)	0	0	0

Final answer:

Example 3

Input:

rectangles = [[2,4],[4,8],[6,12],[3,5]]

Step	Rectangle	Reduced Ratio	Existing Count	New Pairs Added	Total Pairs
1	[2,4]	(1,2)	0	0	0
2	[4,8]	(1,2)	1	1	1
3	[6,12]	(1,2)	2	2	3
4	[3,5]	(3,5)	0	0	3

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each rectangle is processed once
Space	O(n)	Hash map may store up to n unique ratios

The algorithm performs constant work per rectangle. GCD computation is extremely fast and bounded by logarithmic complexity relative to the input values, which is effectively constant for the given constraints.

The hash map stores one entry per distinct ratio. In the worst case, every rectangle has a unique ratio, so the space usage becomes linear.

Test Cases

from typing import List

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        from collections import defaultdict
        from math import gcd

        ratio_count = defaultdict(int)
        pairs = 0

        for width, height in rectangles:
            divisor = gcd(width, height)
            ratio = (width // divisor, height // divisor)

            pairs += ratio_count[ratio]
            ratio_count[ratio] += 1

        return pairs

solution = Solution()

assert solution.interchangeableRectangles(
    [[4,8],[3,6],[10,20],[15,30]]
) == 6  # all rectangles share the same ratio

assert solution.interchangeableRectangles(
    [[4,5],[7,8]]
) == 0  # no interchangeable rectangles

assert solution.interchangeableRectangles(
    [[2,4],[4,8],[6,12],[3,5]]
) == 3  # three rectangles share ratio 1/2

assert solution.interchangeableRectangles(
    [[1,1]]
) == 0  # single rectangle cannot form a pair

assert solution.interchangeableRectangles(
    [[1,2],[2,4]]
) == 1  # exactly one valid pair

assert solution.interchangeableRectangles(
    [[1,2],[2,4],[3,6],[4,8]]
) == 6  # four rectangles produce six pairs

assert solution.interchangeableRectangles(
    [[100000,50000],[2,1]]
) == 1  # large values with same reduced ratio

assert solution.interchangeableRectangles(
    [[1,3],[2,6],[4,12],[5,15]]
) == 6  # all reduce to 1/3

assert solution.interchangeableRectangles(
    [[1,2],[2,3],[3,4],[4,5]]
) == 0  # every ratio is unique

Test Summary

Test	Why
`[[4,8],[3,6],[10,20],[15,30]]`	Verifies many interchangeable pairs
`[[4,5],[7,8]]`	Verifies no valid pairs
`[[2,4],[4,8],[6,12],[3,5]]`	Tests mixed matching and non matching ratios
`[[1,1]]`	Tests minimum input size
`[[1,2],[2,4]]`	Tests exactly one pair
`[[1,2],[2,4],[3,6],[4,8]]`	Tests combination counting
`[[100000,50000],[2,1]]`	Tests large reducible values
`[[1,3],[2,6],[4,12],[5,15]]`	Tests repeated normalized ratios
`[[1,2],[2,3],[3,4],[4,5]]`	Tests completely unique ratios

Edge Cases

One important edge case occurs when all rectangles share the same ratio. In this situation, the number of pairs grows very quickly according to the combination formula n * (n - 1) / 2. A naive implementation using a 32-bit integer may overflow. The Go solution correctly uses int64 to avoid this problem.

Another important case involves ratios that are mathematically equal but represented differently. For example, 2/4, 3/6, and 50/100 all describe the same ratio. A solution using raw width and height values directly would fail to group these together. Reducing each ratio using the GCD guarantees correct normalization.

A third edge case is when every rectangle has a unique ratio. In this case, the correct answer is zero. The implementation handles this naturally because each ratio appears exactly once in the hash map, so no previous matching rectangles exist when processing each new rectangle.