Find K-th Smallest Pair Distance

▶

Steps

setup

Sort the input array

The input array nums is sorted to [1,1,3]. Sorting is essential to generate pairs in order and efficiently compute distances.

💡 Sorting allows pairs to be generated in a structured way, enabling the heap to merge pairs by increasing distance.

Line:

nums.sort()

💡 Sorted array ensures pairs can be generated with increasing indices and distances can be computed directly.

setup

Initialize min-heap with first pairs

Push initial pairs formed by adjacent elements: (nums[0], nums[1]) and (nums[1], nums[2]) with their distances into the min-heap.

💡 Starting with pairs of adjacent elements ensures the smallest possible distances are considered first.

Line:

for i in range(n - 1):
    heapq.heappush(min_heap, (nums[i+1] - nums[i], i, i+1))

💡 The heap now contains pairs with their distances, ready for extraction in ascending order.

setup

Heap after initial insertions

The min-heap now contains two pairs: distance 0 from (nums[0], nums[1]) and distance 2 from (nums[1], nums[2]). The heap property is maintained.

💡 The heap root is the smallest distance pair, which is 0 here.

Line:

min_heap = [(nums[1] - nums[0], 0, 1), (nums[2] - nums[1], 1, 2)]

💡 The heap is ready for extraction of the smallest pair distance.

delete

Pop the smallest pair distance from heap

Pop the smallest distance pair from the heap, which is distance 0 from indices (0,1). This is the first smallest pair distance candidate.

💡 Extracting the smallest pair distance moves us closer to the k-th smallest distance.

Line:

dist, i, j = heapq.heappop(min_heap)

💡 The smallest pair distance is identified and removed from the heap for processing.

insert

Check if next pair can be pushed

Since j+1 = 2 < n, push the next pair (i=0, j=2) with distance nums[2] - nums[0] = 3 - 1 = 2 into the heap.

💡 Pushing the next pair extends the search for pairs starting at i=0 with increasing j.

Line:

if j + 1 < n:
    heapq.heappush(min_heap, (nums[j+1] - nums[i], i, j + 1))

💡 The heap now contains pairs with distances 2 and 2, maintaining candidates for smallest distances.

compare

Check if more pops needed (k=1)

Since k=1, no more pops are needed. The smallest pair distance at the root of the heap is the answer.

💡 When k=1, the first smallest pair distance is the root of the heap after initialization.

Line:

for _ in range(k - 1):
    ...
return min_heap[0][0]

💡 The heap root distance is the k-th smallest pair distance.

reconstruct

Return the k-th smallest pair distance

Return the distance at the root of the heap, which is 2, the k-th smallest pair distance for k=1 based on current heap state.

💡 The answer is the smallest distance pair found by the heap operations.

Line:

return min_heap[0][0]

💡 The algorithm efficiently returns the correct k-th smallest pair distance.

reconstruct

Summary of heap contents

The heap contains pairs with distances 2 and 2, showing all candidate pairs considered after popping the smallest pair.

💡 The heap structure reflects the pairs and their distances used to find the answer.

💡 The heap efficiently manages pairs to find the k-th smallest distance without enumerating all pairs.

reconstruct

Final answer confirmed

The k-th smallest pair distance is confirmed as 0, matching the expected output from the problem statement.

💡 The algorithm returns the correct answer efficiently.

💡 The heap-based approach correctly identifies the smallest pair distance.

reconstruct

End of algorithm

The algorithm completes with the answer 0 returned as the k-th smallest pair distance.

💡 The heap approach efficiently finds the answer without brute force.

💡 Heap-based k-selection with constraints is an efficient solution.

import heapq

def smallestDistancePair(nums, k):
    nums.sort()  # STEP 1: Sort the array
    n = len(nums)
    min_heap = []
    for i in range(n - 1):  # STEP 2: Push initial pairs
        heapq.heappush(min_heap, (nums[i+1] - nums[i], i, i+1))

    for _ in range(k - 1):  # STEP 4: Pop k-1 times
        dist, i, j = heapq.heappop(min_heap)
        if j + 1 < n:  # STEP 5: Push next pair if possible
            heapq.heappush(min_heap, (nums[j+1] - nums[i], i, j + 1))
    return min_heap[0][0]  # STEP 7: Return k-th smallest distance

if __name__ == '__main__':
    print(smallestDistancePair([1,3,1], 1))  # Output: 0

📊

Find K-th Smallest Pair Distance - Watch the Algorithm Execute, Step by Step

Watching each heap operation and pair insertion/removal helps you understand how the algorithm efficiently finds the k-th smallest pair distance without enumerating all pairs.

setupmin-heap

empty heap

insertmin-heapswap [1↔0]

0

0

2

1

heapify_upmin-heap

0

0

2

1

extract_minmin-heap

2

0

Added: 0

insertmin-heap

2

0

2

1

peekmin-heap

2

0

2

1

peekmin-heap

2

0

2

1

Added: 2

peekmin-heap

2

0

2

1

peekmin-heap

2

0

2

1

Added: 0

peekmin-heap

2

0

2

1

Added: 0

Key Takeaways

✓ The min-heap efficiently merges pairs by distance without enumerating all pairs.

Reading code alone doesn't show how the heap maintains the smallest pairs dynamically.

✓ Sorting the array is crucial to generate pairs in a structured order for heap insertion.

Understanding sorting's role clarifies why pairs are pushed in increasing order of indices.

✓ Each pop from the heap is followed by pushing the next pair extending the current pair's second index.

This step-by-step pair extension is key to the algorithm's efficiency and is clearer when visualized.

Practice

1. You need to design a data structure that supports two operations: push(val) which adds an integer to the structure, and pop() which removes and returns the most frequent element. If multiple elements have the same highest frequency, the most recently added among them is removed first. Which approach guarantees optimal time complexity for both operations?

easy

A. Maintain a frequency map and a max-heap keyed by frequency and recency (timestamp) to pop the correct element efficiently.

B. Use dynamic programming to precompute frequencies and then pop elements in order.

C. Use a priority queue keyed only by frequency, ignoring insertion order.

D. Use a single stack and scan it on each pop to find the most frequent element.

Solution

1. Step 1: Understand the problem constraints

   The data structure must return the element with the highest frequency, and if there's a tie, the most recently pushed element among them.

2. Step 2: Evaluate approaches

   Approach A is brute force and inefficient. Approach C ignores recency, so it fails tie-breaking. Approach B uses dynamic programming which is unrelated and inefficient for this problem. Approach D maintains a frequency map and a max-heap keyed by frequency and timestamp, ensuring O(log n) push and pop operations with correct tie-breaking.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max-heap with frequency and timestamp ensures correct order and efficiency [OK]

Hint: Max-heap with freq and timestamp breaks ties correctly [OK]

Common Mistakes:

• Ignoring recency in tie-breaking
• Using a single stack and scanning on pop
• Confusing DP with frequency tracking

2. Consider the following code snippet for finding the kth largest XOR coordinate value. Given the input matrix = [[5, 2], [1, 6]] and k = 3, what is the value of min_heap[0] returned by the function?

easy

A. 4

B. 5

C. 6

D. 7

Solution

1. Step 1: Compute prefix XOR matrix values

   prefix[1][1] = 5, prefix[1][2] = 7 (5^2), prefix[2][1] = 4 (5^1^0), prefix[2][2] = 0 (prefix[1][2]^prefix[2][1]^prefix[1][1]^matrix[1][1] = 7^4^5^6 = 0)

2. Step 2: Track min_heap of size k=3

   Values inserted: 5, 7, 4. The heap after these is [4,7,5]. The next value 0 is less than min_heap[0]=4, so ignored. The kth largest is min_heap[0] = 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap after all insertions has 4 as smallest among top 3 [OK]

Hint: Trace prefix XOR and heap insertions carefully [OK]

Common Mistakes:

• Off-by-one in prefix indices
• Miscomputing XOR values
• Confusing heap root with max value

3. Consider the following buggy implementation of the KthLargest class. Which line contains the subtle bug that can cause incorrect kth largest results?

import heapq

class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.heap = nums
        heapq.heapify(self.heap)
        # Bug: missing while loop to reduce heap size

    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]

medium

A. Missing while loop after heapify to pop extra elements

B. Line 6: self.heap = nums

C. Line 7: heapq.heapify(self.heap)

D. Line 5: self.k = k

Solution

1. Step 1: Analyze initialization

   The constructor heapifies the input list but does not reduce its size to k, so heap may contain more than k elements.

2. Step 2: Identify impact of missing size reduction

   Without popping extra elements, the heap size can exceed k, causing add() to behave incorrectly and return wrong kth largest values.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing size trimming after heapify breaks heap size invariant [OK]

Hint: Heap size must be trimmed to k after heapify [OK]

Common Mistakes:

• Forgetting to pop extra elements after heapify
• Misusing heapreplace when heap size < k
• Incorrectly initializing heap with nums reference

4. The following code attempts to find the top k frequent words using bucket sort. Identify the line containing the subtle bug that causes incorrect ordering when frequencies tie.

medium

A. Line with max_freq = max(freq.values())

B. Line with buckets[i].sort(reverse=True)

C. Line with freq[w] = freq.get(w, 0) + 1

D. Line with for i in range(max_freq, 0, -1)

Solution

1. Step 1: Understand sorting within buckets

   Words in each bucket must be sorted lexicographically ascending to break ties correctly.

2. Step 2: Identify incorrect sorting order

   Using sort(reverse=True) sorts words descending lex order, breaking tie rules.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct tie-break requires ascending lex order [OK]

Hint: Tie-break requires ascending lex sort, not descending [OK]

Common Mistakes:

• Sorting buckets descending lex order
• Using max heap instead of bucket
• Incorrect iteration order over buckets

5. Suppose the problem changes: now characters can be reused unlimited times (like infinite supply), and you want to return a string of length k with characters sorted by frequency descending. Which modification to the bucket sort approach correctly handles this variant?

hard

A. Use a max heap to repeatedly extract the highest frequency character and append it until length k is reached, decrementing frequency each time.

B. Use the same bucket sort but truncate the final concatenated string to length k.

C. Use bucket sort but repeat characters infinitely in buckets until length k is reached.

D. Sort characters by frequency once, then repeat the entire sorted string until length k is reached.

Solution

1. Step 1: Understand infinite reuse constraint

   Characters can be used multiple times, frequencies decrease as used.

2. Step 2: Why max heap is needed

   Max heap allows extracting highest frequency char, appending it, then updating frequency dynamically.

3. Step 3: Why bucket sort fails here

   Bucket sort assumes fixed frequencies; infinite reuse requires dynamic frequency updates.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Max heap supports dynamic frequency changes and repeated extraction [OK]

Hint: Infinite reuse needs dynamic frequency updates, not static buckets [OK]

Common Mistakes:

• Truncating static bucket sort output
• Repeating entire sorted string ignoring frequencies