Last Updated: 8 Apr, 2021
Ninja and K-th smallest Pair Distance
Moderate
Asked in company
Ninja has been given a ‘NUMS’ array/list of size ‘N’. ‘NUMS’ array/list contains ‘N’ positive integers. Ninja has to find the ‘K-th’ smallest distance among all pairs of the ‘NUMS’.
Note: The distance between any two numbers of ‘NUMS’ is abs(‘NUMS[i]’ - ‘NUMS[j]’).
For example:
If ‘NUMS’ = [1, 2, 3] then all possible pairs distances are:
Index 0 and 1 i.e abs(‘NUMS[0]’ - ‘NUMS[1]’) = 1
Index 0 and 2 i.e abs(‘NUMS[0]’ - ‘NUMS[2]’) = 2
Index 1 and 2 i.e abs(‘NUMS[1]’ - ‘NUMS[2]’) = 1
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain two single space-separated integers ‘N’ and ‘K’ which represent the size of ‘NUMS’ and the ‘K-th’ smallest distance that “Ninja” has to find.
The next line contains ‘N’ space-separated integers representing the values of the given array/list ‘NUMS’.
Output Format:
For each test case, print a single line containing a single integer denoting the ‘K-th’ smallest distance among all pairs of the ‘NUMS’.
The output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints:
1 <= ‘T’ <= 50
2 <= ‘N’ <= 10000
1 <= ‘K’ <= (N *(N - 1)) / 2
0 <= ‘NUMS[i]’ <= 100000
Where ‘T’ is the number of test cases, 'N' is the size of ‘NUMS’, ‘K’ represents the ‘K-th’ smallest distance among all pairs of the ‘NUMS’ and ‘NUMS[i]’ represents the ‘i-th’ value of ‘NUMS’.
Time limit: 1 sec.
Approaches
The basic idea is to run two loops and find all possible pair distances and store them in a list/array ‘allPairDist’. Then sort this ‘allPairDist’ and return the value present at ‘K’ - 1 index.
The steps are as follows:
- Declare a list/array ‘allPairDist’ in which we store all the possible pair distances of ‘NUMS’.
- Run a loop from ‘i’ = 0 till ‘i’ is less than ‘N’:
- Run a loop from ‘j’ = ‘i’ + 1 till ‘j’ is less than ‘N’:
- Add abs(‘NUMS[i]’ - ‘NUMS[j]’) into ‘allPairDist’.
- Run a loop from ‘j’ = ‘i’ + 1 till ‘j’ is less than ‘N’:
- Sort ‘allPairDist’.
- Finally, return the value present at ‘K’ - 1 index of this ‘allPairDist’.
First, we sort the array/list ‘NUMS’. Then we are applying binary search and inside this binary search, we are checking how many pairs with distance less than equal to mid.
The steps are as follows:
- Sort the ‘NUMS’ array/list.
- Declare two variables ‘low’ and ‘high’ as discussed above.
- While ‘low’ less than ‘high’:
- ‘mid’ = (‘low’ + ‘high’) / 2.
- Declare a variable ‘count’ in which we store the number of pairs with distance less than ‘mid’.
- Declare a variable ‘left’ represents the largest index of ‘NUMS’ which is less than equal to the current index.
- Run a loop for ‘i’ = 0 to ‘N’:
- while ‘NUMS[i] - ‘NUMS[‘left’] greater than ‘mid’:
- ‘left’ = ‘left’ + 1.
- ‘count’ = ‘count’ + ‘i’ - ‘left’.
- If ‘count’ greater than and equal to ‘K’:
- ‘high’ = ‘mid’.
- while ‘NUMS[i] - ‘NUMS[‘left’] greater than ‘mid’:
- Else:
- ‘low’ = ‘mid’ - 1.
- Finally, return ‘low’.
Similar problems