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
16
17
18
class Solution {
 public:
  long long interchangeableRectangles(vector<vector<int>>& rectangles) {
    long ans = 0;
    unordered_map<double, int> ratioCount;

    for (const vector<int>& rectangle : rectangles) {
      const int width = rectangle[0];
      const int height = rectangle[1];
      ++ratioCount[1.0 * width / height];
    }

    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
15
16
17
class Solution {
  public long interchangeableRectangles(int[][] rectangles) {
    long ans = 0;
    Map<Double, Integer> ratioCount = new HashMap<>();

    for (int[] rectangle : rectangles) {
      final int width = rectangle[0];
      final int height = rectangle[1];
      ratioCount.merge(1.0 * width / height, 1, Integer::sum);
    }

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

    return ans;
  }
}

1
2
3
4
5
6
7
8
9
class Solution:
  def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
    ratioCount = collections.Counter()

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

    return sum(count * (count - 1) // 2
               for count 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 ans = 0;
    unordered_map<pair<int, int>, int, PairHash> ratioCount;

    for (const vector<int>& rectangle : rectangles) {
      const int width = rectangle[0];
      const int height = rectangle[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[] rectangle : rectangles) {
      final int width = rectangle[0];
      final int height = rectangle[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 = collections.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())