Find K-th Smallest Pair Distance

Find K-th Smallest Pair Distance is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the Median and Kth of Two Sorted Arrays subpattern.

Problem statement

Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

Example 1: Input: nums = [1,3,1] k = 1 Output: 0 Explanation: 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.

Note: 2 <= len(nums) <= 10000.

0 <= nums[i] < 1000000.

1 <= k <= len(nums) (len(nums) - 1) / 2.

Topics and companies

Topics: Array, Binary Search, Heap.

Reported in interviews at Google, Amazon.

How to practise Find K-th Smallest Pair Distance on Thita.ai

Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(nlogn + nlogw) time and O(1) space.

Open Find K-th Smallest Pair Distance in the code editor, or read the Find K-th Smallest Pair Distance editorial for a worked solution with its approach and complexity analysis.

Where Find K-th Smallest Pair Distance sits in the DSA pattern sheet

• Binary Search Patterns pattern guide
• Median and Kth of Two Sorted Arrays subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Find K-th Smallest Pair Distance

Other problems that use the same Median and Kth of Two Sorted Arrays and Binary Search Patterns techniques:

• Median of Two Sorted Arrays — Hard, same subpattern
• Binary Search — Easy, same pattern
• Capacity To Ship Packages Within D Days — Medium, same pattern
• Find First and Last Position of Element in Sorted Array — Medium, same pattern
• Find in Mountain Array — Hard, same pattern
• Find K Closest Elements — Medium, same pattern