Number of Pairs of Interchangeable Rectangles solution and explanation
Google
8 more videos on this problem
Number of Pairs of Interchangeable Rectangles - Leetcode 2001 - PythonNeetCode · 7:49 · 10K views
2001. Number of Pairs of Interchangeable Rectangles (Leetcode Medium)Programming Live with Larry · 5:06 · 458 views
Number of Pairs of Interchangeable Rectangles | Leetcode 2001 | Approach + Code with explanation.Pirai's Academy · 10:30 · 213 views
Leetcode 2001 Number of Pairs of Interchangeable RectanglesMath Geeks · 3:24 · 189 views
Number of Pairs of Interchangeable Rectangles - LeetCode 2001 - Python -CombinationsAlpha-Code · 13:04 · 141 views
Number of Pairs of Interchangeable Rectangles LeetCode 2001 solved in javascript.NextGen Programmer · 10:54 · 102 views
Number of Pairs of Interchangeable Rectangle | Array & Hashing | LeetCode 2001 | C++Programming With Niladree - PWN - Bangladesh · 11:42 · 51 views
2001. Number of Pairs of Interchangeable Rectangles - Python - One LineAlgoPrepMaster · 0:56 · 18 views
LeetCode 2001: Number of Pairs of Interchangeable RectanglesAlitaCode · 29:52 · 7 views
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. 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 <= 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.
from collections import defaultdict
def interchangeableRectangles(rectangles):
ratio_count = defaultdict(int)
for w, h in rectangles:
ratio = w / h
ratio_count[ratio] += 1
interchangeable_pairs = 0
for count in ratio_count.values():
if count > 1:
interchangeable_pairs += count * (count - 1) // 2
return interchangeable_pairsimport java.util.HashMap;
public class Solution {
public long interchangeableRectangles(int[][] rectangles) {
HashMap<Double, Long> ratioCount = new HashMap<>();
for (int[] rectangle : rectangles) {
double ratio = (double) rectangle[0] / rectangle[1];
ratioCount.put(ratio, ratioCount.getOrDefault(ratio, 0L) + 1);
}
long interchangeablePairs = 0;
for (long count : ratioCount.values()) {
if (count > 1) {
interchangeablePairs += count * (count - 1) / 2;
}
}
return interchangeablePairs;
}
}#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
long long interchangeableRectangles(vector<vector<int>>& rectangles) {
unordered_map<double, long long> ratio_count;
for (const auto& rectangle : rectangles) {
double ratio = static_cast<double>(rectangle[0]) / rectangle[1];
ratio_count[ratio]++;
}
long long interchangeable_pairs = 0;
for (const auto& entry : ratio_count) {
long long count = entry.second;
if (count > 1) {
interchangeable_pairs += count * (count - 1) / 2;
}
}
return interchangeable_pairs;
}
};using System;
using System.Collections.Generic;
public class Solution {
public long InterchangeableRectangles(int[][] rectangles) {
Dictionary<double, long> ratioCount = new Dictionary<double, long>();
foreach (var rectangle in rectangles) {
double ratio = (double)rectangle[0] / rectangle[1];
if (!ratioCount.ContainsKey(ratio)) {
ratioCount[ratio] = 0;
}
ratioCount[ratio]++;
}
long interchangeablePairs = 0;
foreach (var count in ratioCount.Values) {
if (count > 1) {
interchangeablePairs += count * (count - 1) / 2;
}
}
return interchangeablePairs;
}
}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.
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.
from math import gcd
from collections import defaultdict
def interchangeableRectangles(rectangles):
ratio_count = defaultdict(int)
for w, h in rectangles:
common_divisor = gcd(w, h)
simplified_ratio = (w // common_divisor, h // common_divisor)
ratio_count[simplified_ratio] += 1
interchangeable_pairs = 0
for count in ratio_count.values():
if count > 1:
interchangeable_pairs += count * (count - 1) // 2
return interchangeable_pairsThe 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.
Time Complexity: O(n), where n is the number of rectangles.
Space Complexity: O(n), to store the simplified ratio counts.
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.
/**
* @param {number[][]} rectangles
* @return {number}
*/
var interchangeableRectangles = function (rectangles) {
const cnt = new Map();
let ans = 0;
for (let [w, h] of rectangles) {
const g = gcd(w, h);
w = Math.floor(w / g);
h = Math.floor(h / g);
const x = w * (rectangles.length + 1) + h;
ans += cnt.get(x) | 0;
cnt.set(x, (cnt.get(x) | 0) + 1);
}
return ans;
};
function gcd(a, b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}func interchangeableRectangles(rectangles [][]int) int64 {
ans := 0
n := len(rectangles)
cnt := map[int]int{}
for _, e := range rectangles {
w, h := e[0], e[1]
g := gcd(w, h)
w, h = w/g, h/g
x := w*(n+1) + h
ans += cnt[x]
cnt[x]++
}
return int64(ans)
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
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.