Kth Smallest Absolute Difference — Problem Statement & Solution Guide
Problem Description
You are given an integer array nums of length n and an integer k. Consider every unordered pair of distinct indices (i, j) with i < j; each pair contributes the absolute difference |nums[i] - nums[j]|. Sort all these differences in non‑decreasing order. Return the k‑th smallest value in this sorted list (1‑based indexing).
Input format:
- The first line contains two space‑separated integers n and k.
- The second line contains n space‑separated integers representing nums.
Output format:
- A single integer, the k‑th smallest absolute difference among all pairs.
The solution must handle up to 10^5 elements efficiently, ideally in O(n log n) time.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Kth Smallest Absolute Difference"
WHY DOES IT MATTER?
The pattern combines binary search on the answer space with a linear two‑pointer count, a classic technique for "k‑th smallest pair" or "k‑th smallest distance" problems. Mastering this pattern lets you solve a whole family of selection‑by‑value problems where enumerating all candidates is prohibitive.
OPTIMIZATION CHALLENGE
The key insight is that the count of pairs ≤ d is a monotonic function of d. This monotonicity enables binary search, turning an O(n²) enumeration into O(n log C) by replacing explicit pair generation with a sliding window that runs in linear time for each probe.
REAL-WORLD CONNECTION
Think of a distributed log‑processing system that needs to find the k‑th smallest latency gap between events. Instead of storing every pairwise latency (which would explode quadratically), you sort timestamps and binary‑search a latency threshold, counting how many gaps fall below it in a single pass—mirroring the algorithmic approach.
During an interview, first sort the array, then write a helper that returns the pair count for a given distance using two pointers. Keep the binary‑search loop tight and avoid overflow by using long integers for the high bound (max‑min). This modular design makes debugging trivial and shows clean engineering discipline.
COMPLEXITY AT A GLANCE
O(n log C) where C = max(nums)‑min(nums)O(1) additional (besides input sorting)Core Theory — Why This Approach?
The Kth Smallest Absolute Difference problem asks for the k‑th element in the sorted multiset of |nums[i]‑nums[j]| over all i<j. A naïve solution enumerates every pair, computes the absolute difference, stores them in a list and sorts – this costs O(n²) time and O(n²) space, which is infeasible for typical constraints (n up to 10⁵). The optimal paradigm leverages two powerful ideas: (1) sorting the original array to expose monotonicity of differences, and (2) applying a binary‑search‑over‑answer technique combined with a linear two‑pointer count. After sorting, for any candidate distance d we can count in O(n) how many pairs have difference ≤ d by sliding a right pointer while maintaining the left pointer, because the sorted order guarantees that increasing the right index never decreases the difference. This count enables a classic “lower‑bound” binary search on the answer space (0 … max(nums)‑min(nums)), yielding O(n log C) time where C is the numeric range, and O(1) extra space. An alternative heap‑based approach builds a min‑heap of the smallest difference for each left index and extracts k times, achieving O((n+k) log n) time and O(n) space, which is also acceptable when k is much smaller than n².
Interview Questions on This Problem
Q1How would you find the k‑th smallest pair distance in an array of up to 10⁵ elements without generating all O(n²) differences?
Sort the array, then binary‑search the answer value d. For each mid, use a two‑pointer scan to count pairs with difference ≤ d in O(n). Adjust the search range based on whether the count is ≥ k. The final low bound is the k‑th smallest distance.
Q2Explain how a min‑heap can be used to generate the k smallest absolute differences and discuss its time‑space trade‑offs compared to the binary‑search method.
After sorting, push into a min‑heap the tuple (nums[i+1]‑nums[i], i, i+1) for every i. Repeatedly pop the smallest tuple, record its distance, and if the right index can be advanced (j+1 < n) push (nums[j+1]‑nums[i], i, j+1). After k pops, the last popped distance is the answer. This runs in O((n+k) log n) time and O(n) space, which is faster when k ≪ n² but uses more memory than the O(1) extra‑space binary search.
Q3Why does the two‑pointer counting technique work only after the array is sorted, and what would break if the array remained unsorted?
Sorting guarantees that for a fixed left pointer i, the differences nums[j]‑nums[i] are non‑decreasing as j moves right, so once a difference exceeds the candidate d we can stop advancing j for that i. Without sorting, differences are unordered, and the sliding window would miss valid pairs, leading to incorrect counts.
Examples
Input
4 3 1 3 4 7
Output
3
Explanation: All unordered pairs and their absolute differences are: (1,3)=2, (1,4)=3, (1,7)=6, (3,4)=1, (3,7)=4, (4,7)=3. Sorting these gives [1,2,3,3,4,6]; the 3rd smallest element is 3.
Input
5 1 -10 -5 0 5 10
Output
5
Explanation: The sorted array is [-10,-5,0,5,10]. The smallest absolute difference occurs between any two consecutive numbers and equals 5. Hence the 1st smallest difference is 5.
Input
6 8 2 9 4 7 12 3
Output
5
Explanation: Sorting the array yields [2,3,4,7,9,12]. The 15 pairwise absolute differences are: 1,2,5,7,10,1,4,6,9,3,5,8,2,5,3. After sorting: [1,1,2,2,3,3,4,5,5,5,5,6,7,8,9,10]. The 8th element in this order is 5.
Constraints
- 1 <= n <= 100000
- 1 <= k <= n * (n - 1) / 2
- -10^9 <= nums[i] <= 10^9
- All input values are integers
Optimal Approach & Strategy
Sort nums, binary‑search the distance d, and for each d count qualifying pairs with a two‑pointer scan in O(n). The overall complexity becomes O(n log C) time and O(1) extra space.
Brute Force Approach
Generate every |nums[i]‑nums[j]|, store them in a list, sort the list, and return the element at index k‑1. This is O(n²) time and space.
Verified Code Solutions
function solution(nums, k) {
nums.sort((a, b) => a - b);
let heap = [];
for (let i = 0; i < nums.length - 1; i++) {
heap.push(nums[i + 1] - nums[i]);
}
heap.sort((a, b) => a - b);
for (let i = 0; i < k - 1; i++) {
heap.shift();
}
return heap[0];
}class Solution {
public:
int solution(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
priority_queue<int> heap;
for (int i = 0; i < nums.size() - 1; i++) {
heap.push(nums[i + 1] - nums[i]);
}
for (int i = 0; i < k - 1; i++) {
heap.pop();
}
return heap.top();
}
};class Solution {
public int solution(int[] nums, int k) {
Arrays.sort(nums);
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int i = 0; i < nums.length - 1; i++) {
heap.add(nums[i + 1] - nums[i]);
}
for (int i = 0; i < k - 1; i++) {
heap.poll();
}
return heap.poll();
}
}def solution(nums, k):
nums.sort()
heap = []
for i in range(len(nums) - 1):
heap.append(nums[i + 1] - nums[i])
heap.sort()
for i in range(k - 1):
heap.pop(0)
return heap[0]function solution(nums, k) {
nums.sort((a, b) => a - b);
let heap = [];
for (let i = 0; i < nums.length - 1; i++) {
heap.push(nums[i + 1] - nums[i]);
}
heap.sort((a, b) => a - b);
for (let i = 0; i < k - 1; i++) {
heap.shift();
}
return heap[0];
}Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.