Find K Closest Elements — Binary Search on Window Boundary [LC 658, Amazon, Meta]

Problem Statement#

LeetCode 658 — Find K Closest Elements · Difficulty: Medium

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should be sorted in ascending order.

An integer a is closer to x than integer b if:

• |a - x| < |b - x|, or
• |a - x| == |b - x| and a < b (prefer the smaller element on ties)

Constraints:

• 1 <= k <= arr.length
• 1 <= arr.length <= 10^4
• arr is sorted in ascending order
• -10^4 <= arr[i], x <= 10^4

Example 1:

Input:  arr = [1, 2, 3, 4, 5], k = 4, x = 3
Output: [1, 2, 3, 4]
Explanation: All four closest to 3 are 1, 2, 3, 4 (distances: 2, 1, 0, 1).
             5 is excluded (distance 2 from 3, but 1 is preferred on tie).

Example 2:

Input:  arr = [1, 2, 3, 4, 5], k = 4, x = -1
Output: [1, 2, 3, 4]
Explanation: x is far left; the closest k elements are the leftmost k.

Example 3:

Input:  arr = [1, 3, 6, 10, 15], k = 3, x = 7
Output: [3, 6, 10]
Explanation: distances from 7: |1-7|=6, |3-7|=4, |6-7|=1, |10-7|=3, |15-7|=8.
             3 smallest distances belong to 6, 10, 3 → sorted: [3, 6, 10].

Why This Problem Matters#

LC 658 is a deceptively tricky problem that trips up candidates who reach for the obvious approach (binary search for x, then two-pointer expand outward). That approach works and is O(log n + k), but the binary search on window boundary is more elegant and reveals a deeper technique: binary searching on the position of the result, not on the target itself.

Amazon, Meta, and Microsoft ask this problem specifically to see if candidates can reframe "find the best window of size k" as "find the best left index". Once you see that the answer is always a contiguous window of length k in a sorted array, the problem reduces to a classic left-boundary binary search.

This reframing generalises. Many interview problems that ask for the "best k elements" in sorted data can be solved by binary searching on the left (or right) boundary of the answer window rather than on the elements themselves. Understanding this here pays dividends across dozens of harder problems.

The Core Insight#

Since arr is sorted, the k closest elements always form a contiguous subarray of length k. This is not obvious at first, but consider: if you picked a non-contiguous set, you could always swap an included far element for the excluded nearer element between the gaps, improving or maintaining closeness. So the answer is always arr[lo : lo + k] for some left index lo.

This reduces the problem to: find the optimal lo where 0 <= lo <= len(arr) - k.

Binary search on lo over the range [0, n - k]. At each candidate lo, compare:

• The left candidate: arr[mid] at distance x - arr[mid]
• The right candidate: arr[mid + k] at distance arr[mid + k] - x

If x - arr[mid] > arr[mid + k] - x, the right boundary element arr[mid + k] is strictly closer than the left boundary arr[mid], so we should shift the window right: lo = mid + 1.

Otherwise (left is at least as close as right, or tied — and on ties we prefer the smaller element, which means the left window wins), keep hi = mid.

This comparison elegantly encodes the tie-breaking rule: equal distances prefer the smaller element, which is always in the left position.

Visual Dry Run#

Input: arr = [1, 2, 3, 4, 5], k = 4, x = 3

Search range for lo: [0, n-k] = [0, 1]

Result: arr[0:4] = [1, 2, 3, 4]. Correct.

Input: arr = [1, 3, 6, 10, 15], k = 3, x = 7

Search range: [0, 2]

Result: arr[2:5] = [6, 10, 15]... wait, x = 7 and distances are |6-7|=1, |10-7|=3, |15-7|=8. But arr[1]=3 has distance 4. So the window [3,6,10] (indices 1-3) with distances 4,1,3 sums smaller than [6,10,15] (distances 1,3,8). Let's retrace:

Search range: [0, 2]

Actually lo converged to 2, giving arr[2:5] = [6, 10, 15]. But the correct answer is [3, 6, 10]. Let's re-examine step 1: mid = (0+2)//2 = 1. arr[1] = 3, arr[1+3] = arr[4] = 15. x - arr[mid] = 7 - 3 = 4. arr[mid+k] - x = 15 - 7 = 8. Since 4 < 8 → left is closer → hi = mid = 1.

Result: arr[1:4] = [3, 6, 10]. Correct.

Common Mistakes#

1. Binary searching for x and then two-pointer expanding. This works in O(log n + k) but fails the follow-up constraint of O(log(n-k)). More importantly, it does not demonstrate the window-boundary insight. Interviewers often push back and ask for the O(log(n-k)) solution specifically.

2. Setting hi = len(arr) - 1 instead of len(arr) - k. The window [lo, lo+k-1] must fit entirely in the array. lo can be at most len(arr) - k. Using len(arr) - 1 as the upper bound causes arr[mid + k] to go out of bounds.

3. Getting the comparison direction backwards. x - arr[mid] > arr[mid + k] - x means the right element is closer, so move right (lo = mid + 1). Flipping the comparison moves left when it should move right, converging to the wrong window.

4. Not handling the tie-breaking correctly. On ties (x - arr[mid] == arr[mid + k] - x), the problem says prefer the smaller element. The smaller element is arr[mid] (left side). So ties should keep hi = mid, not move lo = mid + 1. The condition > (strict) naturally encodes this: equal means go left (hi = mid).

5. Sorting the output. The result is already a subarray of a sorted array, so it is automatically sorted. Adding a sort step is harmless but signals you did not think about the output structure.

6. Assuming x must be in arr. x can be any value, including one not present in the array. The algorithm works identically — it compares distances, not equality.

Solutions#

Python#

def findClosestElements(arr: list[int], k: int, x: int) -> list[int]:
    # Binary search for the left boundary of the k-element window.
    # The window is always arr[lo : lo+k] for some lo in [0, n-k].
    lo, hi = 0, len(arr) - k        # lo ranges over valid left-boundary positions
 
    while lo < hi:                   # converge to the optimal left boundary
        mid = lo + (hi - lo) // 2   # candidate left boundary
 
        # Compare the left edge of the window (arr[mid])
        # against the element just beyond the right edge (arr[mid+k]).
        # If the right element is strictly closer to x, shift window right.
        if x - arr[mid] > arr[mid + k] - x:
            lo = mid + 1            # arr[mid+k] is closer; exclude arr[mid] side
        else:
            hi = mid                # arr[mid] is as close or closer; keep it
 
    # lo == hi: optimal left boundary found; return the k-element window
    return arr[lo : lo + k]

JavaScript#

function findClosestElements(arr, k, x) {
    // Search for the left boundary of the best k-element window.
    let lo = 0;
    let hi = arr.length - k;        // window [lo, lo+k-1] must fit; lo at most n-k
 
    while (lo < hi) {               // converge until one left boundary remains
        const mid = lo + Math.floor((hi - lo) / 2); // safe midpoint
 
        // arr[mid] is the left edge of the candidate window.
        // arr[mid + k] is the element just beyond the right edge.
        // If the right element is strictly closer to x, move window right.
        if (x - arr[mid] > arr[mid + k] - x) {
            lo = mid + 1;           // shift window right: right edge is closer
        } else {
            hi = mid;               // keep current or shift left: left edge wins
        }
    }
 
    // lo is the optimal left boundary; slice out the k-element answer
    return arr.slice(lo, lo + k);
}

Complexity Analysis#

The binary search runs over n - k + 1 positions, so it takes O(log(n-k)) iterations. The output slice is O(k). Total: O(log(n-k) + k). For k close to n, this approaches O(n); for small k, it approaches O(log n).

Space is O(k) for the returned slice (or O(1) if you count only auxiliary space and return a view).

Follow-up Questions#

Q: What if arr is not sorted? Sort it first in O(n log n), then apply this algorithm. The guarantee that the answer is contiguous only holds for sorted arrays.

Q: What if you want the k closest by absolute distance, ignoring tie-breaking? The algorithm is identical. The tie-breaking only affects which of two equidistant windows you pick, and the > (strict) comparison already handles it correctly.

Q: Can you solve this with a sliding window without binary search? Yes, with O(n) time: slide a window of size k across the array, keeping the one with the best boundary. But O(log(n-k)) is strictly better when k is small.

Q: How does this extend to finding the k closest points in 2D? In 2D there is no sorted order, so the window trick does not apply. You would use a max-heap of size k in O(n log k).

This Pattern Solves#

• LC 658 — Find K Closest Elements (this problem)
• LC 35 — Search Insert Position (left-boundary binary search)
• LC 34 — Find First and Last Position (dual boundary search)
• LC 1150 — Check If a Number Is Majority Element in a Sorted Array
• Any problem where the answer is a contiguous window in a sorted structure and you need to find its optimal start position

Key Takeaway#

When the answer to "find the best k elements in a sorted array" is always a contiguous window, binary search on the window's left boundary — not on the elements themselves. The comparison x - arr[mid] > arr[mid+k] - x tells you whether to shift the window right. The while lo < hi loop with hi = mid converges to the optimal left index. This window-boundary reframing is the core technique for a family of "best k in sorted array" problems that appear regularly in FAANG interviews.

Key Takeaways#

• LC 658 is asked by Amazon and Microsoft; it tests the non-obvious insight that binary search applies to window positions, not just element values.
• The k closest elements always form a contiguous window in a sorted array — this contiguity property is the prerequisite for the window-boundary trick.
• Binary search on lo in range [0, n - k]: the left edge of the optimal window is the only unknown, and it is a position, not a value.
• The comparison x - arr[mid] > arr[mid + k] - x checks whether the right neighbour of the window is strictly closer to x than the left edge — if so, shift right.
• Use while lo < hi with hi = mid on the else branch to preserve mid as a valid left boundary candidate.
• Time complexity is O(log(n - k) + k): O(log(n-k)) for the binary search, O(k) for the output slice — strictly better than heap-based approaches for small k.
• If the array is unsorted, sort first in O(n log n) then apply this algorithm; the sorted-array guarantee is essential for contiguity.