K-th smallest absolute difference of two elements in an array

Software Development
1

Hello Everyone,

We are given an array of size n containing positive integers. The absolute difference between values at indices i and j is |a[i] – a[j]|. There are n*(n-1)/2 such pairs and we are asked to print the kth (1 <= k <= n*(n-1)/2) the smallest absolute difference among all these pairs.
Examples:

Input : a[] = {1, 2, 3, 4}
k = 3
Output : 1
The possible absolute differences are :
{1, 2, 3, 1, 2, 1}.
The 3rd smallest value among these is 1.

Input : n = 2
a[] = {10, 10}
k = 1
Output : 0

Naive Method is to find all the n*(n-1)/2 possible absolute differences in O(n^2) and store them in an array. Then sort this array and print the k-th minimum value from this array. This will take time O(n^2 + n^2 * log(n^2)) = O(n^2 + 2n^2log(n)).
The naive method won’t be efficient for large values of n, say n = 10^5.
An Efficient Solution is based on Binary Search.

  1. Sort the given array a[].
  2. We can easily find the least possible absolute difference in O(n) after sorting. The largest possible difference will be a[n-1] - a[0] after sorting the array. Let low = minimum_difference and high = maximum_difference.
  3. while low < high:
  4. mid = (low + high)/2
  5. if ((number of pairs with absolute difference <= mid) < k):
  6. low = mid + 1
  7. else:
  8. high = mid
  9. return low

We need a function that will tell us the number of pairs with a difference <= mid efficiently.
Since our array is sorted, this part can be done like this:

  1. result = 0
  2. for i = 0 to n-1:
  3. result = result + (upper_bound(a+i, a+n, a[i] + mid) - (a+i+1))
  4. return result

Here upper_bound is a variant of binary search which returns a pointer to the first element from a[i] to a[n-1] which is greater than a[i] + mid. Let the pointer returned be j. Then a[i] + mid < a[j]. Thus, subtracting (a+i+1) from this will give us the number of values whose difference with a[i] is <= mid. We sum this up for all indices from 0 to n-1 and get the answer for the current mid.

// C++ program to find k-th absolute difference

// between two elements

#include<bits/stdc++.h>

using namespace std;

// returns number of pairs with absolute difference

// less than or equal to mid.

int countPairs( int *a, int n, int mid)

{

int res = 0;

for ( int i = 0; i < n; ++i)

// Upper bound returns pointer to position

// of next higher number than a[i]+mid in

// a[i..n-1]. We subtract (a + i + 1) from

// this position to count

res += upper_bound(a+i, a+n, a[i] + mid) -

(a + i + 1);

return res;

}

// Returns k-th absolute difference

int kthDiff( int a[], int n, int k)

{

// Sort array

sort(a, a+n);

// Minimum absolute difference

int low = a[1] - a[0];

for ( int i = 1; i <= n-2; ++i)

low = min(low, a[i+1] - a[i]);

// Maximum absolute difference

int high = a[n-1] - a[0];

// Do binary search for k-th absolute difference

while (low < high)

{

int mid = (low+high)>>1;

if (countPairs(a, n, mid) < k)

low = mid + 1;

else

high = mid;

}

return low;

}

// Driver code

int main()

{

int k = 3;

int a[] = {1, 2, 3, 4};

int n = sizeof (a)/ sizeof (a[0]);

cout << kthDiff(a, n, k);

return 0;

}

Output:

1

The time complexity of the algorithm is O( nlogn + nlognlogn). Sorting takes O(nlogn). After that the main binary search over low and high takes O(nlognlogn) time because each call to the function int f(int c, int n, int* a) takes time O(n*logn).