2001

2001. Number of Pairs of Interchangeable Rectangles (Medium)

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.length
• 1 <= n <= 105
• rectangles[i].length == 2
• 1 <= widthi, heighti <= 105

Similar Questions:

• Number of Good Pairs (Easy)
• Count Nice Pairs in an Array (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/number-of-pairs-of-interchangeable-rectangles/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    long long interchangeableRectangles(vector<vector<int>>& A) {
        unordered_map<double, int> m;
        long long ans = 0;
        for (auto &a : A) {
            double r = (double)a[0] / a[1];
            ans += m[r];
            m[r]++;
        }
        return ans;
    }
};