Find K-th Smallest Pair Distance

📋

Find K-th Smallest Pair Distance

Edge cases:

</>

IDE

def smallestDistancePair(nums: list[int], k: int) -> int:public int smallestDistancePair(int[] nums, int k)int smallestDistancePair(vector<int>& nums, int k)function smallestDistancePair(nums, k)

def smallestDistancePair(nums, k):
    # Write your solution here
    pass

class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int smallestDistancePair(vector<int>& nums, int k) {
    // Write your solution here
    return 0;
}

function smallestDistancePair(nums, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 2Greedy approach picking next smallest pair distance directly without binary search.✅ Implement binary search on distance with two-pointer counting to find k-th smallest distance.

Wrong: non-zero for identical elementsFailing to detect all elements equal and returning incorrect distance.✅ Check if max(nums) == min(nums) and return 0 immediately.

Wrong: IndexError or crashNot handling empty or single-element arrays properly.✅ Add guard clauses to return 0 if nums length < 2.

Wrong: Wrong k-th smallest due to off-by-one in counting pairsCounting pairs with distance < mid instead of <= mid in binary search.✅ Count pairs with distance <= mid to correctly narrow binary search.

Wrong: TLE on large inputUsing brute force O(n^2) approach for large n.✅ Use binary search on answer with two-pointer counting for O(n log n + n log W).

✓

Test Cases

Try testing your code on empty and minimal inputs to catch base case bugs.

Consider tricky inputs that expose off-by-one or greedy mistakes.

Optimize your solution to handle large inputs efficiently using binary search.

t1_01basic

Input{"nums":[1,1,3],"k":1}

Expected0

⏱ Performance - must finish in 2000ms

All pairs are (1,3) distance 2, (1,1) distance 0, (3,1) distance 2. The 1st smallest distance is 0.

💡 Consider all pairs and their absolute differences.

💡 Sort the array and use binary search on possible distances.

💡 Count pairs with distance <= mid to narrow down the k-th smallest.

Why it failed: Incorrect output means failure to correctly count pairs or binary search boundaries. Fix by ensuring counting pairs with distance <= mid is accurate.

✓ Correctly identifies the smallest pair distance using binary search and counting.

t1_02basic

Input{"nums":[1,1,2,6],"k":3}

Expected1

⏱ Performance - must finish in 2000ms

Pairs distances sorted: 0(1,1),1(1,2),4(6,2),5(6,1),5(6,1), etc. The 3rd smallest distance is 1.

💡 Sort nums to simplify distance calculations.

💡 Use two pointers to count pairs with distance <= mid.

💡 Adjust binary search range based on count compared to k.

Why it failed: Wrong output likely from incorrect pair counting or binary search update. Fix by carefully implementing two-pointer counting within binary search.

✓ Correctly computes the 3rd smallest pair distance using binary search and two pointers.

t2_01edge

Input{"nums":[],"k":1}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no pairs; by definition return 0 as no distances exist.

💡 Check for empty input and handle gracefully.

💡 Return 0 or handle no pairs case explicitly.

💡 Add a guard clause for empty or insufficient elements.

Why it failed: Fails on empty input by not handling zero pairs; fix by returning 0 when nums length < 2.

✓ Handles empty input correctly by returning 0.

t2_02edge

Input{"nums":[5],"k":1}

Expected0

⏱ Performance - must finish in 2000ms

Single element array has no pairs; distance is 0 by definition.

💡 Single element means no pairs exist.

💡 Return 0 when nums length < 2.

💡 Add explicit check for single element input.

Why it failed: Fails single element input by not returning 0; fix by checking length before processing pairs.

✓ Correctly returns 0 for single element input.

t2_03edge

Input{"nums":[2,2,2,2],"k":5}

Expected0

⏱ Performance - must finish in 2000ms

All elements identical; all pair distances are 0 regardless of k.

💡 All identical elements produce zero distances.

💡 Check if max-min distance is zero to shortcut.

💡 Return 0 immediately if all elements equal.

Why it failed: Fails identical elements test by returning non-zero; fix by detecting zero max-min difference and returning 0.

✓ Correctly returns 0 when all elements are identical.

t2_04edge

Input{"nums":[1,1000000],"k":1}

Expected999999

⏱ Performance - must finish in 2000ms

Array with two elements has only one pair; distance is abs(1 - 1000000) = 999999.

💡 With only two elements, only one pair exists.

💡 Return the absolute difference between the two elements.

💡 Check for minimal input size and handle accordingly.

Why it failed: Fails two-element input by incorrect distance calculation; fix by returning abs(nums[0] - nums[1]) when n=2 and k=1.

✓ Correctly handles two-element input returning their absolute difference.

t3_01corner

Input{"nums":[1,3,6,10,15],"k":7}

Expected9

⏱ Performance - must finish in 2000ms

Pairs sorted distances: 2,3,4,5,7,9,9,10,12,14; 7th smallest is 7. Tests off-by-one errors in counting pairs.

💡 Carefully count pairs with distance <= mid in binary search.

💡 Watch for off-by-one errors in two-pointer increments.

💡 Ensure counting includes pairs equal to mid distance.

Why it failed: Fails due to off-by-one in pair counting; fix by including pairs with distance equal to mid in count.

✓ Correctly handles off-by-one in counting pairs.

t3_02corner

Input{"nums":[1,1,1,1,1],"k":10}

Expected0

⏱ Performance - must finish in 2000ms

All pairs have distance 0; tests confusion between 0/1 knapsack style counting and pair counting.

💡 All pairs have zero distance; count pairs correctly.

💡 Avoid treating pairs as unbounded items; count unique pairs only.

💡 Use two pointers to count pairs, not multiply counts.

Why it failed: Fails by overcounting pairs or confusing pair counting with unbounded counting; fix by counting pairs with two pointers correctly.

✓ Correctly counts pairs with zero distance without overcounting.

t3_03corner

Input{"nums":[1,2,3,4,5],"k":4}

Expected1

⏱ Performance - must finish in 2000ms

Tests greedy trap: smallest distances are 1,1,1,2,... The 4th smallest is 2, not 1.

💡 Greedy picking smallest pairs directly fails here.

💡 Use binary search on distance, not greedy selection.

💡 Count pairs with distance <= mid to find correct k-th smallest.

Why it failed: Fails greedy trap by returning 1 instead of 2; fix by using binary search with pair counting instead of greedy selection.

✓ Correctly avoids greedy trap by binary searching distances.

t4_01performance

Input{"nums":[0,10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,470,480,490,500,510,520,530,540,550,560,570,580,590,600,610,620,630,640,650,660,670,680,690,700,710,720,730,740,750,760,770,780,790,800,810,820,830,840,850,860,870,880,890,900,910,920,930,940,950,960,970,980,990],"k":2500}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, testing O(n log n + n log W) binary search approach within 2s time limit.

💡 Brute force O(n^2) is too slow for n=100.

💡 Use binary search on answer with two-pointer counting for O(n log n + n log W).

💡 Pre-sort nums and count pairs efficiently to pass performance.

Why it failed: TLE due to O(n^2) brute force approach; fix by implementing binary search on distance with two-pointer counting.

✓ Efficient binary search approach confirmed to run within time limit.

Practice

1. Given the following Python code implementing the optimal approach for Kth Largest in a Stream, what is the output of the last print statement?

import heapq

class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.heap = nums
        heapq.heapify(self.heap)
        while len(self.heap) > k:
            heapq.heappop(self.heap)

    def add(self, val: int) -> int:
        if len(self.heap) < self.k:
            heapq.heappush(self.heap, val)
        elif val > self.heap[0]:
            heapq.heapreplace(self.heap, val)
        return self.heap[0]

kthLargest = KthLargest(3, [4, 5, 8, 2])
print(kthLargest.add(3))
print(kthLargest.add(5))
print(kthLargest.add(10))
print(kthLargest.add(9))
print(kthLargest.add(4))

easy

A. 8

B. 5

C. 4

D. 9

Solution

1. Step 1: Trace heap initialization

   Initial nums = [4,5,8,2], heapified and trimmed to size k=3: heap becomes [4,5,8] after popping 2.

2. Step 2: Trace add calls and heap updates

   add(3): 3 < 4 (heap[0]), no replace, return 4 add(5): 5 > 4, replace 4 with 5, heap now [5,5,8], return 5 add(10): 10 > 5, replace 5 with 10, heap now [5,10,8], return 5 add(9): 9 > 5, replace 5 with 9, heap now [8,10,9], return 8 add(4): 4 < 8, no replace, return 8

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Last add returns 8 as kth largest element [OK]

Hint: Heap root always holds kth largest element [OK]

Common Mistakes:

• Off-by-one errors in heap size
• Replacing when val <= heap[0]
• Misunderstanding heap root meaning

2. What is the time complexity of the add(val) operation in the optimal min-heap approach for maintaining the kth largest element in a stream, assuming the heap size is k and the stream length is n?

medium

A. O(n ∙ log n) per add call, because the stream grows with n

B. O(1) per add call, as heap root access is constant time

C. O(k) per add call, because we may need to scan the heap to find the position

D. O(log k) per add call, since heap operations depend only on heap size k

Solution

1. Step 1: Identify heap size and operations

   The heap size is fixed at k, independent of stream length n. Each add involves either a push or a replace operation on the heap.

2. Step 2: Analyze complexity of heap operations

   Heap push or replace operations take O(log k) time because the heap has size k. Accessing the root is O(1), but add involves heapify steps.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Heap operations depend on k, not n, so O(log k) per add [OK]

Hint: Heap operations scale with heap size k, not stream length n [OK]

Common Mistakes:

• Confusing n with k in complexity
• Assuming linear scan of heap
• Ignoring heapify cost

3. Suppose the frequency stack must support a new operation popK(k) that removes and returns the top k most frequent elements in order, breaking ties by recency. Which modification to the optimal heap-based approach correctly supports this operation efficiently?

hard

A. Perform k consecutive pop() calls on the heap, updating frequencies after each pop.

B. Use a separate max-heap for each frequency level and merge results on popK(k).

C. Modify the heap to store lists of elements per frequency and pop from these lists in order.

D. Maintain a global sorted list of elements by frequency and recency, and slice the top k on popK(k).

Solution

1. Step 1: Understand popK(k) requirements

   We must pop the top k elements by frequency and recency order, updating frequencies after each pop.

2. Step 2: Evaluate modifications

   Perform k consecutive pop() calls on the heap, updating frequencies after each pop. This performs k pops sequentially, each O(log n), correctly updating frequencies and maintaining heap invariants. Options A, B, and D either complicate the data structure or lose efficiency and correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sequential pops maintain correctness and efficiency [OK]

Hint: Sequential pops maintain heap correctness for top-k [OK]

Common Mistakes:

• Trying to pop multiple elements at once without updating frequencies
• Using complex data structures that break heap invariants

4. Suppose the problem changes: you must find the k closest points to the origin, but points can be repeated multiple times (i.e., duplicates allowed and must be counted separately). Which modification to the Quickselect approach correctly handles this scenario without increasing time complexity significantly?

hard

A. Use a max heap of size k to keep track of closest points, allowing duplicates naturally.

B. Use a min heap to store all points and pop k times to get closest points, handling duplicates automatically.

C. Sort all points by distance and then remove duplicates before returning the first k points.

D. Modify Quickselect to partition points by distance and include duplicates in the partitioning logic without skipping any points.

Solution

1. Step 1: Understand duplicates impact

   Duplicates must be treated as distinct points; Quickselect partitions by distance and does not rely on uniqueness.

2. Step 2: Modify partition to handle duplicates correctly

   Partition logic remains the same; all points, including duplicates, are compared and placed correctly without skipping.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Quickselect handles duplicates naturally if partitioning is correct [OK]

Hint: Quickselect partitions all points regardless of duplicates [OK]

Common Mistakes:

• Using min heap instead of max heap
• Removing duplicates before selection
• Sorting all points unnecessarily

5. Suppose you want to find the top k frequent words but now words can be reused infinitely many times (like unlimited supply). Which modification to the optimal bucket sort approach correctly handles this scenario?

hard

A. This problem reduces to a knapsack variant; bucket sort no longer applies

B. Modify frequency counting to consider infinite reuse, then apply bucket sort as usual

C. Use a dynamic programming approach to count combinations of words for frequencies

D. Use a max heap keyed by frequency and word lex order, repeatedly pop top k elements

Solution

1. Step 1: Understand infinite reuse impact

   Infinite reuse means frequency counts are not fixed; problem becomes combinatorial.

2. Step 2: Recognize problem class change

   Top k frequent words with unlimited reuse resembles knapsack or coin change, not simple frequency counting.

3. Step 3: Bucket sort no longer applies

   Bucket sort relies on fixed frequencies; dynamic programming or other combinatorial methods are needed.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Infinite reuse breaks frequency counting assumptions [OK]

Hint: Infinite reuse changes problem class, bucket sort invalid [OK]

Common Mistakes:

• Trying to reuse bucket sort with infinite counts
• Ignoring combinatorial explosion
• Assuming heap approach suffices