Number of Pairs of Interchangeable Rectangles
MedPrompt
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
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
countto 0. - Use a nested loop to iterate through all pairs of indices
(i, j)such that0 <= i < j < n, wherenis the number of rectangles. - For each pair, get their dimensions:
w1, h1for rectangleiandw2, h2for rectanglej. - 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 (
longin 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.
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
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).
Solutions
Solution
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 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.