AlgoViz
HomeHeap / Priority Queue

Find K Closest Elements

Medium

Binary search the window's left edge

Problem

Given a sorted array, an integer x and k, return the k elements closest to x (in order).

In simple words

Binary-search the left edge of the best window of size k, comparing the two boundary distances.

The idea

The answer is a contiguous window of length k in the sorted array, so binary search where it begins by comparing the distance from x to each end of a candidate window. That gives O(log n + k) rather than heaping every element.

The trick

  • Search left in 0..n-k; compare x - a[mid] against a[mid+k] - x.
  • The result is contiguous because the array is sorted.
  • Ties prefer the smaller value.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
3
4
5
0
1
2
3
4

Step 1 of 2. Here's the example — arr=[1,2,3,4,5], k=4, x=3 Values: 1, 2, 3, 4, 5.

1/2
Optimal
timeO(log n + k)spaceO(1)
1lo=0; hi=n-k2while lo<hi: mid; if x-arr[mid] > arr[mid+k]-x: lo=mid+1 else hi=mid3return arr[lo..lo+k-1]

Input

array
[1, 2, 3, 4, 5]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 2, 3, 4, 5], k = 4, x = 3
Output:
[1, 2, 3, 4]
Explanation:
The 4 numbers nearest 3.

Example 2

Input:
nums = [1, 2, 3, 4, 5], k = 4, x = -1
Output:
[1, 2, 3, 4]
Explanation:
Nearest to -1 are the smallest 4.

Example 3

Input:
nums = [1, 5, 10], k = 2, x = 4
Output:
[1, 5]
Explanation:
1 and 5 sit closest to 4.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.