Number Of Pairs Of Interchangeable Rectangles - Leetcode Solution

Problem Statement:

Given n rectangles where the i-th rectangle has a width of widths[i] and height of heights[i], return the number of pairs of overlapping rectangles. A pair of rectangles (i, j) is called interchangeable if min(widths[i], heights[i]) == min(widths[j], heights[j]).

Solution:

Algorithm:

1. Create a dictionary to store the frequency of each possible value of min(widths[i], heights[i]).
2. Iterate through the rectangles: For each rectangle, calculate its value of min(widths[i], heights[i]) and add it to the corresponding frequency count in the dictionary.
3. For each value in the dictionary, calculate the number of pairs that can be formed using the formula n * (n - 1) / 2 where n is the frequency count. Add this count to a variable to keep track of the total number of pairs.
4. Return the total number of pairs.

Python Code:

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        freq = dict()
        for i in range(len(rectangles)):
            val = min(rectangles[i][0], rectangles[i][1])
            if val in freq:
                freq[val] += 1
            else:
                freq[val] = 1
                
        count = 0
        for val in freq:
            n = freq[val]
            count += n * (n - 1) / 2
                
        return int(count)

Time Complexity:

The time complexity of the algorithm is O(n) where n is the number of rectangles.

Space Complexity:

The space complexity of the algorithm is O(n) where n is the number of rectangles.

1