Find K Closest Elements
Binary search on the leftmost index of the k-sized window minimizing distance to x.
3 min read
binary-search two-pointers
Problem#
Given a sorted array arr, an integer k, and a value x, return the k closest values to x in ascending order. Ties broken by smaller value.
Examples#
arr = [1,2,3,4,5], k = 4, x = 3→[1,2,3,4]
Constraints#
1 <= k <= arr.length <= 10^4.
Hints#
Hint 1
Binary search the leftmost index
i of the window [i, i+k). Compare x - arr[mid] vs arr[mid + k] - x. Approach#
Binary search over candidate window starts [0, n - k]. At mid, compare distances of arr[mid] and arr[mid + k] to x; the closer one wins. If arr[mid + k] is closer (or tied with a smaller index), shift right; else shift left. Output arr[lo..lo+k).
Solution#
class Solution {public: vector<int> findClosestElements(vector<int>& arr, int k, int x) { int lo = 0, hi = arr.size() - k; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1; else hi = mid; } return vector<int>(arr.begin() + lo, arr.begin() + lo + k); }};func findClosestElements(arr []int, k int, x int) []int { lo, hi := 0, len(arr)-k for lo < hi { mid := lo + (hi-lo)/2 if x-arr[mid] > arr[mid+k]-x { lo = mid + 1 } else { hi = mid } } out := make([]int, k) copy(out, arr[lo:lo+k]) return out}from typing import List
class Solution: def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]: lo, hi = 0, len(arr) - k while lo < hi: mid = lo + (hi - lo) // 2 if x - arr[mid] > arr[mid + k] - x: lo = mid + 1 else: hi = mid return arr[lo:lo + k]function findClosestElements(arr, k, x) { let lo = 0, hi = arr.length - k; while (lo < hi) { const mid = lo + ((hi - lo) >> 1); if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1; else hi = mid; } return arr.slice(lo, lo + k);}class Solution { public List<Integer> findClosestElements(int[] arr, int k, int x) { int lo = 0, hi = arr.length - k; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1; else hi = mid; } List<Integer> out = new ArrayList<>(k); for (int i = lo; i < lo + k; i++) out.add(arr[i]); return out; }}function findClosestElements(arr: number[], k: number, x: number): number[] { let lo = 0, hi = arr.length - k; while (lo < hi) { const mid = lo + ((hi - lo) >> 1); if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1; else hi = mid; } return arr.slice(lo, lo + k);}Editorial#
The window [i, i+k) is the answer iff arr[i-1] (if any) is farther from x than arr[i+k-1] AND arr[i+k] (if any) is farther than arr[i]. Binary searching the left edge directly avoids materializing distances or running a heap.
Complexity#
- Time: O(log(n - k) + k).
- Space: O(1) extra.
Concept revision#
Related#