Arrays - 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 i^th 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.

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.

Input: rectangles = [[4,5],[7,8]]
Output: 0
Explanation: There are no interchangeable pairs of rectangles.

Constraints:

1 <= nums.length <= 2 * 10⁴
-1000 <= nums[i] <= 1000
-10⁷ <= k <= 10⁷

Solution 1 - Store ratio counts and find unique pairs of answers

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. 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 $[\begin{matrix} n * (n-1) \\ _____________ \\ 2 \end{matrix}]$
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].

A generic formula to calculate k unique combincations from n values is:

result = [\begin{matrix} n ! \\ ________________ \\ (n-k) ! * k! \end{matrix}]

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.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: