Problem

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 ($\frac{n(n-1)}{2}$ ) such pairs and we are asked to find and print the k-th smallest absolute difference among all these pairs, given ( $1 \leq k \leq \frac{n(n-1)}{2}$ ).

Examples

Example 1:

1
2
3
4
5
6

Input: arr = [1, 3, 6], k = 2
Output: 2
Explanation:
1. The absolute differences are: |1-3|=2, |1-6|=5, |3-6|=3
2. The sorted differences are: [2, 3, 5]
3. The 2nd smallest difference is 2.

Solution

Method 1 - Sorting

Here is the approach:

  1. Sorting: We start by sorting the array.
  2. Binary Search: We perform a binary search on the possible values of absolute differences.
  3. Counting Pairs: For each midpoint during the binary search, count the pairs with a difference less than or equal to the midpoint.
  4. Adjustment: Based on the count, adjust the low and high bounds of the binary search until we find the ( k )th smallest absolute difference.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public class KthSmallestDifference {
    public static int countPairsWithDistanceLessThanOrEqual(
        int mid, int[] arr, int n) {
        int count = 0;
        int j = 1;
        for (int i = 0; i < n; i++) {
            while (j < n && arr[j] - arr[i] <= mid) {
                j++;
            }
            count += j - i - 1;
        }
        return count;
    }

    public static int kthSmallestAbsoluteDifference(int[] arr, int k) {
        Arrays.sort(arr); // Sort the array first
        int n = arr.length;
        int low = 0, high = arr[n - 1] - arr[0];

        while (low < high) {
            int mid = (low + high) / 2;
            if (countPairsWithDistanceLessThanOrEqual(mid, arr, n) < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        return low;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 6};
        int k = 2;
        System.out.println(kthSmallestAbsoluteDifference(arr, k)); // Output: 2
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


def kth_smallest_absolute_difference(arr, k):
    arr.sort()  # Sort the array first
    n = len(arr)
    low, high = 0, arr[n - 1] - arr[0]

    while low < high:
        mid = (low + high) // 2
        if countPairsWithDistanceLessThanOrEqual(mid, arr, n) < k:
            low = mid + 1
        else:
            high = mid

    return low

def countPairsWithDistanceLessThanOrEqual(mid, arr, n):
    count = 0
    j = 1
    for i in range(n):
        while j < n and arr[j] - arr[i] <= mid:
            j += 1
        count += j - i - 1
    return count


# Example usage
arr = [1, 3, 6]
k = 2
print(kth_smallest_absolute_difference(arr, k))  # Output: 2

Complexity

  • ⏰ Time complexity: O(n log n + n^2 log n), where n is number of elements in array. Sorting takes O(n \log n). Counting pairs inside the binary search takes O(n^2). Thus, the overall time complexity is O(n \log n + n^2 \log n).
  • 🧺 Space complexity: O(1)