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. More formally, two rectangles are interchangeable if widthi/heighti == widthj/heightj (using decimal division, not integer division).
Return the number of pairs of interchangeable rectangles in rectangles.
Example 1:
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): - 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 Explanation: There are no interchangeable pairs of rectangles.
Constraints:
n == rectangles.length1 <= n <= 105rectangles[i].length == 21 <= widthi, heighti <= 105Problem Overview: You receive a list of rectangles where each rectangle is defined by [width, height]. Two rectangles are interchangeable if their width-to-height ratios are equal. The task is to count how many pairs (i, j) exist such that both rectangles share the same ratio.
The key observation is that interchangeable rectangles share the same proportional relationship between width and height. Instead of comparing every pair directly, convert each rectangle into a ratio representation and count how often each ratio appears.
Approach 1: Brute Force Pair Comparison (O(n²) time, O(1) space)
Compare every pair of rectangles using two nested loops. For rectangles (w1, h1) and (w2, h2), check whether w1 * h2 == w2 * h1. Cross multiplication avoids floating-point precision issues. Each valid comparison increments the answer. This approach requires checking n(n-1)/2 pairs, which becomes too slow for large inputs. It’s useful only as a baseline to understand the ratio condition.
Approach 2: Hash Map for Ratio Counting (O(n) time, O(n) space)
Instead of comparing rectangles directly, compute the ratio w / h for each rectangle and store its frequency in a hash map. As you iterate through the array, check how many times the same ratio has already appeared. Every previous rectangle with that ratio forms a valid pair with the current one. Increment the result by the stored count, then update the frequency. This transforms the pair-counting problem into a frequency accumulation problem using a hash table. The iteration over the array happens once, making the solution linear.
Approach 3: Simplified Ratio Using GCD (O(n) time, O(n) space)
Floating-point ratios may introduce precision issues when stored as hash keys. A safer technique is to reduce each ratio using the greatest common divisor. Compute g = gcd(width, height), then normalize the rectangle to (width/g, height/g). This reduced pair uniquely represents the ratio. Store it in a hash map and count pairs the same way as the previous approach. This method relies on basic math and number theory concepts to create stable keys.
Recommended for interviews: The hash map counting approach with ratio normalization is the expected solution. It demonstrates understanding of ratio equivalence, efficient pair counting, and proper use of hashing. Brute force confirms the underlying relationship, but the O(n) hash-based method shows the optimization interviewers look for.
This approach involves calculating the width-to-height ratio for each rectangle and storing the count of rectangles with each ratio in a hash map. By iterating over this map, we can calculate the number of interchangeable pairs for each ratio using the combination formula.
We use a default dictionary to store the count of each ratio seen in the rectangles. For each rectangle, we compute the ratio as a floating-point value and increment its count in the dictionary. After processing all rectangles, we accumulate the total pairs using the combination formula C(n, 2) = n * (n - 1) / 2 for each ratio.
Time Complexity: O(n), since each rectangle is processed once to compute its ratio.
Space Complexity: O(n), in the worst case, if all rectangles have different ratios.
Instead of using floating-point arithmetic which might lead to precision errors, this approach utilizes the greatest common divisor (GCD) to convert the width and height of each rectangle into a simplified ratio form (as an integer pair), thus maintaining accuracy and efficiency.
The GCD is used to simplify each rectangle's width and height into a reduced integer form representing the ratio. This avoids the pitfalls of floating-point division and is stored as a tuple in a hash map. The rest of the approach follows the hash map counting to determine the number of pairs.
Python
Time Complexity: O(n), where n is the number of rectangles.
Space Complexity: O(n), to store the simplified ratio counts.
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.
The time complexity is O(n times log M), and the space complexity is O(n). Here, n and M are the number of rectangles and the maximum side length of the rectangles, respectively.
Python
Java
C++
Go
JavaScript
| Approach | Complexity |
|---|---|
| Using Hash Map for Ratio Counting | Time Complexity: O(n), since each rectangle is processed once to compute its ratio. |
| Using Simplified Form of the Ratio | Time Complexity: O(n), where n is the number of rectangles. |
| Mathematics + Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n²) | O(1) | Useful for understanding the ratio condition or when input size is extremely small |
| Hash Map Ratio Counting | O(n) | O(n) | General optimal solution using ratio frequency counting |
| GCD Simplified Ratio with Hash Map | O(n) | O(n) | Preferred when avoiding floating point precision and creating stable hash keys |
Number of Pairs of Interchangeable Rectangles - Leetcode 2001 - Python • NeetCode • 10,174 views views
Watch 9 more video solutions →Practice Number of Pairs of Interchangeable Rectangles with our built-in code editor and test cases.
Practice on FleetCode