Back to solutions

Number of Pairs of Interchangeable Rectangles

MediumArrays

Count rectangle pairs with equal width-to-height ratio.

Open problem
Constraints
  • 1 <= n <= 10^5
  • 1 <= width, height <= 10^5

Group by ratio, count pairs

Time O(n)Space O(n)

Reduce each rectangle to its width/height ratio. Rectangles with equal ratios are interchangeable. Sweep once: for each rectangle, the number of new pairs it forms equals how many earlier rectangles already had its ratio, so add the running count for that ratio before incrementing it.

Key terms
ratio key:
A canonical representation of width/height (an exact fraction or a double) used to group rectangles.
pair counting:
Each new equal item adds as many pairs as items already in its group.
long long interchangeableRectangles(vector<vector<int>>& rects) {
    unordered_map<double, long long> cnt;
    long long pairs = 0;
    for (auto& r : rects) {
        double ratio = (double)r[0] / r[1];
        pairs += cnt[ratio]++;
    }
    return pairs;
}
Step by step
  1. Maintain a map from ratio to how many rectangles have it so far.
  2. For each rectangle, compute its ratio.
  3. Add the current count for that ratio to the answer (new pairs with earlier ones).
  4. Increment the count for that ratio.