Number of Pairs of Interchangeable Rectangles

Number of Pairs of Interchangeable Rectangles - Problem

Array Hash Table Math Counting Number Theory Medium

You are given n rectangles represented by a 0-indexed 2D integer array rectangles, where rectangles[i] = [width_i, height_i] denotes the width and height of the i^th rectangle.

Two rectangles i and j (where i < j) are considered interchangeable if they have the same width-to-height ratio. More formally, two rectangles are interchangeable if width_i/height_i == width_j/height_j (using decimal division, not integer division).

Return the number of pairs of interchangeable rectangles in rectangles.

Input & Output

Example 1 — Basic Case

$ Input: rectangles = [[4,6],[8,10],[4,8],[2,4]]

› Output: 1

💡 Note: Rectangles [4,8] and [2,4] have the same ratio 1:2 (4/8 = 2/4 = 0.5), forming 1 interchangeable pair

Example 2 — Multiple Groups

$ Input: rectangles = [[4,8],[3,6],[10,20],[12,16]]

› Output: 3

💡 Note: Three pairs: [4,8] & [10,20] (ratio 1:2), [3,6] & [12,16] (both simplify to ratio 1:2), and [4,8] & [3,6] & [10,20] & [12,16] all have ratio 1:2, giving us C(4,2) = 6 total pairs

Example 3 — No Matches

$ Input: rectangles = [[1,2],[2,3],[3,4]]

› Output: 0

💡 Note: All rectangles have different ratios: 1/2, 2/3, 3/4. No pairs are interchangeable

Constraints

n == rectangles.length
1 ≤ n ≤ 10⁵
rectangles[i].length == 2
1 ≤ width_i, height_i ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Rectangles

Array of [width, height] pairs representing rectangles

Calculate Ratios

Find simplified width:height ratio for each rectangle

Count Pairs

Rectangles with same ratio are interchangeable

Key Takeaway

🎯 Key Insight: Rectangles are interchangeable when they have the same simplified width-to-height ratio

Asked in

G Google 15 a Amazon 12 f Facebook 8

The key insight is to group rectangles by their simplified width-to-height ratios. Use GCD to avoid floating point precision issues and count pairs using combination formula. Best approach is hash map grouping with Time: O(n × log(min(w,h))), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map with Ratio Counting	O(n × log(min(w,h)))	O(n)	Group rectangles by their simplified ratios and count pairs in each group
Brute Force	O(n²)	O(1)	Check every pair of rectangles to see if their ratios match

Hash Map with Ratio Counting — Algorithm Steps

Step 1: Calculate GCD to simplify each ratio
Step 2: Count rectangles for each unique ratio
Step 3: Calculate pairs using combination formula k*(k-1)/2

Visualization

Tap to expand

Step-by-Step Walkthrough

Simplify Ratios

Use GCD to reduce each ratio to lowest terms

Group & Count

Count rectangles for each unique ratio

Calculate Pairs

Use formula k*(k-1)/2 for each group

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

struct RatioCount {
    int width, height;
    int count;
};

long long solution(int rectangles[][2], int n) {
    struct RatioCount ratios[1000];
    int uniqueRatios = 0;
    
    for (int i = 0; i < n; i++) {
        int width = rectangles[i][0], height = rectangles[i][1];
        // Simplify ratio using GCD
        int g = gcd(width, height);
        int simpWidth = width / g, simpHeight = height / g;
        
        // Find or create entry for this ratio
        int found = 0;
        for (int j = 0; j < uniqueRatios; j++) {
            if (ratios[j].width == simpWidth && ratios[j].height == simpHeight) {
                ratios[j].count++;
                found = 1;
                break;
            }
        }
        
        if (!found) {
            ratios[uniqueRatios].width = simpWidth;
            ratios[uniqueRatios].height = simpHeight;
            ratios[uniqueRatios].count = 1;
            uniqueRatios++;
        }
    }
    
    long long totalPairs = 0;
    for (int i = 0; i < uniqueRatios; i++) {
        int count = ratios[i].count;
        // For k rectangles with same ratio, pairs = k*(k-1)/2
        totalPairs += (long long) count * (count - 1) / 2;
    }
    
    return totalPairs;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for 2D array
    int rectangles[1000][2];
    int n = 0;
    char* ptr = line + 1; // Skip first '['
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            rectangles[n][0] = atoi(ptr);
            while (*ptr != ',') ptr++;
            ptr++;
            rectangles[n][1] = atoi(ptr);
            while (*ptr != ']') ptr++;
            ptr++;
            n++;
        } else {
            ptr++;
        }
    }
    
    printf("%lld\n", solution(rectangles, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × log(min(w,h)))

Single pass through rectangles, each GCD calculation takes O(log(min(w,h))) time

⚡ Linearithmic

Space Complexity

O(n)

Hash map stores up to n unique ratios in worst case

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map with Ratio Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler