In this post, we will discuss one of the most frequently asked interview coding questions in Python.
The problem statement has been defined below:
How to find the count of m unique and different pairs from a list, given a list of integers? A pair here can be considered as an integer ordered pair (x,y) which is present in the list, and m represents the absolute difference between the numbers x and y.
Note: The ordered pair (x,y) and (y,x) are considered as the same pair.
Sample Input:
[2,3,7,9,0], m = 2
Sample Output:
2
Explanation:
The given list is [2,3,7,9,0] and the difference which needs to be identified from the list is 2. The numbers 2 and 0 give the absolute difference as 2, and the numbers 9 and 7 also result in the absolute difference of 2. Hence the number of unique pairs whose absolute difference is 2, is 2.
Corner case:
-
What if there are no 2 values whose difference is m? In that case, we will return 0.
-
What if the absolute difference m to be found is a value less than 0? Even then return 0.
Note: Don't forget to figure out other corner cases (if any) and provide proper solutions to such cases, since they are very important because this gives the interviewer an insight into the interviewee's thinking ability, logical ability, and problem analysis ability.
Basic Approach to solve this Problem
A naive approach is to look at each and every element and see if every other element and the current element's absolute difference would be m or not. We would have to use 2 for loops wherein the outer loop would take the first element and the inner loop would look for every element and take its difference with the outer loop picked value. Since there are 2 for loops involved, the time complexity would be 0(size of the list*size of the list) = 0(n**2).
def findPairs(lst, n, m):
count = 0
for i in range(0, n):
for j in range(i+1, n):
if lst[i] - lst[j] == m or lst[j] - lst[i] == m:
count += 1
return count
nums = [2,3,7,9,0]
n = len(nums)
m = 2
findPairs(nums, n, m)
Output:
2
Optimized Approach to solve the Problem
The counter method from the collections module keeps track of the count of every element present in the list.
def findPairs(nums, m):
result = 0
if m < 0:
return 0
elif m == 0:
dic = Counter(nums)
for i in dic.values():
if i != 1:
result += 1
else:
num = set(nums)
for i in num:
if i+m in num:
result += 1
return result
nums = [2,3,7,9,0]
m = 2
findPairs(nums, m)
Output:
2
When the absolute difference is found to be greater than 0, the elements are first sorted. Then a for loop is iterated over every element of the list and it is added to m (absolute difference). This number is searched for in the list. If it is found, then the count is incremented by 1. Consider the below example:
Our list is [2, 3,7,9,0] and m is 2. Iterating from the first element in the list, if 2+2 (4) is found in the list, the result is incremented. It is done for all the elements. Below is a trace:
2+2 = 4, 4 in list? No. Result = 0
3+2 = 5, 5 in list? No. Result = 0
7+2 = 9, 9 in list? Yes. Result = 1
9+2=11, 11 in list? No. Result = 1
0+2=2, 2 in list? Yes. Result = 2
Result = 2 is returned
Conclusion:
In this post, we understood how to solve the count of m unique pair in a list problem statement. Don't forget to post in your comments about different approaches to the same problem.
You may also like:
