Number of Pairs of Interchangeable Rectangles

In this approach, we are going to compute width-to-height ratio and store them into a HashMap with key as ratio and value as, how many of same width-to-height ratio rectangles found, then finally get the unique pairs from the HashMap.

Implementation steps:

• Create a HashMap to store width-to-height counts, and call it ratioCount.
• Iterate through each rectangle from input rectangles.
• Next, calculate the width-to-height ratio for each rectangle.
  Java

  double ratio = (double) rectangle[0] / rectangle[1];

• In next step, store this into ratioCount HashMap, if the ratio is already exist, increment value by 1, otherwise add 1.
• Now, go through each ratio count stored in ratioCount HashMap, calculate the number of pairs that can be formed using the count of rectangles with that ratio.
  • The number of pairs for a count n of rectangles with the same ratio is $\left[\begin{array}{c}\mathrm{n\; *\; (n-1)}\\ \mathrm{\_\_\_\_\_\_\_\_\_\_\_\_\_}\\ 2\end{array}\right]$
  Example:
  For example, if the input is rectangles = [[4,8],[3,6],[10,20],[15,30]] , all the rectangles will have same ratio 0.5 and the count of rectangles is 4, to get the unique pairs of rectangles we can use 4 *3 / 2.
  Unique pairs are [4,8],[3,6], [4,8],[10,20], [4,8],[15,30], [3,6],[10,20], [3,6],[15,30] and [10,20],[15,30].

Note: A generic formula to calculate k unique combincations from n values is: $\mathrm{result}=\left[\begin{array}{c}\mathrm{n\; !}\\ \mathrm{\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_}\\ \mathrm{(n-k)\; !\; *\; k!}\end{array}\right]$

import java.util.HashMap;

public class InterChangeableRectanglePairs {

    static long interchangeableRectangles(int[][] rectangles) {
        HashMap<Double, Long> ratioCount  = new HashMap<>();

        // calculate and store the ratio counts
        for(int[] rectangle: rectangles) {
            double ratio = (double)rectangle[0] / rectangle[1];
            ratioCount.merge(ratio, 1l, Long::sum);
        }

        //calculate pairs for each unique ratio
        //Generic formula for an array of n numbers with k distinct groupings
        // n! / (n-k)! * k!
        int result = 0;
        for(Long uniquePairCount: ratioCount.values()) {
            result += (uniquePairCount * (uniquePairCount -1) ) /2;
        }
        return result;
    }

}

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of rectangles array.
Space complexity: O(n), since we are storing width-to-height ratios into a HashMap.