Number Of Pairs Of Interchangeable Rectangles Leetcode [Python]

Welcome to another coding adventure!

In this blog post, we'll be tackling the Number Of Pairs Of Interchangeable Rectangles problem, a medium-level challenge from LeetCode.

We'll walk through the problem statement, its constraints, and provide both a brute-force and an efficient solution in Python.

So, let's dive in!

Problem Overview

The problem revolves around a set of rectangles represented as a 2D integer array, where each element is of the form [widthi, heighti], indicating the width and height of the ith rectangle.

Two rectangles i and j (where i < j) are considered interchangeable if they share the same width-to-height ratio, expressed as widthi/heighti == widthj/heightj.

The task at hand is to count the number of pairs of interchangeable rectangles in the given set.

Example 1:

Input: rectangles = [[4,8],[3,6],[10,20],[15,30]]
Output: 6

Explanation: In this example, we can identify the following 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: In this case, there are no interchangeable pairs of rectangles.

Understanding the Constraints

Before delving into the solution, let's take a closer look at the constraints given in the problem:

• n == rectangles.length: This means the number of rectangles should match the length of the input array.
• 1 <= n <= 105: There can be between 1 and 105 rectangles.
• rectangles[i].length == 2: Each rectangle is represented as a 2-element array.
• 1 <= widthi, heighti <= 105: The width and height of each rectangle are positive integers ranging from 1 to 105. Now that we have a good grasp of the problem, its examples, and the constraints, let's explore the solutions.

Brute-Force Approach

A brute-force approach to this problem would involve checking every pair of rectangles to determine if they are interchangeable.

This approach has a time complexity of O(n^2), which might not be efficient for large inputs but is a good starting point for understanding the problem.

def interchangeableRectangles(rectangles):
    count = {}  # { Width / Height Ratio: Count }
    res = 0

    for w, h in rectangles:
        # Increment the count for the ratio
        count[w / h] = 1 + count.get(w / h, 0)

    for c in count.values():
        res += (c * (c - 1)) // 2

    return res

In the code above, we maintain a dictionary count to keep track of the count of rectangles with each unique ratio.

We iterate through the input rectangles and calculate the ratio for each one.

If the ratio is not in the dictionary, we initialize it with a count of 1. If the ratio is already in the dictionary, we increment its count.

After processing all rectangles, we calculate the number of pairs for each unique ratio using the formula (count * (count - 1)) // 2 and add it to the result.

Finally, we return the total count of interchangeable pairs.

Efficient Approach

The brute-force approach works fine, but there's a more efficient way to solve this problem.

Instead of storing the count of each unique ratio, we can utilize the concept of combinations from mathematics.

The formula for combinations of n items taken k at a time is n! / (k! * (n - k)!).

In our case, n represents the count of rectangles with the same ratio, and k is 2 because we want pairs.

The more generic formula for combinations is n! / (k! * (n - k)!).

In our context, with k = 2, it simplifies to n! / (2! * (n - 2)!), which can be further simplified to (n * (n - 1)) / 2.

We can use this formula to calculate the number of pairs for each ratio efficiently.

def interchangeableRectangles(rectangles):
    count = {}  # { Width / Height Ratio: Count }
    res = 0

    for w, h in rectangles:
        # Increment the count for the ratio
        count[w / h] = 1 + count.get(w / h, 0)

    for c in count.values():
        res += (c * (c - 1)) // 2

    return res

Time and Space Complexity

Time Complexity: In both the brute-force and efficient approaches, we iterate through the input array of rectangles once, which takes O(n) time.

The additional operations to calculate pairs and maintain the dictionary do not increase the time complexity.

So, the time complexity of our solution is O(n).

Space Complexity: We use a dictionary to store the counts of ratios, which can have up to n unique ratios.

Therefore, the space complexity is O(n).

Reasoning Behind Our Approach

The reasoning behind the approach lies in the problem's mathematical nature.

We identify interchangeable rectangles based on their width-to-height ratios.

By efficiently counting the rectangles with the same ratio and applying a mathematical combination formula, we can find the number of interchangeable pairs in a time-efficient manner.

Related Interview Questions By Company:

• Insert Interval LeetCode
• Reorganize String LeetCode
• Longest Substring Without Repeating Characters LeetCode

Related Interview Questions By Difficulty:

• Subarray Sum Equals K LeetCode
• Isomorphic Strings LeetCode
• Best Time To Buy And Sell Stock II LeetCode

Conclusion

In this blog post, we tackled the Number Of Pairs Of Interchangeable Rectangles problem from LeetCode.

We explored the problem statement, examined its constraints, and provided both a brute-force and an efficient solution in Python.

We also delved into the mathematical reasoning behind the efficient approach.

If you found this guide helpful, please consider liking and subscribing to support our our platform.

If you have any questions, suggestions, or alternative solutions, please don't hesitate to comment and share your thoughts.

We hope this post has been valuable to you as you continue your coding journey!

Question Link: Number of Pairs of Interchangeable Rectangles on LeetCode