Compile Ready
Module 2 · Top K Pattern

Find K Closest Elements

MediumProblem 4 of 14 11 min read ~25 min to solve LeetCode
HeapPriority QueueBinary SearchSliding WindowSorting
Asked atMicrosoftAmazonGoogleMetaAppleBloomberg

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 must be sorted in ascending order. If two values are equally close, the smaller value is preferred.

Input

A sorted integer array arr, a window size k, and a target value x.

Output

A list of k values closest to x, sorted ascending.

Constraints

  • •1 <= k <= arr.length <= 10000
  • •arr is sorted in ascending order
  • •-10000 <= arr[i], x <= 10000

Examples

Example 1

Input: 
arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]
Explanation: The four closest values to 3 are 1, 2, 3, and 4. Value 5 is farther than 1 after the tie rules are applied.

Example 2

Input: 
arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]
Explanation: All values are to the right of x, so the first four array values are closest and already sorted.

Learning Objectives

  • Use sorted input to reduce the primary solution to a binary search over window starts.
  • Explain why the answer is always one contiguous length-k window in the sorted array.
  • Implement the heap alternative with distance and smaller-value tie-breaks.
  • Remember that the final result must be sorted ascending.

Intuition

Pattern Recognition

The signal is k closest elements plus a sorted array. This still looks like a top-k selection problem, but sorted order gives a stronger structure: the final answer must be a contiguous window of length k. So the primary interview solution is to binary search the left boundary of that window.

The heap-course trap is forgetting the tie-break and the final order. If you use a heap, compare by distance to x, and when distances tie, treat the larger value as worse because the smaller value should win. After selecting k values with the heap, sort them ascending before returning.

Common mistakes

  • ×Using a heap and returning values in heap order instead of sorted ascending order.
  • ×Breaking ties toward the larger value even though the problem prefers the smaller value.
  • ×Ignoring the sorted-array property and missing the O(log(n - k) + k) window solution.
  • ×Binary searching individual values instead of binary searching the left boundary of a length-k window.

Algorithm Explanation

Key idea

Because arr is sorted, the best k elements form one contiguous window. Compare two neighbouring candidate windows by looking at arr[mid] on the left edge and arr[mid + k] just outside the right edge. If arr[mid] is farther from x than arr[mid + k], the optimal window starts to the right; otherwise it starts at mid or earlier. The heap alternative keeps a size-k max-heap where the root is the worst retained value by distance, with larger value worse on ties.

Heap walkthrough

Use arr = [1,2,3,4,5], k = 4, and x = 3. The heap alternative stores the best four values, but exposes the worst retained value at the root. See 1, distance 2, heap becomes [1:d2]. See 2, distance 1, heap becomes [1:d2,2:d1]. See 3, distance 0, heap becomes [1:d2,2:d1,3:d0]. See 4, distance 1, heap becomes [1:d2,4:d1,3:d0,2:d1]. See 5, distance 2, push it; between 1 and 5, both have distance 2, but 5 is worse because ties prefer the smaller value. Pop 5 and keep [1,2,3,4]. Sorting the retained values gives [1,2,3,4].

Algorithm

  1. For the primary solution, set left = 0 and right = arr.length - k.
  2. While left < right, let mid be the middle possible window start.
  3. Compare distance from x to arr[mid] with distance from x to arr[mid + k].
  4. If the left edge is farther, move left to mid + 1; otherwise move right to mid.
  5. Return the k values from left through left + k - 1.
  6. For the heap alternative, push each value into a max-heap by distance, pop when size exceeds k, then sort the retained values ascending.

Solutions

Solution 1: Binary search the window start

When to prefer this:

Use this as the primary interview solution because the input array is already sorted and the answer is a contiguous window.

There are n - k + 1 possible windows of length k. Binary search the left boundary by comparing the value just inside the left edge with the value just outside the right edge. The comparison tells which side has the better window.

Step-by-step

  1. Search possible window starts from 0 to arr.length - k.
  2. For a middle start mid, compare x - arr[mid] with arr[mid + k] - x.
  3. If the left value is farther, discard starts up to mid.
  4. Otherwise keep mid and the starts to its left.
  5. Copy the k values beginning at the final left index into the answer list.
Time

O(log(n - k) + k)

Space

O(k)

Binary search finds the window start, then k sorted values are copied to the returned list; extra workspace besides output is O(1).

Java implementation

Loading…

Solution 2: Size-k max-heap by distance with sorted output

When to prefer this:

Use this to practise the heap top-k pattern, or when the input is not sorted and you still need k closest values by a comparator.

Keep a size-k heap whose root is the worst retained value: larger distance is worse, and for equal distance the larger value is worse. After the scan, sort the retained values because the problem requires ascending output.

Step-by-step

  1. Create a PriorityQueue that places the worst retained value at the root.
  2. Offer each value from arr into the heap.
  3. If the heap size exceeds k, poll the root to remove the worst candidate.
  4. Convert the heap to a list after all values are scanned.
  5. Sort the list ascending before returning it.
Time

O(n log k + k log k)

Space

O(k)

The heap is capped at k + 1 elements, and the final k retained values are sorted for the required ascending output.

Java implementation

Loading…

Dry Run

Sample input

arr = [1,2,3,4,5], k = 4, x = 3. Track the primary binary search over possible window starts.

leftrightmidcomparedecision
010x - arr[0] = 2, arr[4] - x = 2left edge is not farther, set right = 0

The search stops with left = 0, so copy four values starting at index 0. The sorted result is [1,2,3,4].

Interview Tips

Lead with the binary-search window because the input is sorted. Then, for a heap course or a follow-up, present the max-heap comparator carefully: worse means larger distance, and if distances tie, the larger value is worse. Always finish by sorting the selected values ascending.

Likely follow-ups

  • How would the solution change if the input array were not sorted?
  • Can you return the elements in their original input order instead of sorted order?
  • How would you support repeated queries with different x values on the same sorted array?
  • What if ties should prefer the larger value instead of the smaller value?

Similar Problems

K Closest Points to Origin
MediumAlso selects closest candidates by a distance metric.
Kth Largest Element in an Array
MediumUses a fixed-size heap to keep a top-k boundary.
Top K Frequent Elements
MediumAnother custom-priority top-k selection problem.
Sliding Window Median
HardRequires careful ordering and heap maintenance over a sorted boundary concept.

Key Takeaways

  • Sorted input makes the closest k elements a contiguous window problem.
  • Binary search over window starts gives O(log(n - k) + k) time.
  • A heap alternative must evict larger distance first and larger value first on ties.
  • The final answer must be sorted ascending, regardless of heap order.
Reusable template: When closest elements come from a sorted array, binary search the length-k window; otherwise use a size-k max-heap with an exact distance and tie comparator.