Number of Pairs of Interchangeable Rectangles

Med

#1823Time: O(n^2), where n is the number of rectangles. The nested loops result in a quadratic number of comparisons.Space: O(1), as it only uses a few variables to store loop indices and the final count, regardless of the input size.

Patterns

Math Counting Number Theory

Data structures

Array Hash Table

Prompt

You are given n rectangles represented by a 0-indexed 2D integer array rectangles, where rectangles[i] = [width_i, height_i] denotes the width and height of the i^th 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 width_i/height_i == width_j/height_j (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 <= 10⁵
rectangles[i].length == 2
1 <= width_i, height_i <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. It involves checking every possible pair of rectangles to see if they are interchangeable. While simple to conceive and implement, its performance is poor for large datasets.

Algorithm

Initialize a counter count to 0.
Use a nested loop to iterate through all pairs of indices (i, j) such that 0 <= i < j < n, where n is the number of rectangles.
For each pair, get their dimensions: w1, h1 for rectangle i and w2, h2 for rectangle j.
To check for interchangeability (w1/h1 == w2/h2) without using floating-point numbers, use cross-multiplication: w1 * h2 == w2 * h1.
To avoid potential integer overflow, cast the dimensions to a 64-bit integer type (long in Java) before multiplying.
If the cross-multiplication products are equal, increment the count.
After the loops complete, return the final count.

Walkthrough

The brute-force method iterates through all unique pairs of rectangles. For each pair of rectangles, i and j, we compare their width-to-height ratios. A direct comparison using floating-point division (width_i / height_i == width_j / height_j) can be prone to precision errors. A more reliable method is to use integer arithmetic with cross-multiplication: width_i * height_j == width_j * height_i. Since the product of widths and heights can exceed the capacity of a standard 32-bit integer (up to 10^5 * 10^5 = 10^10), we must use a 64-bit integer type (long in Java) for the calculation to prevent overflow. We maintain a counter, which is incremented for every pair that satisfies this condition.

1class Solution {2    public long interchangeableRectangles(int[][] rectangles) {3        long count = 0;4        int n = rectangles.length;5        for (int i = 0; i < n; i++) {6            for (int j = i + 1; j < n; j++) {7                long w1 = rectangles[i][0];8                long h1 = rectangles[i][1];9                long w2 = rectangles[j][0];10                long h2 = rectangles[j][1];11                if (w1 * h2 == w2 * h1) {12                    count++;13                }14            }15        }16        return count;17    }18}

Complexity

Time

O(n^2), where n is the number of rectangles. The nested loops result in a quadratic number of comparisons.

Space

O(1), as it only uses a few variables to store loop indices and the final count, regardless of the input size.

Trade-offs

Pros

Simple to understand and implement.
Requires no extra space, making it very memory-efficient.

Cons

Extremely inefficient for large inputs due to its quadratic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints (n up to 10^5).

A more efficient approach involves grouping rectangles by their width-to-height ratio. By using a HashMap, we can count the occurrences of each ratio in a single pass. For each group of k rectangles with the same ratio, they form k * (k-1) / 2 pairs. This method avoids the expensive quadratic pair-wise comparison.

Algorithm

Initialize a total pair count count to 0.
Create a HashMap, ratioCounts, to store the frequency of each ratio. The key will be the double ratio, and the value will be its frequency (long).
Iterate through each rectangle in the input array rectangles.
For the current rectangle, calculate its width-to-height ratio as a double: ratio = (double)width / height.
Look up this ratio in the ratioCounts map to find how many rectangles with this same ratio have been seen before. Let this be previousCount.
The current rectangle can form a new pair with each of those previousCount rectangles. So, add previousCount to the total count.
Increment the frequency of the current ratio in the map. ratioCounts.put(ratio, previousCount + 1).
After iterating through all rectangles, return the total count.

Walkthrough

Instead of comparing every rectangle with every other rectangle, we can optimize the process by grouping rectangles that have the same ratio. The problem then becomes counting the number of pairs we can form within each group.

We can iterate through the list of rectangles once. For each rectangle, we calculate its width-to-height ratio. We use a HashMap to keep track of how many times we've seen each specific ratio so far.

When we encounter a rectangle with a certain ratio, we check the HashMap. If we have already seen k rectangles with this same ratio, it means our current rectangle can form k new interchangeable pairs. We add k to our total count of pairs. Then, we update the HashMap to reflect that we have now seen k+1 rectangles with this ratio. This process is repeated for all rectangles, and the final accumulated count is the answer.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public long interchangeableRectangles(int[][] rectangles) {6        Map<Double, Long> ratioCounts = new HashMap<>();7        long count = 0;8 9        for (int[] rect : rectangles) {10            double ratio = (double) rect[0] / rect[1];11            long currentCount = ratioCounts.getOrDefault(ratio, 0L);12            count += currentCount;13            ratioCounts.put(ratio, currentCount + 1);14        }15 16        return count;17    }18}

Complexity

Time

O(n), where n is the number of rectangles. We iterate through the array once, and each HashMap operation (get and put) takes, on average, O(1) time.

Space

O(U), where `U` is the number of unique ratios. In the worst-case scenario where all rectangles have different ratios, the space complexity is O(n).

Trade-offs

Pros

Highly efficient with a linear time complexity, making it suitable for large inputs.
Conceptually elegant, solving the problem by counting groups rather than individual pairs.

Cons

Requires extra space for the HashMap, which can be up to O(n) in the worst case.
Using double as a HashMap key can be risky due to floating-point precision issues, though it often works for this type of problem. A more robust (but slightly more complex) implementation would simplify the fraction width/height using the Greatest Common Divisor (GCD) and use the resulting pair or a string representation as the key.

Solutions

Solution

1class Solution {2public3  long interchangeableRectangles(int[][] rectangles) {4    long ans = 0;5    int n = rectangles.length + 1;6    Map<Long, Integer> cnt = new HashMap<>();7    for (var e : rectangles) {8      int w = e[0], h = e[1];9      int g = gcd(w, h);10      w /= g;11      h /= g;12      long x = (long)w * n + h;13      ans += cnt.getOrDefault(x, 0);14      cnt.merge(x, 1, Integer : : sum);15    }16    return ans;17  }18private19  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }20}

1/** * @param {number[][]} rectangles * @return {number} */ var interchangeableRectangles =2  function (rectangles) {3    const cnt = new Map();4    let ans = 0;5    for (let [w, h] of rectangles) {6      const g = gcd(w, h);7      w = Math.floor(w / g);8      h = Math.floor(h / g);9      const x = w * (rectangles.length + 1) + h;10      ans += cnt.get(x) | 0;11      cnt.set(x, (cnt.get(x) | 0) + 1);12    }13    return ans;14  };15function gcd(a, b) {16  if (b == 0) {17    return a;18  }19  return gcd(b, a % b);20}

1class Solution {2public:3  long long interchangeableRectangles(vector<vector<int>> &rectangles) {4    long long ans = 0;5    int n = rectangles.size();6    unordered_map<long long, int> cnt;7    for (auto &e : rectangles) {8      int w = e[0], h = e[1];9      int g = gcd(w, h);10      w /= g;11      h /= g;12      long long x = 1ll * w * (n + 1) + h;13      ans += cnt[x];14      cnt[x]++;15    }16    return ans;17  }18};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem