Start by computing the ratio of width to height for each rectangle and store counts in a hash map. Each time a ratio repeats, it forms new interchangeable pairs, which can be summed incrementally. This approach avoids checking all O(n^2) pairs, leveraging array scanning with a hash table for speed and accuracy.
Problem Statement
You are given a list of rectangles represented as a 2D array rectangles, where each rectangle is defined by its width and height. Two rectangles are interchangeable if they have the same width-to-height ratio, using decimal division for precision.
Return the total number of pairs (i, j) with i < j where rectangles[i] and rectangles[j] are interchangeable. Each rectangle may appear in multiple pairs if its ratio matches multiple other rectangles.
Examples
Example 1
Input: rectangles = [[4,8],[3,6],[10,20],[15,30]]
Output: 6
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.
Example 2
Input: rectangles = [[4,5],[7,8]]
Output: 0
There are no interchangeable pairs of rectangles.
Constraints
- n == rectangles.length
- 1 <= n <= 105
- rectangles[i].length == 2
- 1 <= widthi, heighti <= 105
Solution Approach
Compute Ratios and Use Hash Map
Iterate over each rectangle, compute its width divided by height as a decimal, and store the count of each unique ratio in a hash map. This prepares for pair counting without nested loops.
Count Pairs Incrementally
For each rectangle, if its ratio is already in the hash map, increment the total pairs by the current count of that ratio. Then update the hash map count. This counts all valid pairs efficiently.
Return Total Pair Count
After processing all rectangles, return the accumulated pair count. This uses O(n) time for array scanning and hash operations, avoiding explicit O(n^2) comparisons.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) due to a single pass through the rectangles and O(1) hash operations per rectangle. Space complexity is O(n) for storing ratio counts in the hash map.
What Interviewers Usually Probe
- Look for candidates to optimize from O(n^2) pair checking to hash-based counting.
- Expect discussion on precision when dividing integers to form accurate ratios.
- Check whether candidates consider edge cases with identical width or height values.
Common Pitfalls or Variants
Common pitfalls
- Using integer division instead of decimal division when calculating ratios, leading to incorrect pair counting.
- Nested loops for pair comparison, which causes timeouts on large inputs.
- Failing to correctly increment pair counts based on existing ratio counts in the hash map.
Follow-up variants
- Count pairs of rectangles that are exact matches in width and height instead of ratios.
- Return the list of all interchangeable rectangle index pairs rather than just the count.
- Handle rectangles where dimensions are very large, requiring careful numeric precision for ratios.
How GhostInterview Helps
- Automatically detects the array scanning plus hash lookup pattern and highlights ratio counting opportunities.
- Provides step-by-step guidance on incrementally counting pairs without nested loops.
- Warns about common mistakes like integer division and miscounted hash map entries.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the key pattern to solve Number of Pairs of Interchangeable Rectangles efficiently?
Use array scanning plus a hash map to track width-to-height ratios, incrementing counts as you encounter repeated ratios.
Why is integer division incorrect for this problem?
Integer division truncates decimals, which can make distinct ratios appear equal and miscount interchangeable pairs.
Can I use nested loops to check all rectangle pairs?
Technically yes, but it leads to O(n^2) time complexity and will likely time out on large inputs.
How does a hash map help in counting pairs?
It stores the number of times each ratio occurs, allowing you to calculate new pairs in O(1) per rectangle.
What constraints should I consider for width and height values?
Width and height values are up to 10^5, so using proper numeric types and decimal division is necessary to avoid precision issues.
Need direct help with Number of Pairs of Interchangeable Rectangles instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Number of Pairs of Interchangeable Rectangles from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the number of good subsets in an integer array, where each subset's product is the product of distinct primes.
Open problem page#2748 Number of Beautiful PairsCount all index pairs in an array where the first digit of one number and last digit of another are coprime efficiently.
Open problem page#3044 Most Frequent PrimeFind the most frequent prime over 10 from numbers generated by scanning a 2D matrix in all straight directions efficiently.
Open problem page