Top K Smallest Distances | Dataford Interview Questions

Given a sorted array of integers (e.g., [1, 2, 4, 7, 11, 16]), where distance between two numbers is defined as d = |a - b|, find the top K pairs with the smallest distances. For example, if K = 2, the result is [(1, 2), (2, 4)] corresponding to distances 1 and 2.

Asked in the Virtual Onsite stage. Implement top_k_pairs(nums, k).

Input and Output

nums is a sorted list of integers, and k is a positive integer. Return up to k pairs as lists [nums[i], nums[j]], ordered by increasing distance. Break equal-distance ties by increasing i, then increasing j.

Constraints

2 <= nums.length <= 10000
nums is sorted in nondecreasing order
-10^9 <= nums[i] <= 10^9
1 <= k <= 10^8
Pairs use distinct indices

Function Signature

def top_k_pairs(nums, k):

Your question is Top K Smallest Distances. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem