Number of Pairs of Interchangeable Rectangles

MEDIUM

Description

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

Checkout 2 different approaches to solve Number of Pairs of Interchangeable Rectangles. Click on different approaches to view the approach and algorithm in detail.

Brute Force

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.

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.

class Solution {
    public long interchangeableRectangles(int[][] rectangles) {
        long count = 0;
        int n = rectangles.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long w1 = rectangles[i][0];
                long h1 = rectangles[i][1];
                long w2 = rectangles[j][0];
                long h2 = rectangles[j][1];
                if (w1 * h2 == w2 * h1) {
                    count++;
                }
            }
        }
        return count;
    }
}

Complexity Analysis

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

Pros and Cons

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

Code Solutions

Checking out 4 solutions in different languages for Number of Pairs of Interchangeable Rectangles. Click on different languages to view the code.

class Solution {
public
  long interchangeableRectangles(int[][] rectangles) {
    long ans = 0;
    int n = rectangles.length + 1;
    Map<Long, Integer> cnt = new HashMap<>();
    for (var e : rectangles) {
      int w = e[0], h = e[1];
      int g = gcd(w, h);
      w /= g;
      h /= g;
      long x = (long)w * n + h;
      ans += cnt.getOrDefault(x, 0);
      cnt.merge(x, 1, Integer : : sum);
    }
    return ans;
  }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

Video Solution

Watch the video walkthrough for Number of Pairs of Interchangeable Rectangles

Patterns:

MathCountingNumber Theory

Data Structures:

ArrayHash Table