Skip to content

2001. Number of Pairs of Interchangeable Rectangles 👍

Approach 1: Less accurate

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  long long interchangeableRectangles(vector<vector<int>>& rectangles) {
    long long ans = 0;
    unordered_map<double, int> ratioCount;

    for (const vector<int>& r : rectangles)
      ++ratioCount[(double)r[0] / r[1]];

    for (const auto& [_, count] : ratioCount)
      ans += static_cast<long>(count) * (count - 1) / 2;

    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public long interchangeableRectangles(int[][] rectangles) {
    long ans = 0;
    Map<Double, Integer> ratioCount = new HashMap<>();

    for (int[] r : rectangles)
      ratioCount.merge((double) r[0] / r[1], 1, Integer::sum);

    for (final int count : ratioCount.values())
      ans += (long) count * (count - 1) / 2;

    return ans;
  }
}
1
2
3
4
5
6
7
8
class Solution:
  def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
    ratioCount = Counter()

    for width, height in rectangles:
      ratioCount[width / height] += 1

    return sum(c * (c - 1) // 2 for c in ratioCount.values())

Approach 2: More accurate

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  long long interchangeableRectangles(vector<vector<int>>& rectangles) {
    long long ans = 0;
    unordered_map<pair<int, int>, int, pairHash> ratioCount;

    for (const vector<int>& r : rectangles) {
      const int width = r[0];
      const int height = r[1];
      const int d = __gcd(width, height);
      ++ratioCount[{width / d, height / d}];
    }

    for (const auto& [_, count] : ratioCount)
      ans += static_cast<long>(count) * (count - 1) / 2;

    return ans;
  }

 private:
  struct pairHash {
    size_t operator()(const pair<int, int>& p) const {
      return p.first ^ p.second;
    }
  };
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public long interchangeableRectangles(int[][] rectangles) {
    long ans = 0;
    Map<Pair<Integer, Integer>, Integer> ratioCount = new HashMap<>();

    for (int[] r : rectangles) {
      final int width = r[0];
      final int height = r[1];
      final int d = gcd(width, height);
      ratioCount.merge(new Pair<>(width / d, height / d), 1, Integer::sum);
    }

    for (final int count : ratioCount.values())
      ans += (long) count * (count - 1) / 2;

    return ans;
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
    ratioCount = Counter()

    def gcd(a: int, b: int) -> int:
      return a if b == 0 else gcd(b, a % b)

    for width, height in rectangles:
      d = gcd(width, height)
      ratioCount[(width // d, height // d)] += 1

    return sum(c * (c - 1) // 2 for c in ratioCount.values())