Skip to main content
Talentd

Number of Pairs of Interchangeable Rectangles - Solution & Explanation

MediumArrayHash TableMathCounting12 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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.length
  • 1 <= n <= 105
  • rectangles[i].length == 2
  • 1 <= widthi, heighti <= 105

Approach Overview

Problem 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.

Approach 1: Using Hash Map for Ratio Counting

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.

Code

PythonJavaC++C#

Python

Java

C++

C#

Complexity

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.

Try this approach in the editor →

Approach 2: Using Simplified Form of the Ratio

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.

Code

Python

Python

Complexity

Time Complexity: O(n), where n is the number of rectangles.
Space Complexity: O(n), to store the simplified ratio counts.

Try this approach in the editor →

Approach 3: 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.

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.

Code

PythonJavaC++GoJavaScript

Python

Java

C++

Go

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Hash Map for Ratio Counting

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.

Using Simplified Form of the Ratio

Time Complexity: O(n), where n is the number of rectangles.
Space Complexity: O(n), to store the simplified ratio counts.

Mathematics + Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair ComparisonO(n²)O(1)Useful for understanding the ratio condition or when input size is extremely small
Hash Map Ratio CountingO(n)O(n)General optimal solution using ratio frequency counting
GCD Simplified Ratio with Hash MapO(n)O(n)Preferred when avoiding floating point precision and creating stable hash keys

Video Solution

Number of Pairs of Interchangeable Rectangles - Leetcode 2001 - Python • NeetCode • 10,301 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Number of Pairs of Interchangeable Rectangles easy or hard?
This problem is classified as Medium difficulty. The challenge is recognizing that interchangeable rectangles share the same ratio and that pair counting can be optimized using a hash map. Once that insight is clear, the implementation is straightforward.
Number of Pairs of Interchangeable Rectangles Python/Java solution
Python and Java implementations typically use a dictionary or HashMap to track ratio frequencies. Each rectangle is normalized using either floating-point division or GCD reduction, then counted using the hash map. The algorithm processes the array once, giving O(n) time complexity.
How to solve Number of Pairs of Interchangeable Rectangles in O(n)?
Iterate through the rectangles and compute a ratio representation for each one. Store the ratio in a hash map with its frequency. When a ratio appears again, add the existing frequency to the pair count before incrementing it. Using GCD to normalize (width, height) ensures ratios are stored consistently.
What is the best approach for Number of Pairs of Interchangeable Rectangles?
The most efficient approach uses a hash map to count rectangle ratios. Convert each rectangle into a width-to-height ratio and track how many times the same ratio has appeared before. Every previous occurrence forms a valid pair. This method runs in O(n) time and O(n) space.
Is Number of Pairs of Interchangeable Rectangles asked at Google/Amazon/Meta?
Ratio counting and hash map frequency problems frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, the technique of reducing ratios and counting pairs with hashing is a common interview pattern.
What data structure is used in Number of Pairs of Interchangeable Rectangles?
A hash map is the primary data structure used to store the frequency of each rectangle ratio. The key represents the normalized ratio, and the value tracks how many rectangles share it. This allows constant-time lookups while counting valid pairs.
What is the time complexity of Number of Pairs of Interchangeable Rectangles?
The optimal solution runs in O(n) time because each rectangle is processed once while updating a hash map of ratios. Space complexity is O(n) in the worst case when all rectangles have unique ratios. A brute force solution would require O(n²) comparisons.

Ready to solve this problem?

Practice Number of Pairs of Interchangeable Rectangles with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Nice Pairs in an Array

Next

Number of Good Pairs