Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
There are O(n²) pair distances and we want the k-th smallest WITHOUT materialising them. Sort the array, then binary search on the *distance value* d in [0, max − min]: for each candidate d, count how many pairs have distance ≤ d using a two-pointer sweep in O(n). Because that count is monotonic in d, the smallest d whose count is ≥ k is exactly the k-th smallest distance. Total O(n log n + n log W) where W is the value range.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise that 'k-th smallest pair distance' is a binary-search-on-the-answer problem rather than a sort-everything problem, and whether you can build the O(n) monotone counting function with two pointers and prove it's amortised linear.
Where candidates slip
Generating all O(n²) distances (TLE / MLE at n = 10⁴), or writing the pair counter with a nested loop (O(n²) per binary-search step), or forgetting to sort before counting.
How to stand out
Name the technique ('binary search on the answer'), justify monotonicity of `countPairs`, and explain why the two-pointer counter is O(n) because `left` never resets. Then connect it to Kth Smallest in a Sorted Matrix and Split Array Largest Sum.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewk-th smallest pair distancen small enough to list all O(n^2) pairs?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Enumerate and Sort All Distances
1Hint 1Explore hintHide hint
The most literal reading: every pair has a distance. How many pairs are there, and what would you do with all their distances?
2Hint 2Explore hintHide hint
Compute the absolute difference for every pair (i, j) with i < j and collect them into a list.
3Hint 3Explore hintHide hint
Sort the list and return the element at index k − 1 (k is 1-indexed).
A · Core idea
Enumerate all n(n−1)/2 pairs with two nested loops, push each absolute difference into a list, sort the list, and return the (k−1)-th entry.
Why it's obviously correct. It materialises the exact multiset the problem talks about — every pairwise distance — and then 'k-th smallest' is just an array index after sorting. There's no cleverness to get wrong; it's the definition turned into code, which makes it the perfect baseline to state before optimising.
Why it doesn't scale. With n = 10⁴, the pair count is about 5 × 10⁷. Generating them is ~50 million operations (tolerable), but storing 50 million integers is ~200 MB and sorting them is O(n² log n) ≈ 5 × 10⁷ × 26 ≈ 1.3 × 10⁹ comparisons — both blow the typical time and memory limits. The bottleneck is that we pay to produce every distance even though we only want one of them.
The key realisation that leads to the better solution. We don't need the sorted list — we only need to know which value sits at rank k. If, for any candidate distance d, we could quickly answer 'how many pairs have distance ≤ d?', we could binary search for the smallest d whose count reaches k. That count turns out to be computable in O(n) after sorting, which is what the optimal approach exploits.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [1, 3, 1], k = 1(i=0, j=1)
|1 − 3| = 2
dists = [2]0C · Code with teaching comments
Reference implementation previewpublic int smallestDistancePair(int[] nums, int k) { int n = nums.length; int[] dists = new int[n * (n - 1) / 2]; int idx = 0; for (int i = 0; i < n; i++) {Explore the full codeHide the full code
D · Why it works and complexityO(n² log n) timeO(n²) spaceOpen the invariant and proofExplore the proofHide the proof
Sorting all distances answers far more than the question asks — it ranks every pair when we only want rank k. Whenever you catch yourself fully sorting an implicit set to grab one element, ask whether you can instead count items ≤ X and binary search X. Counting is almost always cheaper than ranking everything.
ComplexityO(n² log n) time, O(n²) space — There are n(n−1)/2 ≈ n²/2 pairs to generate, and sorting that many distances costs O(n² log n). The list itself holds O(n²) integers.
E · Edge cases and pitfalls3Allocating ~n²/2 integers — out of memory for n near 10⁴.Explore edge casesHide edge cases
Pitfalls
- Allocating ~n²/2 integers — out of memory for n near 10⁴.
- Indexing with `dists[k]` instead of `dists[k - 1]` — off by one because k is 1-indexed.
- Submitting this as the final answer on the hard variant — it TLEs/MLEs at the upper constraints.
Approach 2 of 2 · Optimal
Binary Search on the Answer + Two-Pointer Count (Optimal)
1Hint 1Explore hintHide hint
You don't need every distance — only the value at rank k. Suppose you could ask 'how many pairs have distance ≤ d?' cheaply. How would that pin down the answer?
2Hint 2Explore hintHide hint
Sort the array. Then `countPairs(d)` is monotonic: bigger d never decreases the count. Binary search the smallest d with `countPairs(d) >= k`.
3Hint 3Explore hintHide hint
Compute `countPairs(d)` with two pointers on the sorted array: for each `right`, advance `left` while `nums[right] − nums[left] > d`; then every index in `[left, right)` pairs with `right`, so add `right − left`. The `left` pointer never moves backward → O(n).
A · Core idea
Sort nums. The smallest possible distance is 0 and the largest is nums[n-1] − nums[0], so the answer lives in [0, nums[n-1] − nums[0]]. Binary search that value range for the smallest distance d such that at least k pairs have distance ≤ d.
Why binary search on the value works — monotonicity. Define countPairs(d) = number of pairs with distance ≤ d. As d grows, no pair ever leaves the 'within distance' set and some may join, so countPairs is non-decreasing in d. That makes the predicate countPairs(d) >= k a monotone step function: false for small d, then true forever after some threshold. Binary search locates that threshold — and the threshold value is precisely the k-th smallest distance, because just below it fewer than k pairs qualify and exactly at it the count first reaches k.
Why the count uses two pointers and is O(n). On the sorted array, for a fixed right endpoint right, the pairs ending at right with distance ≤ d are exactly those whose left value is ≥ nums[right] − d. Because the array is sorted, those left endpoints form a contiguous block [left, right). We maintain left as the smallest index with nums[right] − nums[left] <= d. As right advances, the required left can only move forward (a larger nums[right] needs an equal-or-larger lower bound), so across the entire scan left travels at most n steps total. Each right contributes right − left pairs. One forward sweep of two pointers — O(n), not O(n²).
Why the lower-bound template (`hi = mid`, return `lo`). We want the smallest d satisfying the predicate, so this is a left-boundary search. When countPairs(mid) >= k, mid is a feasible distance but maybe not the smallest, so keep it: hi = mid. When countPairs(mid) < k, mid is too small, so lo = mid + 1. With while (lo < hi) the window converges to the threshold and we return lo. Note we binary search on a value, so there's no array index to read at mid — mid is itself a candidate distance.
Why sorting is mandatory. Two facts depend on it: (1) the max distance is last − first, giving tight search bounds; (2) the two-pointer count relies on left endpoints forming a contiguous sorted block. Without sorting, counting pairs ≤ d would itself be O(n²) and the whole speed-up evaporates. Sorting costs O(n log n) once, dwarfed by neither term.
Putting the complexity together. Sort O(n log n); then O(log W) binary-search steps (W ≤ 10⁶, so ~20 steps) each doing an O(n) count → O(n log W). No O(n²) list, O(1) auxiliary space. This comfortably handles n = 10⁴.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [1, 3, 1], k = 1 (sorted → [1, 1, 3])Interactive diagram
How countPairs(d) sweeps with two pointers
lo=0, hi=2For each right endpoint, left advances until the pair fits within d; right − left pairs are added. left never resets.
0C · Code with teaching comments
D · Why it works and complexityO(n log n + n log W) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The pivot from O(n²) to near-linear is the realisation that counting how many candidates are ≤ X is exponentially cheaper than sorting all candidates. Binary search on the answer turns 'find the k-th value' into 'find the threshold where the count crosses k'. The two-pointer counter is the workhorse that makes each threshold test O(n). This count-then-binary-search shape recurs in Kth Smallest in a Sorted Matrix, Split Array Largest Sum, and Koko Eating Bananas.
ComplexityO(n log n + n log W) time, O(1) space — Sorting is O(n log n). The binary search runs O(log W) iterations where W = max − min ≤ 10⁶, and each iteration does an O(n) two-pointer count → O(n log W). Only a handful of scalars are used → O(1) extra space.
E · Edge cases and pitfalls9nums = [1, 1, 1], k = 2 — max distance is 0 → lo = hi = 0 from the start, loop body never runs, return 0.Explore edge casesHide edge cases
Edge cases handled
nums = [1, 1, 1], k = 2max distance is 0 → lo = hi = 0 from the start, loop body never runs, return 0.nums = [1, 6, 1], k = 3Sorted [1, 1, 6]; binary searches [0, 5]. countPairs reaches 3 only at d = 5 → returns 5.k = n·(n−1)/2 (the largest)Asks for the maximum distance; the predicate is only satisfied at d = last − first, so lo converges to hi.All elements distinct and far apartcountPairs(0) = 0 forces lo upward; the search still terminates in O(log W) steps.
Pitfalls
- Binary searching over array indices instead of the distance value range.
- Forgetting to sort — the two-pointer count becomes wrong and O(n²).
- Writing countPairs with a nested loop (resetting left each right) — that's O(n²) per step, killing the speed-up.
- Using `hi = mid - 1` for this lower-bound search — can skip the exact threshold distance.
- Counting ordered pairs (doubling) — use `right − left`, which counts each unordered pair once.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int smallestDistancePair(int[] nums, int k) { Arrays.sort(nums); int n = nums.length; int lo = 0, hi = nums[n - 1] - nums[0]; while (lo < hi) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Resetting the left pointer each iteration (nested O(n²) count)
If `left` restarts at 0 for every `right`, the counter is O(n²) per binary-search step → O(n² log W) overall, no better than brute force. The whole point is that `left` only moves forward across the entire sweep.
Explore the code comparisonHide the code comparison
Resetting the left pointer each iteration (nested O(n²) count)
If `left` restarts at 0 for every `right`, the counter is O(n²) per binary-search step → O(n² log W) overall, no better than brute force. The whole point is that `left` only moves forward across the entire sweep.
Don't write this
def count_pairs(dist):
count = 0
for right in range(n):
left = 0 # resets every time → O(n^2)
while nums[right] - nums[left] > dist:
left += 1
count += right - left
return countWrite this instead
def count_pairs(dist):
count = left = 0 # left persists across all right → O(n)
for right in range(n):
while nums[right] - nums[left] > dist:
left += 1
count += right - left
return count2Binary searching indices instead of the distance value
The k-th smallest distance is a *value* in [0, max − min], not an index into the array. Searching index bounds is a category error — there's no sorted-by-distance array to index into.
Explore the code comparisonHide the code comparison
Binary searching indices instead of the distance value
The k-th smallest distance is a *value* in [0, max − min], not an index into the array. Searching index bounds is a category error — there's no sorted-by-distance array to index into.
Don't write this
int lo = 0, hi = nums.length - 1; // WRONG: indices
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
// ... comparing nums[mid] ...
}Write this instead
int lo = 0, hi = nums[nums.length - 1] - nums[0]; // distance values
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (countPairs(nums, mid) >= k) hi = mid;
else lo = mid + 1;
}3Forgetting to sort before counting
The two-pointer count assumes that left endpoints within distance d form a contiguous block, which only holds on sorted data. Skipping the sort makes the count silently wrong.
Explore the code comparisonHide the code comparison
Forgetting to sort before counting
The two-pointer count assumes that left endpoints within distance d form a contiguous block, which only holds on sorted data. Skipping the sort makes the count silently wrong.
Don't write this
public int smallestDistancePair(int[] nums, int k) {
int lo = 0, hi = 1000000; // never sorted
// ... countPairs assumes sorted but nums isn't ...
}Write this instead
public int smallestDistancePair(int[] nums, int k) {
Arrays.sort(nums);
int lo = 0, hi = nums[nums.length - 1] - nums[0];
// ... now countPairs is valid ...
}Revise
Carry the pattern into the interview
Pattern to remember
Binary search on the answer + two-pointer feasibility count
Code pattern to memorize
sort(nums)
lo, hi = 0, nums[-1] - nums[0]
while lo < hi:
mid = lo + (hi - lo) // 2
if countPairs(mid) >= k: # enough pairs within distance mid
hi = mid
else:
lo = mid + 1
return lo
countPairs(d): left = 0; for right: while nums[right]-nums[left] > d: left++; cnt += right-leftRules to remember
- 1Binary search on the value, not the index. The search space is the distance range
[0, max − min], not array positions. - 2Sort first — the two-pointer count and the 'distance = nums[right] − nums[left]' shortcut both require sorted order.
- 3
countPairs(d)is monotonic non-decreasing ind; that monotonicity is the whole reason binary search applies. - 4Find the smallest
dwithcountPairs(d) >= k→ use thehi = mid/lo = mid + 1lower-bound template and returnlo. - 5The two-pointer counter is O(n):
leftonly ever moves forward across the whole scan, so it's amortised linear, not nested.
Use this pattern when
- 'k-th smallest/largest value' over an implicit set too big to enumerate (pairs, sums, products)
- You can cheaply *count how many candidates are ≤ X* for any X (a monotone feasibility test)
- The answer is a number in a known range, and counting is faster than sorting all candidates
- 'Minimize the maximum' / 'maximize the minimum' / 'k-th by value' phrasings
Choose another pattern when
- k is tiny and n is small → just generate and sort all O(n²) distances, far simpler
- You need the actual pair, not the distance value → binary-search-on-answer only gives the value
- No monotone counting function exists → binary search on the answer doesn't apply
Interview takeaway
This is the flagship 'binary search on the answer' problem: when you can't afford to list all candidates but you *can* count how many are ≤ X, binary search the value. Pair it with a two-pointer count and an O(n²) problem collapses to O(n log n + n log W). The same recipe solves Kth Smallest in a Sorted Matrix, Split Array Largest Sum, and Koko Eating Bananas.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternThe canonical 'binary search on the answer' with a monotone counting predicate. Recognise it whenever you need the k-th value of an implicit set too large to enumerate but where 'how many are ≤ X' is cheap to compute. Pairing it with a two-pointer count gives the linear feasibility test; the same recipe powers Kth Smallest in a Sorted Matrix, Split Array Largest Sum, and Koko Eating Bananas.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Kth Smallest Element in a Sorted MatrixComing soonBinary search the value; count entries ≤ mid by walking the matrix in O(n) instead of pairs.
- Split Array Largest SumComing soonBinary search the largest-sum answer; greedily count the splits needed for a candidate cap.
- Koko Eating BananasBinary search the eating speed; count hours needed as the monotone feasibility test.
- Kth Smallest Number in Multiplication TableComing soonBinary search the value; count table entries ≤ mid row by row in O(rows).