[LeetCode] Number of Pairs of Interchangeable Rectangles

2001. Number of Pairs of Interchangeable Rectangles

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
string hash(int a, int b) {
return to_string(a) + "#" + to_string(b);
}
public:
long long interchangeableRectangles(vector<vector<int>>& A) {
long long res = 0;
unordered_map<string, long long> freq;
for(auto& a : A) {
int h = a[0], w = a[1], g = __gcd(h,w);
h /= g, w /= g;
res += freq[hash(h,w)]++;
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/08/12/PS/LeetCode/number-of-pairs-of-interchangeable-rectangles/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.