Solution Explanation: Number of Pairs of Interchangeable Rectangles

This problem asks us to find the number of pairs of rectangles that have the same width-to-height ratio. A naive approach would involve comparing every pair of rectangles, resulting in O(n²) time complexity. A more efficient solution leverages the properties of ratios and hash tables.

Core Idea:

The key is to recognize that we only care about the ratio of width to height, not the absolute values. Two rectangles are interchangeable if their simplified ratios are identical. We can simplify a ratio by finding the greatest common divisor (GCD) of the width and height and dividing both by it. This gives us the simplest fractional representation of the ratio.

Algorithm:

1. Simplify Ratios: Iterate through the rectangles array. For each rectangle [width, height], calculate the GCD of width and height. Then, divide both width and height by the GCD to get the simplified ratio.

2. Count Occurrences: Use a hash table (dictionary in Python, HashMap in Java, etc.) to store the simplified ratios as keys and the count of rectangles with that ratio as values. For each simplified ratio encountered, increment its count in the hash table.

3. Calculate Pairs: After processing all rectangles, iterate through the hash table. For each ratio, calculate the number of pairs that can be formed from the rectangles with that ratio. This is simply the combination formula: n! / (2! * (n-2)!), where n is the count of rectangles with that ratio. This simplifies to n * (n-1) / 2. Add this number of pairs to the total count.

4. Return Total: Return the total count of interchangeable pairs.

Time Complexity: O(n log M), where n is the number of rectangles and M is the maximum value of width or height. The dominant factor is calculating the GCD for each rectangle (Euclidean algorithm is O(log M)). The hash table operations (insertion, lookup) are typically O(1) on average.

Space Complexity: O(n), in the worst case, where each rectangle has a unique ratio, and we store all n ratios in the hash table.

Code Examples:

The code examples below illustrate the algorithm in different programming languages. Note that the gcd function (for calculating the greatest common divisor) may need to be implemented separately depending on the language. Many languages provide this function in their standard libraries (e.g., math.gcd in Python).

Python:

from math import gcd
from collections import Counter
 
def interchangeableRectangles(rectangles):
    ratios = []
    for w, h in rectangles:
        g = gcd(w, h)
        ratios.append((w // g, h // g))
 
    count = Counter(ratios)
    total_pairs = 0
    for ratio, num_rectangles in count.items():
        total_pairs += num_rectangles * (num_rectangles - 1) // 2
    return total_pairs
 

Java:

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public long interchangeableRectangles(int[][] rectangles) {
        Map<String, Integer> ratioCounts = new HashMap<>();
        long totalPairs = 0;
 
        for (int[] rect : rectangles) {
            int w = rect[0];
            int h = rect[1];
            int gcd = findGCD(w, h);
            String ratio = (w / gcd) + "/" + (h / gcd); 
            ratioCounts.put(ratio, ratioCounts.getOrDefault(ratio, 0) + 1);
        }
 
        for (int count : ratioCounts.values()) {
            totalPairs += (long)count * (count - 1) / 2;
        }
 
        return totalPairs;
    }
 
    private int findGCD(int a, int b) {
        if (b == 0) return a;
        return findGCD(b, a % b);
    }
}

C++:

#include <vector>
#include <numeric> // for std::gcd
#include <map>
 
using namespace std;
 
long long interchangeableRectangles(vector<vector<int>>& rectangles) {
    map<pair<int, int>, int> ratioCounts;
    long long totalPairs = 0;
 
    for (const auto& rect : rectangles) {
        int w = rect[0];
        int h = rect[1];
        int gcd = std::gcd(w, h);
        pair<int, int> ratio = {w / gcd, h / gcd};
        ratioCounts[ratio]++;
    }
 
    for (const auto& pair : ratioCounts) {
        totalPairs += (long long)pair.second * (pair.second - 1) / 2;
    }
 
    return totalPairs;
}

These examples demonstrate the core algorithm. The specific implementation details (like handling of ratios as strings or pairs) may vary slightly depending on the language and personal preferences. However, the overall time and space complexity remain the same.