Find the K Closest Pairs in a Sorted Array

Quick Overview

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.

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.

|Home/Coding & Algorithms/Apple
Apple logo
Apple
Aug 9, 2026, 12:00 AM
mediumSoftware EngineerOnsiteCoding & Algorithms
0
0

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.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...