How to Solve Find K-th Smallest Pair Distance

The fastest way to solve Find K-th Smallest Pair Distance is to sort the array, binary search the distance value, and for each guess count how many pairs have distance less than or equal to that guess. The key insight is that the answer is not a pair index after sorting pairs explicitly; it is a distance value inside a bounded numeric range. A sliding left pointer lets each count check run in linear time after sorting.

Problem Statement

You are given an integer array nums and an integer k. For every pair of indices i and j with i < j, define the pair distance as the absolute difference between nums[i] and nums[j]. Your task is to return the k-th smallest distance among all possible pairs, so the answer depends on the ordering of distances, not on the ordering of the original elements.

A brute force approach would generate all pair distances, sort them, and pick the k-th one, but that breaks down because there are O(n^2) pairs. In this problem, the important structure is that pair distances fall inside a numeric range from 0 to max(nums) - min(nums), which makes it possible to search the answer space directly. For example, with nums = [1,3,1] and k = 1, the pair distances are 2, 0, and 2, so the smallest distance is 0.

Examples

Example 1

Input: nums = [1,3,1], k = 1

Output: 0

Here are all the pairs: (1,3) -> 2 (1,1) -> 0 (3,1) -> 2 Then the 1st smallest distance pair is (1,1), and its distance is 0.

Example 2

Input: nums = [1,1,1], k = 2

Output: 0

Example details omitted.

Example 3

Input: nums = [1,6,1], k = 3

Output: 5

Example details omitted.

Constraints

• n == nums.length
• 2 <= n <= 104
• 0 <= nums[i] <= 106
• 1 <= k <= n * (n - 1) / 2

Solution Approach

Sort to make distance checks monotonic

Start by sorting nums. Once nums is sorted, increasing the right index only increases or preserves differences, which creates the monotonic condition needed for binary search on the answer. This step also turns the counting subproblem into a sliding-window scan instead of repeated absolute difference checks against unsorted values.

Binary search the distance, not the pair

Search between low = 0 and high = nums[n - 1] - nums[0]. For a guessed distance mid, ask a problem-specific question: how many index pairs have distance less than or equal to mid? If that count is at least k, then mid is large enough to cover the k-th smallest distance, so move left. Otherwise, move right. This works because the count of pairs with distance less than or equal to X never decreases as X grows.

Count pairs with a two-pointer window

Use two pointers on the sorted array to count pairs whose distance is at most mid. For each right index, advance left while nums[right] - nums[left] > mid. Then every index from left through right - 1 forms a valid pair with right, so add right - left to the count. A common failure mode here is resetting left for each right, which destroys the linear pass and misses the sorted-window advantage that makes this problem efficient.

Complexity Analysis

Sorting costs O(n log n). Each binary search step performs one linear two-pointer count, and the search range spans distance values from 0 to M where M = max(nums) - min(nums), so the full runtime is O(n log n + n log M). The counting pass uses O(1) extra working space beyond the sort, so space is typically O(1) auxiliary, or O(log n) if you include sort stack usage depending on language implementation.

What Interviewers Usually Probe

• They hint to binary search the answer space instead of enumerating all pair distances.
• They ask how to count pairs with distance <= X efficiently after sorting.
• They push back on O(n^2) generation, which usually means the two-pointer counting check is the missing piece.

Common Pitfalls or Variants

Common pitfalls

• Binary searching pair positions instead of binary searching the distance value itself.
• Using a nested scan for each mid, which turns the counting check back into O(n^2).
• Moving the left pointer incorrectly and undercounting or overcounting pairs when nums[right] - nums[left] exceeds mid.

Follow-up variants

• Return the k-th largest pair distance, which flips how you reason about the count threshold.
• Count pairs with distance strictly less than X instead of less than or equal to X, which changes the boundary condition.
• Solve the same answer-space search when the array contains many duplicates, where zero-distance pairs dominate early ranks.

How GhostInterview Helps

• Shows why the searchable space is the distance range, not the list of explicit pairs.
• Walks through the <= mid counting logic on sorted nums so the two-pointer invariant stays clear.
• Flags off-by-one binary search updates that commonly break Find K-th Smallest Pair Distance.

Topic Pages

• Array
• Two Pointers
• Binary Search
• Sorting

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main pattern in Find K-th Smallest Pair Distance?

The core pattern is binary search over the valid answer space. Instead of building all pair distances, you sort nums and test whether a candidate distance can cover at least k pairs.

Why does sorting help in this problem?

Sorting makes pair differences monotonic as the right pointer moves. That lets you count how many pairs have distance less than or equal to a guessed value in one linear scan.

How do you count pairs with distance <= X efficiently?

Use two pointers on the sorted array. For each right index, move left forward until nums[right] - nums[left] <= X, then add right - left valid pairs ending at right.

Why is brute force too slow for LeetCode 719?

There are O(n^2) pairs, so explicitly generating and sorting all distances becomes too expensive as n grows. The binary-search-plus-counting method avoids materializing that full distance list.

What usually goes wrong when implementing this solution?

Most bugs come from off-by-one updates in the binary search or from mismanaging the left pointer during counting. If the count function is not monotonic or linear, the whole approach breaks for this problem.