Leetcode 2001: Number of Pairs of Interchangeable Rectangles
You are given a list of rectangles, each represented by its width and height. Two rectangles are interchangeable if their width-to-height ratios are the same. Your task is to return the number of interchangeable rectangle pairs in the list.
Problem
Approach
Steps
Complexity
Input: The input consists of a list of rectangles, where each rectangle is represented as a pair of integers: [width, height]. The number of rectangles is between 1 and 10^5, and each width and height is between 1 and 10^5.
Example: rectangles = [[6,12], [3,6], [5,10], [15,30]]
Constraints:
• 1 <= n <= 10^5
• 1 <= width_i, height_i <= 10^5
• rectangles[i].length == 2
Output: Return the total number of pairs of interchangeable rectangles.
Example: 6
Constraints:
Goal: The goal is to calculate the number of interchangeable pairs of rectangles, which can be done by checking for rectangles with the same width-to-height ratio.
Steps:
• 1. Compute the width-to-height ratio for each rectangle.
• 2. Use a hash map to store the frequency of each unique ratio.
• 3. For each unique ratio, calculate the number of interchangeable pairs using the frequency of that ratio.
• 4. Return the total count of pairs.
Goal: The input list contains between 1 and 10^5 rectangles. Each rectangle has a width and height between 1 and 10^5.
Steps:
• 1 <= n <= 10^5
• 1 <= width_i, height_i <= 10^5
Assumptions:
• The input list contains valid rectangles with width and height values between 1 and 10^5.
• Input: rectangles = [[6,12], [3,6], [5,10], [15,30]]
• Explanation: The width-to-height ratios for these rectangles are 6/12, 3/6, 5/10, and 15/30, which are all the same. Therefore, all 6 pairs of rectangles are interchangeable.
• Input: rectangles = [[6,7], [7,8]]
• Explanation: The width-to-height ratios for these rectangles are different, so there are no interchangeable pairs.
Approach: The solution involves calculating the width-to-height ratio for each rectangle and storing them in a hash map. The total number of interchangeable pairs is computed by considering how many rectangles share the same ratio.
Observations:
• The key observation is that rectangles with the same width-to-height ratio are interchangeable.
• This problem can be solved efficiently by using a hash map to track the frequency of each ratio.
Steps:
• 1. For each rectangle, calculate the width-to-height ratio.
• 2. Use a hash map to count the frequency of each unique ratio.
• 3. For each unique ratio with a count greater than 1, compute the number of interchangeable pairs using the combination formula: count * (count - 1) / 2.
• 4. Sum the results to get the total number of interchangeable pairs.
Empty Inputs:
• If the input has only one rectangle, there are no interchangeable pairs.
Large Inputs:
• The solution should handle up to 10^5 rectangles efficiently.
Special Values:
• Rectangles with the same width and height will have a ratio of 1.
Constraints:
• Ensure that the solution can handle the full range of input sizes and values efficiently.
long long interchangeableRectangles(vector<vector<int>>& rectangles) {
unordered_map<double, int> mp;
long long cnt = 0;
for(auto r: rectangles) {
double x = (double)r[0]/ r[1];
if(mp.find(x) != mp.end()) cnt += mp[x];
mp[x]++;
}
// int cnt = 0;
// for(auto &it: mp)
// {
// cout << it.second << ' ';
// cnt = cnt + it.second * (it.second -1 ) / 2;
// }
return cnt;
}
1 : Function Definition
long long interchangeableRectangles(vector<vector<int>>& rectangles) {
Defines the function `interchangeableRectangles` that takes a vector of rectangles (represented as pairs of integers) and returns the count of interchangeable rectangle pairs.
2 : Variable Initialization
unordered_map<double, int> mp;
Initializes an unordered map `mp` that will store the ratio of the width and height of each rectangle, mapped to the count of how many times that ratio has been encountered.
3 : Variable Initialization
long long cnt = 0;
Initializes the variable `cnt` to store the count of interchangeable rectangle pairs.
4 : Looping Through Rectangles
for(auto r: rectangles) {
Starts a loop to iterate over each rectangle in the `rectangles` vector.
5 : Ratio Calculation
double x = (double)r[0]/ r[1];
Calculates the ratio of the rectangle's width to height and stores it in the variable `x`.
6 : Map Lookup
if(mp.find(x) != mp.end()) cnt += mp[x];
Checks if the ratio `x` already exists in the map `mp`. If it does, the current count of rectangles with the same ratio is added to `cnt`.
7 : Map Update
mp[x]++;
Increments the count for the ratio `x` in the map `mp` to track how many times this ratio has appeared.
8 : Return Statement
return cnt;
Returns the total count of interchangeable rectangle pairs stored in `cnt`.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the number of rectangles. We iterate over the list once to calculate ratios and update the hash map.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) because we store the frequency of each unique ratio in a hash map.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus