Solution Approach

We use the standard binary search template with first_true_index to find the optimal starting position for the k-element window.

Binary Search Setup:

• left = 0: minimum possible starting position
• right = len(arr) - k: maximum possible starting position (window must fit in array)
• first_true_index = -1: tracks the first valid starting position

Feasible Condition: For any position mid, we check if mid is a valid starting position:

• Compare x - arr[mid] (distance from x to left boundary) with arr[mid + k] - x (distance from x to element just outside right boundary)
• If x - arr[mid] > arr[mid + k] - x: the element outside the window is closer, so mid is NOT valid (move right)
• Otherwise: mid is a valid starting position

Binary Search Template:

while left <= right:
    mid = (left + right) // 2
    if x - arr[mid] > arr[mid + k] - x:
        # Not feasible: arr[mid + k] is closer, should start later
        left = mid + 1
    else:
        # Feasible: arr[mid] is closer or equal, valid start
        first_true_index = mid
        right = mid - 1

Return Result: Return arr[first_true_index:first_true_index + k] - the k elements starting from the optimal position.

Why This Works: The feasibility pattern is monotonic. If position i is valid (starting there includes closer elements than starting later), then all positions j > i might also be valid, but we want the leftmost valid position. The template finds exactly this boundary.

Time Complexity: O(log(n - k)) for binary search, where n is the array length.

Space Complexity: O(1) excluding the output array.

Example Walkthrough

Let's trace through the binary search template with arr = [1, 2, 3, 4, 5, 6, 7], k = 3, x = 5.

Initial state:

• left = 0, right = 7 - 3 = 4, first_true_index = -1
• Possible starting positions: 0, 1, 2, 3, 4
• Feasible condition: x - arr[mid] <= arr[mid + k] - x (starting at mid is valid)

Iteration 1:

• mid = (0 + 4) // 2 = 2
• Check: x - arr[2] = 5 - 3 = 2, arr[2 + 3] - x = arr[5] - 5 = 6 - 5 = 1
• Is 2 > 1? Yes → NOT feasible (arr[5]=6 is closer than arr[2]=3)
• Update: left = 3

Iteration 2:

• left = 3, right = 4
• mid = (3 + 4) // 2 = 3
• Check: x - arr[3] = 5 - 4 = 1, arr[3 + 3] - x = arr[6] - 5 = 7 - 5 = 2
• Is 1 > 2? No → Feasible (arr[3]=4 is closer than arr[6]=7)
• Update: first_true_index = 3, right = 2

Iteration 3:

• left = 3, right = 2
• Loop ends: left > right

Result:

• first_true_index = 3
• Return arr[3:6] = [4, 5, 6]

Verification: Starting at index 3 gives window [4, 5, 6] with distances [1, 0, 1]. Starting at index 2 gives window [3, 4, 5] with distances [2, 1, 0]. Starting at index 4 gives window [5, 6, 7] with distances [0, 1, 2]. The window [4, 5, 6] has the smallest maximum distance, confirming our answer.

Time and Space Complexity

Time Complexity: O(log(n - k) + k)

The binary search runs on a search space of size n - k + 1 (possible starting positions), giving O(log(n - k)) iterations. Each iteration performs constant-time comparisons.

Creating the output slice takes O(k) time to copy k elements.

Overall: O(log(n - k) + k). When k is small relative to n, this is effectively O(log n). When k is close to n, this is O(k).

Space Complexity: O(k)

The algorithm uses only a few variables (left, right, mid, first_true_index) for O(1) auxiliary space. The output array requires O(k) space to store the k closest elements.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

The Pitfall: A common mistake is using while left < right with right = mid instead of the standard template with while left <= right and right = mid - 1.

Incorrect (non-standard template):

while left < right:
    mid = (left + right) // 2
    if x - arr[mid] > arr[mid + k] - x:
        left = mid + 1
    else:
        right = mid
return arr[left:left + k]

Correct (standard template):

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if x - arr[mid] > arr[mid + k] - x:
        left = mid + 1
    else:
        first_true_index = mid
        right = mid - 1
return arr[first_true_index:first_true_index + k]

The standard template with first_true_index clearly tracks the answer and handles edge cases consistently.

2. Incorrect Distance Comparison

The Pitfall: Using >= instead of > in the comparison, which changes the tiebreaker behavior. When distances are equal, we want to prefer the smaller element (leftmost window).

Incorrect:

if x - arr[mid] >= arr[mid + k] - x:  # WRONG: >= excludes equal case
    left = mid + 1

Correct:

if x - arr[mid] > arr[mid + k] - x:  # RIGHT: > includes equal case as valid
    left = mid + 1

When x - arr[mid] == arr[mid + k] - x, both elements are equidistant from x. The tiebreaker prefers the smaller element, so starting at mid is valid.

3. Off-by-One in Search Bounds

The Pitfall: Setting right = len(arr) - 1 instead of right = len(arr) - k.

Why it's wrong: If we start at position len(arr) - 1, we can't fit k elements. The window would extend beyond the array.

Correct: right = len(arr) - k ensures the k-element window always fits within the array.

4. Not Handling Edge Case: k Equals Array Length

The Pitfall: When k == len(arr), the search space is just one position (index 0), and right = 0.

The Solution: The template handles this correctly:

• left = 0, right = 0
• First iteration: mid = 0, checking arr[0] vs arr[k] (but arr[k] is out of bounds!)

Add a guard for this edge case:

if k == len(arr):
    return arr[:]