Find K Closest Elements — Binary Search on Window Boundary

Problem Statement#

Given a sorted integer array arr, integers k and x, return the k integers closest to x. The result must be sorted ascending. If two integers are equidistant from x, prefer the smaller one.

Constraints:

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

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

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

Why This Problem Matters#

LeetCode 658 — Find K Closest Elements — is a Medium that Google, Amazon, and Microsoft love because it tests whether you can reason about the structure of an answer rather than reach for brute force. Candidates who sort by distance immediately leak that they treat the input as unordered, and interviewers downgrade them on the spot.

The problem is a litmus test for binary search creativity. The naive approach is O(n log n). The optimal one is O(log(n-k)+k) by binary searching on the left boundary of the answer window. Recognising that the answer must be a contiguous slice is the key signal interviewers want.

This pattern shows up in recommendation systems (k nearest items by score), geospatial queries on a single axis, and autocomplete ranking. Mastering it generalises to any "best window of fixed size in a sorted array" question.

The Core Insight#

Because arr is sorted, the k closest elements to x form a contiguous subarray of length k. There is no scenario where picking scattered elements beats picking a window — moving any element of the answer to a closer slot still leaves a contiguous window.

That reduces the problem to: find the best left boundary lo of the window arr[lo .. lo+k-1]. The valid range for lo is [0, n-k]. For a candidate mid, compare x - arr[mid] (left edge distance) with arr[mid+k] - x (the element just past the right edge). If the left edge is farther, slide the window right.

Equality must keep hi = mid so the search biases toward smaller starting indices, which encodes the tie-breaking rule. Once binary search converges, arr[lo : lo+k] is the answer in sorted order with no extra work.

Visual Dry Run#

arr = [1, 3, 6, 10, 15], k = 3, x = 7. Valid lo range: 0 to 2.

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

Solution (Optimal)#

class Solution:
    def findClosestElements(self, arr, k, x):
        # Binary search on the left boundary of the answer window.
        # Valid range for lo is [0, n - k].
        lo, hi = 0, len(arr) - k
 
        while lo < hi:
            mid = (lo + hi) // 2
 
            # Compare distance of left edge vs the element just past right edge.
            # Equality keeps hi = mid so we bias toward smaller starting indices.
            if x - arr[mid] > arr[mid + k] - x:
                lo = mid + 1
            else:
                hi = mid
 
        # Slice is already sorted because arr is sorted.
        return arr[lo : lo + k]

var findClosestElements = function(arr, k, x) {
    // Binary search on left boundary of the k-sized window.
    let lo = 0;
    let hi = arr.length - k;
 
    while (lo < hi) {
        const mid = Math.floor((lo + hi) / 2);
 
        // If left edge farther than the element past the right, slide right.
        if (x - arr[mid] > arr[mid + k] - x) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
 
    return arr.slice(lo, lo + k);
};

Time: O(log(n-k) + k) — log search plus O(k) slice for the output. Space: O(1) extra ignoring the output array.

Common Mistakes#

• Sorting by distance: O(n log n) and discards the sorted property.
• Using hi = n - 1 instead of hi = n - k: causes arr[mid + k] out-of-bounds.
• Wrapping the comparison in abs: unnecessary because both differences are non-negative for a sorted array.
• Flipping the inequality: breaks tie-breaking and returns larger elements.
• Re-sorting the slice: it is already sorted, the extra sort signals confusion.

Interview Tips#

• State up front that the answer is contiguous — that single observation drives the entire solution.
• Mention three approaches (sort, two-pointer shrink, binary search) and explain the trade-offs before coding.
• Walk through the inequality with concrete numbers so the interviewer trusts your tie-breaking.
• Confirm constraints out loud: lo upper bound is n - k, not n - 1.

Follow-up Questions#

• What if the array is not sorted? Sort first or use a max-heap of size k in O(n log k).
• What if k is 0? Return an empty list, skip the search.
• Solve it without binary search? Two pointers from both ends shrinking until size k, O(n - k).
• How does it extend to 2D points? 1D binary search does not generalise; use a k-d tree or heap by Euclidean distance.
• What if duplicates exist? The algorithm is unchanged; numeric comparisons handle ties correctly.

Key Takeaways#

• LeetCode 658 is a Medium asked at Google, Amazon, and Microsoft.
• The k closest elements in a sorted array always form a contiguous window of length k.
• Binary search the window left boundary in [0, n - k], not [0, n - 1].
• The decision rule is x - arr[mid] > arr[mid + k] - x to slide right.
• Tie-breaking is automatic when equality keeps hi = mid.
• Total time is O(log(n - k) + k); space is O(1) excluding output.
• Re-sorting the answer slice is wasted work because the input is already sorted.