2001. Number of Pairs of Interchangeable Rectangles LeetCode Solution

In this guide, you will get 2001. Number of Pairs of Interchangeable Rectangles LeetCode Solution with the best time and space complexity. The solution to Number of Pairs of Interchangeable Rectangles problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Number of Pairs of Interchangeable Rectangles solution in C++
4. Number of Pairs of Interchangeable Rectangles solution in Java
5. Number of Pairs of Interchangeable Rectangles solution in Python
6. Additional Resources

Problem Statement of 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.

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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

2001. Number of Pairs of Interchangeable Rectangles LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

2001. Number of Pairs of Interchangeable Rectangles LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

2001. Number of Pairs of Interchangeable Rectangles LeetCode Solution in Python

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())
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.