Is Number of Pairs of Interchangeable Rectangles easy or hard?

This problem is classified as Medium difficulty. The challenge is recognizing that interchangeable rectangles share the same ratio and that pair counting can be optimized using a hash map. Once that insight is clear, the implementation is straightforward.

Number of Pairs of Interchangeable Rectangles Python/Java solution

Python and Java implementations typically use a dictionary or HashMap to track ratio frequencies. Each rectangle is normalized using either floating-point division or GCD reduction, then counted using the hash map. The algorithm processes the array once, giving O(n) time complexity.

How to solve Number of Pairs of Interchangeable Rectangles in O(n)?

Iterate through the rectangles and compute a ratio representation for each one. Store the ratio in a hash map with its frequency. When a ratio appears again, add the existing frequency to the pair count before incrementing it. Using GCD to normalize (width, height) ensures ratios are stored consistently.

What is the best approach for Number of Pairs of Interchangeable Rectangles?

The most efficient approach uses a hash map to count rectangle ratios. Convert each rectangle into a width-to-height ratio and track how many times the same ratio has appeared before. Every previous occurrence forms a valid pair. This method runs in O(n) time and O(n) space.

Is Number of Pairs of Interchangeable Rectangles asked at Google/Amazon/Meta?

Ratio counting and hash map frequency problems frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, the technique of reducing ratios and counting pairs with hashing is a common interview pattern.

What data structure is used in Number of Pairs of Interchangeable Rectangles?

A hash map is the primary data structure used to store the frequency of each rectangle ratio. The key represents the normalized ratio, and the value tracks how many rectangles share it. This allows constant-time lookups while counting valid pairs.

What is the time complexity of Number of Pairs of Interchangeable Rectangles?

The optimal solution runs in O(n) time because each rectangle is processed once while updating a hash map of ratios. Space complexity is O(n) in the worst case when all rectangles have unique ratios. A brute force solution would require O(n²) comparisons.

Description Hints 2 Solution Video 7:49

2001. Number of Pairs of Interchangeable Rectangles

Medium53.1% acceptance2 companies

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 (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.

Example 1:

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.

Example 2:

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

Constraints:

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

Asked at 2 companies

Google Amazon

Topics

Hints open one at a time

Hint 1

Store the rectangle height and width ratio in a hashmap.

Hint 2

Traverse the ratios, and for each ratio, use the frequency of the ratio to add to the total pair count.

7:49

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution