Ninja‌ ‌and‌ ‌K-th‌ ‌smallest‌ ‌Pair‌ ‌Distance

Moderate
0/80
Average time to solve is 45m
profile
Contributed by
2 upvotes
Asked in company
Apple

Problem statement

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
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
2 1
1 2
4 4
1 2 3 4
Sample Output 1:
1
2
Explanation of sample input 1:
In the first test case, all possible pairs distances are:
Index 0 and 1 i.e abs(‘NUMS’[0] - ‘NUMS’[1]) = 1.
Hence the 1’st smallest distance is 1. 

In the first test case, 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 0 and 3 i.e abs(‘NUMS’[0] - ‘NUMS’[3]) = 3
Index 1 and 2 i.e abs(‘NUMS’[1] - ‘NUMS’[2]) = 1
Index 1 and 3 i.e abs(‘NUMS’[1] - ‘NUMS’[3]) = 2
Index 3 and 4 i.e abs(‘NUMS’[3] - ‘NUMS’[4]) = 1

So all possible distances in increasing order are 1 1 1 2 2 3.
Hence the 4’th smallest distance is 2.
Sample Input 2:
2
5 3
1 1 2 2 3
4 2
3 2 100 8
Sample Output 2:
1
5
Explanation for sample input 2:
In the first test case, all possible distances in increasing order are 0 0 1 1 1 1 1 1  2 2
Hence the 3’th smallest distance is 1. 

In the second test case, all possible distances in increasing order are 1 5 6 92 97 98
Hence the 2’th smallest distance is 5.
Hint

Can you think of storing all the possible pair distances?

Approaches (2)
Brute Force

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:

 

  1. Declare a list/array ‘allPairDist’ in which we store all the possible pair distances of ‘NUMS’.
  2. 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’.
  3. Sort ‘allPairDist’.
  4. Finally, return the value present at ‘K’ - 1 index of this ‘allPairDist’.
Time Complexity

O((N ^ 2) * log(N)), where ‘N’ is the size of ‘NUMS’.

 

Since we are finding all possible pair distances using a nested loop in O(N^2) time and then using a sort function that takes O((N^2)*log(N^2)) time. Hence, the overall time complexity is O((N^2)*log(N)).

Space Complexity

O(N ^ 2), where ‘N’ is the size of ‘NUMS’.

 

Because we are storing all possible pair distances of ‘NUMS’ in ‘allPairDist’. Hence the space complexity is O(N ^ 2).

Code Solution
(100% EXP penalty)
Ninja‌ ‌and‌ ‌K-th‌ ‌smallest‌ ‌Pair‌ ‌Distance
Full screen
Console