Skip to main content

658 - Find K Closest Elements

Difficulty: Medium | Pattern: Binary Search | Company tags: Google, Amazon, Facebook

Problem Statement​

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

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

  • |a - x| < |b - x|, or
  • |a - x| == |b - x| and a < b

Example 1:

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

Example 2:

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

Approach: Binary Search for Window Start — O(log(n-k) + k)​

Key insight: The answer is a contiguous window of size k. Binary search for the optimal starting position. The window [lo, lo+k] should start where x - arr[mid] vs arr[mid+k] - x favors the right element being further.

import bisect

def findClosestElements(arr: list[int], k: int, x: int) -> list[int]:
    lo, hi = 0, len(arr) - k
    
    while lo < hi:
        mid = (lo + hi) // 2
        # Compare: is arr[mid+k] closer to x than arr[mid]?
        if x - arr[mid] > arr[mid + k] - x:
            lo = mid + 1
        else:
            hi = mid
    
    return arr[lo:lo + k]

Dry Run​

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

lo=0, hi=1 (len=5, 5-4=1)

lohimidarr[mid]arr[mid+k]x-arr[mid]=3-1=2 vs arr[mid+k]-x=5-3=2action
010152 vs 2 → equal → hi=0hi=mid=0

lo=0=hi → return arr[0:4] = [1,2,3,4] ✓

Tie-Breaking: Why > Not >=?​

When x - arr[mid] == arr[mid+k] - x, we prefer the smaller values → keep hi = mid (left window). Only use lo = mid+1 when right element is strictly closer.

Complexity​

  • Time: O(log(n-k) + k) — binary search + slice
  • Space: O(k) for output