Find K Closest Elements (LC 658)
You're given a sorted integer array arr plus integers k and x; find the k values in arr that sit closest to x, and return them sorted in ascending order.
When comparing two candidates a and b for closeness to x: a wins if |a - x| < |b - x|, or if the distances tie and a < b.
Worked Examples
arr = [1,2,3,4,5], k = 4, x = 3[1,2,3,4]2, 3 and 4 are within 1 of x = 3. Both 1 and 5 are 2 away, and the tie goes to the smaller value, 1.arr = [1,1,2,3,4,5], k = 4, x = -1[1,1,2,3]x is below every value, so the four smallest values are the closest. The two 1s count as separate values.⚖️Formal Constraints & Bounds
1 <= k <= arr.length1 <= arr.length <= 104arris sorted in ascending order.-104 <= arr[i], x <= 104
Core Insight
Binary search the window's LEFT EDGE over [0, len(arr) - k - 1]. Comparing the departing element (x - arr[mid]) against the entering element (arr[mid + k] - x) is the monotonic feasibility question.
Real-World Scenario & Production Applications
Recommendation systems retrieving the k nearest neighbors to a query score from a pre-sorted index, and time-series systems fetching the k readings closest to a given timestamp.
Subproblems & Recurrence Decomposition3 Phases
The answer is always a single contiguous window of size k. Its left edge lo ranges over [0, len(arr) - k] -- that entire range is the binary search domain, not the array's values.
lo, hi = 0, len(arr) - kStep-by-Step Execution Trace Table
| Step | Search Domain [lo, hi] | mid | x - arr[mid] vs arr[mid+k] - x | Action | New Search Domain |
|---|---|---|---|---|---|
| 1 | [0, 0] (arr=[1,2,3,4,5], k=4, x=3) | 0 | 3-1=2 vs 5-3=2 → 2 > 2 is False | hi = mid - 1 = -1 | [0, -1] |
| 2 | [0, -1] | — | lo <= hi (0 <= -1) is False | Converged | Return arr[0:4] = [1,2,3,4] |
| 1 | lo, hi = 0, len(arr) - k - 1 |
| 2 | while lo <= hi: |
| 3 | mid = lo + (hi - lo) // 2 |
| 4 | if x - arr[mid] > arr[mid + k] - x: |
| 5 | lo = mid + 1 |
| 6 | else: |
| 7 | hi = mid - 1 |
| 8 | return arr[lo:lo + k] |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
There's no target index to find here — the thing being binary searched is the left edge of a sliding window of size k.
🥈 The Analogy: Sliding a Fixed-Size Frame Along a Number Line
Imagine a picture frame that can hold exactly k numbers, sliding along the sorted array. You want to park the frame so the k numbers inside are collectively closest to x. At any candidate position mid, sliding the frame one step right would drop arr[mid] (the leftmost element leaving) and pick up arr[mid + k] (the next element entering). Comparing "how far is the element about to leave" versus "how far is the element about to enter" tells you, with certainty, whether sliding right helps or hurts — and that yes/no question is monotonic across all valid left edges.
🔑 The Key Idea in the Code
Because arr is sorted, x - arr[mid] and arr[mid + k] - x shrink and grow predictably as the window slides, which is exactly the monotonic structure binary search needs — just measured between two elements a window-width apart, not between one element and x directly. When len(arr) == k (e.g. arr = [1], k = 1, x = 5), hi = len(arr) - k - 1 = -1, so the loop while lo <= hi never executes and returns arr[0:k] directly!
Binary searching closest element then expanding outward: Finding the single closest element and expanding two pointers outward takes and has complex edge-case bounds. Binary searching the sliding window starting index directly takes and is much cleaner.
Window comparator condition: When comparing window boundaries
midandmid + k, the transition condition isx - arr[mid] > arr[mid + k] - x. If the element atmid + kis closer toxthanarr[mid],lomust move tomid + 1.Tie-breaking preference for smaller values: When distances are equal (
|a - x| == |b - x|), the problem requires picking the smaller value. The strict inequality>ensures that ties prefer the left element.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Sorted array + fixed window size k + 'k closest elements to x' -- the answer is always a single CONTIGUOUS window, so its left edge is a search space of size n - k + 1.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: the optimal left edge candidate space is [lo, hi] = [0, len(arr) - k - 1]. Comparing x - arr[mid] (the element that would leave on a right shift) against arr[mid + k] - x (the element that would enter) tells you whether shifting right strictly helps, which is monotonic because arr is sorted.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Comparing arr[mid] directly to x instead of comparing the two elements a window-shift would trade (arr[mid] leaving vs arr[mid + k] entering).
Using >= instead of > in the comparison silently breaks the tie-breaking rule (prefer the smaller of two equally-close values).
Comparing abs(arr[mid] - x) with abs(arr[mid + k] - x) instead of the signed x - arr[mid] with arr[mid + k] - x: two equal values below x tie, the search stops too early, and arr = [0,2,2,2,3,3,5], k = 1, x = 6 returns [2] instead of [5].
The 60-Second Interview Pitch
Say this out loud before you type a single line
"Since the answer is always one contiguous window of size k, I binary search its left edge candidate space over [0, len(arr) - k - 1] using while lo <= hi. At each mid I compare x - arr[mid] (departing) against arr[mid + k] - x (entering): if departing is strictly farther, shifting right helps, so lo = mid + 1; otherwise hi = mid - 1. This converges on the optimal window left edge lo in O(log(n - k)) time, then an
O(k)slice returns the answer."
Complexity & Mathematical Proof
O(log(n - k) + k)
Look at the while loop: while lo <= hi: searches over the candidate window boundaries with hi = len(arr) - k - 1. Each iteration performs O(1) comparisons (x - arr[mid] vs arr[mid + k] - x) and halves the range, terminating in O(log(n - k)) iterations. Slicing arr[lo:lo + k] afterward costs O(k).
O(k) Output
Look at memory allocations: Call stack uses O(1) Iterative. The only allocation is the O(k) output slice returned to the caller -- no auxiliary heaps are used during the search itself.
Derivation Progression
Every valid window candidate is tested by its left edge, searching over N - K positions with while lo <= hi.
Comparing the departing and entering elements of a one-step shift is a monotonic O(1) feasibility test.
Binary search converges on the optimal left edge, then a single O(K) slice materializes the answer.
Variable Definitions
Total number of elements in the sorted array
Fixed size of the closest-elements window
Memory Architecture & Bounds
O(1) Iterative while loop with zero recursion frames
O(1) Only scalar pointers during the search
O(K) Result slice of K closest elements
Boundary Best / Worst Cases
when K == N (the whole array is the answer, no search needed).
.
for K ≪ N.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
The statement specifies a "sorted integer array arr, two integers k and x" and asks for the "k closest integers to x" Because the input array is already sorted, any closest elements must form a contiguous window of length ! Finding closest elements therefore reduces to finding the optimal left index of that window, denoted by left_index . This triggers a binary search directly over the window's starting index.
With , the search space for the left boundary of a length- window is strictly . Thus, lo = 0 and hi = len(arr) - k.
A common naive attempt is binary searching for and then using two pointers to expand outward. While correct, that approach takes and involves intricate boundary checks when pointers reach array ends. Binary searching the window left edge eliminates all pointer expansion logic. A subtle trap is comparing arr[mid] to directly instead of comparing the delta vs , which destroys monotonicity across window shifts.
Find K Closest Elements (LC 658)
You're given a sorted integer array arr plus integers k and x; find the k values in arr that sit closest to x, and return them sorted in ascending order.
When comparing two candidates a and b for closeness to x: a wins if |a - x| < |b - x|, or if the distances tie and a < b.
Worked Examples
arr = [1,2,3,4,5], k = 4, x = 3[1,2,3,4]2, 3 and 4 are within 1 of x = 3. Both 1 and 5 are 2 away, and the tie goes to the smaller value, 1.arr = [1,1,2,3,4,5], k = 4, x = -1[1,1,2,3]x is below every value, so the four smallest values are the closest. The two 1s count as separate values.⚖️Formal Constraints & Bounds
1 <= k <= arr.length1 <= arr.length <= 104arris sorted in ascending order.-104 <= arr[i], x <= 104
Core Insight
Binary search the window's LEFT EDGE over [0, len(arr) - k - 1]. Comparing the departing element (x - arr[mid]) against the entering element (arr[mid + k] - x) is the monotonic feasibility question.
Real-World Scenario & Production Applications
Recommendation systems retrieving the k nearest neighbors to a query score from a pre-sorted index, and time-series systems fetching the k readings closest to a given timestamp.
Subproblems & Recurrence Decomposition3 Phases
The answer is always a single contiguous window of size k. Its left edge lo ranges over [0, len(arr) - k] -- that entire range is the binary search domain, not the array's values.
lo, hi = 0, len(arr) - kStep-by-Step Execution Trace Table
| Step | Search Domain [lo, hi] | mid | x - arr[mid] vs arr[mid+k] - x | Action | New Search Domain |
|---|---|---|---|---|---|
| 1 | [0, 0] (arr=[1,2,3,4,5], k=4, x=3) | 0 | 3-1=2 vs 5-3=2 → 2 > 2 is False | hi = mid - 1 = -1 | [0, -1] |
| 2 | [0, -1] | — | lo <= hi (0 <= -1) is False | Converged | Return arr[0:4] = [1,2,3,4] |
| 1 | lo, hi = 0, len(arr) - k - 1 |
| 2 | while lo <= hi: |
| 3 | mid = lo + (hi - lo) // 2 |
| 4 | if x - arr[mid] > arr[mid + k] - x: |
| 5 | lo = mid + 1 |
| 6 | else: |
| 7 | hi = mid - 1 |
| 8 | return arr[lo:lo + k] |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
There's no target index to find here — the thing being binary searched is the left edge of a sliding window of size k.
🥈 The Analogy: Sliding a Fixed-Size Frame Along a Number Line
Imagine a picture frame that can hold exactly k numbers, sliding along the sorted array. You want to park the frame so the k numbers inside are collectively closest to x. At any candidate position mid, sliding the frame one step right would drop arr[mid] (the leftmost element leaving) and pick up arr[mid + k] (the next element entering). Comparing "how far is the element about to leave" versus "how far is the element about to enter" tells you, with certainty, whether sliding right helps or hurts — and that yes/no question is monotonic across all valid left edges.
🔑 The Key Idea in the Code
Because arr is sorted, x - arr[mid] and arr[mid + k] - x shrink and grow predictably as the window slides, which is exactly the monotonic structure binary search needs — just measured between two elements a window-width apart, not between one element and x directly. When len(arr) == k (e.g. arr = [1], k = 1, x = 5), hi = len(arr) - k - 1 = -1, so the loop while lo <= hi never executes and returns arr[0:k] directly!
Binary searching closest element then expanding outward: Finding the single closest element and expanding two pointers outward takes and has complex edge-case bounds. Binary searching the sliding window starting index directly takes and is much cleaner.
Window comparator condition: When comparing window boundaries
midandmid + k, the transition condition isx - arr[mid] > arr[mid + k] - x. If the element atmid + kis closer toxthanarr[mid],lomust move tomid + 1.Tie-breaking preference for smaller values: When distances are equal (
|a - x| == |b - x|), the problem requires picking the smaller value. The strict inequality>ensures that ties prefer the left element.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Sorted array + fixed window size k + 'k closest elements to x' -- the answer is always a single CONTIGUOUS window, so its left edge is a search space of size n - k + 1.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: the optimal left edge candidate space is [lo, hi] = [0, len(arr) - k - 1]. Comparing x - arr[mid] (the element that would leave on a right shift) against arr[mid + k] - x (the element that would enter) tells you whether shifting right strictly helps, which is monotonic because arr is sorted.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Comparing arr[mid] directly to x instead of comparing the two elements a window-shift would trade (arr[mid] leaving vs arr[mid + k] entering).
Using >= instead of > in the comparison silently breaks the tie-breaking rule (prefer the smaller of two equally-close values).
Comparing abs(arr[mid] - x) with abs(arr[mid + k] - x) instead of the signed x - arr[mid] with arr[mid + k] - x: two equal values below x tie, the search stops too early, and arr = [0,2,2,2,3,3,5], k = 1, x = 6 returns [2] instead of [5].
The 60-Second Interview Pitch
Say this out loud before you type a single line
"Since the answer is always one contiguous window of size k, I binary search its left edge candidate space over [0, len(arr) - k - 1] using while lo <= hi. At each mid I compare x - arr[mid] (departing) against arr[mid + k] - x (entering): if departing is strictly farther, shifting right helps, so lo = mid + 1; otherwise hi = mid - 1. This converges on the optimal window left edge lo in O(log(n - k)) time, then an
O(k)slice returns the answer."
Complexity & Mathematical Proof
O(log(n - k) + k)
Look at the while loop: while lo <= hi: searches over the candidate window boundaries with hi = len(arr) - k - 1. Each iteration performs O(1) comparisons (x - arr[mid] vs arr[mid + k] - x) and halves the range, terminating in O(log(n - k)) iterations. Slicing arr[lo:lo + k] afterward costs O(k).
O(k) Output
Look at memory allocations: Call stack uses O(1) Iterative. The only allocation is the O(k) output slice returned to the caller -- no auxiliary heaps are used during the search itself.
Derivation Progression
Every valid window candidate is tested by its left edge, searching over N - K positions with while lo <= hi.
Comparing the departing and entering elements of a one-step shift is a monotonic O(1) feasibility test.
Binary search converges on the optimal left edge, then a single O(K) slice materializes the answer.
Variable Definitions
Total number of elements in the sorted array
Fixed size of the closest-elements window
Memory Architecture & Bounds
O(1) Iterative while loop with zero recursion frames
O(1) Only scalar pointers during the search
O(K) Result slice of K closest elements
Boundary Best / Worst Cases
when K == N (the whole array is the answer, no search needed).
.
for K ≪ N.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
The statement specifies a "sorted integer array arr, two integers k and x" and asks for the "k closest integers to x" Because the input array is already sorted, any closest elements must form a contiguous window of length ! Finding closest elements therefore reduces to finding the optimal left index of that window, denoted by left_index . This triggers a binary search directly over the window's starting index.
With , the search space for the left boundary of a length- window is strictly . Thus, lo = 0 and hi = len(arr) - k.
A common naive attempt is binary searching for and then using two pointers to expand outward. While correct, that approach takes and involves intricate boundary checks when pointers reach array ends. Binary searching the window left edge eliminates all pointer expansion logic. A subtle trap is comparing arr[mid] to directly instead of comparing the delta vs , which destroys monotonicity across window shifts.