Find the K Closest Pairs in a Sorted Array
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement `k_closest_pairs(nums, k)` for a strictly increasing sorted array.
Consider every pair of indices `(i, j)` with `i < j`. Its distance is `nums[j] - nums[i]`. Return the `k` pairs with smallest distance as arrays `[nums[i], nums[j]]`, ordered by `(distance, i, j)` ascending. This ordering is the required tie-break rule.
### Constraints
- `2 <= len(nums) <= 200000`
- `-10^9 <= nums[i] < nums[i+1] <= 10^9`
- `1 <= k <= min(n*(n-1)/2, 200000)`
- Target substantially better than enumerating and sorting all `O(n^2)` pairs when `k` is small.
### Example
For `[1, 2, 4, 7, 11, 16]` and `k = 2`, return `[[1,2], [2,4]]` with distances one and two.
```hint Test nonadjacent candidates
The required set is defined over every pair, so include inputs where considering only neighboring values is not enough to produce all `k` results.
```
```hint Make ties observable
Include equal distances from different index pairs and verify the stated `(distance, i, j)` order.
```
Quick Answer: Implement `k_closest_pairs(nums, k)` for a strictly increasing sorted array. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
For every index pair `(i,j)` with `i<j` in a strictly increasing sorted array, define distance `nums[j]-nums[i]`. Return the k pairs `[nums[i],nums[j]]` with smallest keys `(distance,i,j)`, in that exact order. Avoid enumerating and sorting all quadratic pairs when k is small.
Constraints
- 2 <= len(nums) <= 200000 and nums is strictly increasing.
- Every value is an integer from -10^9 through 10^9.
- 1 <= k <= min(n*(n-1)/2, 200000).
- Return pairs ordered exactly by (distance, left index, right index).
Examples
Input: ([1, 2], 1)
Expected Output: [[1, 2]]
Explanation: The only pair is returned.
Input: ([1, 2, 4, 7, 11, 16], 2)
Expected Output: [[1, 2], [2, 4]]
Explanation: The source example returns distances one and two.
Hints
- Test k = 1 and k equal to the total number of pairs on a small input.
- Include a nonadjacent pair that appears before a much wider adjacent-to-prefix candidate.
- Use several equal distances to exercise both index tie fields and both numeric limits.