Log inSign up
mediumLeetCodeNot Started

Find K Closest Elements

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on LeetCode
Lesson

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 · Example 1: Target Inside Array:

Input: arr = [1, 2, 3, 4, 5], k = 4, x = 3
Output: [1, 2, 3, 4]
Explanation: Distances to 3: |1-3|=2, |2-3|=1, |3-3|=0, |4-3|=1, |5-3|=2. Closest 4 elements: 3 (dist 0), 2 (dist 1), 4 (dist 1), 1 (dist 2 vs 5 tie breaker 1 < 5). Result: [1, 2, 3, 4]. Heap Tree of Size K=4 (Max-Heap by distance): (dist 2, val 1) / \ (dist 1, val 2) (dist 1, val 4) / (dist 0, val 3)

Example 2 · Example 2: Target Less Than Minimum:

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

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why the k closest elements must form a contiguous subarray.
  • Implement the size-k Max-Heap pattern for top/closest problems.
  • Master the subtle binary search condition: x - arr[mid] > arr[mid + k] - x.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find K closest elements to a target value in a sorted array.
  • Tie-breaker prefers smaller element values.
  • Array is already sorted.

Algorithmic Decision Tree:

  • Max-Heap of size K works well when data is unsorted or streaming.
  • Because the input is sorted, Binary Search on the window's starting index yields optimal O(log(N - K) + K) time.

Connected Patterns:

K Closest Points to OriginTop K Frequent ElementsKth Smallest Element in a Sorted Matrix

1. Brute Force — Sort by Custom Distance Comparator

Intuition

Clone array, sort using comparator (abs(a - x), a), slice first k elements, and sort the result in ascending order.

When to apply: When simplicity is valued over time efficiency and N is small.

Algorithm

  1. Step 1: Create a copy of the array.
  2. Step 2: Sort by custom comparator: abs(a - x) < abs(b - x) or (abs(a - x) == abs(b - x) && a < b).
  3. Step 3: Take the first k elements.
  4. Step 4: Sort these k elements in ascending order and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <cmath>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> findClosestElements(vector<int>& arr, int k, int x) {
10 vector<int> sortedArr = arr;
11 sort(sortedArr.begin(), sortedArr.end(), [x](int a, int b) {
12 int d1 = abs(a - x);
13 int d2 = abs(b - x);
14 if (d1 != d2) return d1 < d2;
15 return a < b;
16 });
17 vector<int> result(sortedArr.begin(), sortedArr.begin() + k);
18 sort(result.begin(), result.end());
19 return result;
20 }
21};
22
23int main() {
24 Solution sol;
25 vector<int> arr = {1, 2, 3, 4, 5};
26 vector<int> res = sol.findClosestElements(arr, 4, 3);
27 cout << "K Closest (Brute Force): ";
28 for (int v : res) cout << v << " ";
29 cout << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N log N) — O(N log N) dominated by full array sorting.
  • Space complexity: O(N) — O(N) auxiliary space to clone and sort the array.

Why Brute Force Doesn't Scale:

With N = 105, O(N log N) takes ~1.7 * 106 ops. Binary search takes O(log N) which is only ~17 operations.

Binary search takes ~0.01ms versus ~30ms for sorting.

2. Better — Max-Heap of Size K

Intuition

By maintaining a Max-Heap of size k, the element with the maximum distance among the current k closest elements is always at the root. If a new element is closer than the root, pop root and push new element.

When to apply: When inputs are arriving in a stream or array is unsorted.

Algorithm

  1. Step 1: Create a Max-Heap comparing (abs(val - x), val).
  2. Step 2: For each num in arr: push num into heap.
  3. Step 3: If heap size > k, pop top.
  4. Step 4: Collect remaining k elements, sort ascending, and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <cmath>
5#include <algorithm>
6using namespace std;
7
8class Solution {
9public:
10 vector<int> findClosestElements(vector<int>& arr, int k, int x) {
11 auto comp = [x](const int& a, const int& b) {
12 int d1 = abs(a - x);
13 int d2 = abs(b - x);
14 if (d1 != d2) return d1 < d2;
15 return a < b;
16 };
17 priority_queue<int, vector<int>, decltype(comp)> maxHeap(comp);
18
19 for (int num : arr) {
20 maxHeap.push(num);
21 if ((int)maxHeap.size() > k) {
22 maxHeap.pop();
23 }
24 }
25
26 vector<int> result;
27 while (!maxHeap.empty()) {
28 result.push_back(maxHeap.top());
29 maxHeap.pop();
30 }
31 sort(result.begin(), result.end());
32 return result;
33 }
34};
35
36int main() {
37 Solution sol;
38 vector<int> arr = {1, 2, 3, 4, 5};
39 vector<int> res = sol.findClosestElements(arr, 4, 3);
40 cout << "K Closest (Max-Heap): ";
41 for (int v : res) cout << v << " ";
42 cout << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N log K) — O(N log K) due to heap operations of bounded size K.
  • Space complexity: O(K) — O(K) auxiliary space for heap.

3. Optimal — Binary Search on Window Start Index

Intuition

Since the array is sorted, the K closest elements form a contiguous block. The starting index must be in [0, N - K]. For candidate start mid, compare arr[mid] and arr[mid + K]: if x - arr[mid] > arr[mid + K] - x, arr[mid + K] is strictly closer to x than arr[mid], meaning mid is too far left, so left = mid + 1. Otherwise right = mid.

When to apply: Standard optimal approach for sorted arrays.

Algorithm

  1. Step 1: Set left = 0, right = arr.length - k.
  2. Step 2: While left < right: mid = left + (right - left) / 2.
  3. Step 3: If x - arr[mid] > arr[mid + k] - x, set left = mid + 1.
  4. Step 4: Else set right = mid.
  5. Step 5: Return subarray arr[left ... left + k - 1].

Interactive Trace for Find K Closest Elements

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Process elements [1, 2, 3, 4]
Visual state
Values and pointers at this exact step
tree
Root: (dist 2, val 1)
1
Child: (dist 1, val 2)
2
Child: (dist 1, val 4)
4
Leaf: (dist 0, val 3)
3

Node order shown; add connections to display explicit tree edges.

top: h1
Check / comparison
Heap size = 4. Root is (dist 2, val 1).
Decision / next transition
Next element will be compared against root.
Why this step matters

Step 1: Process elements [1, 2, 3, 4]. All 4 elements fit into Max-Heap of capacity k=4.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5class Solution {
6public:
7 vector<int> findClosestElements(vector<int>& arr, int k, int x) {
8 int left = 0;
9 int right = arr.size() - k;
10
11 while (left < right) {
12 int mid = left + (right - left) / 2;
13 if (x - arr[mid] > arr[mid + k] - x) {
14 left = mid + 1;
15 } else {
16 right = mid;
17 }
18 }
19
20 return vector<int>(arr.begin() + left, arr.begin() + left + k);
21 }
22};
23
24int main() {
25 Solution sol;
26 vector<int> arr = {1, 2, 3, 4, 5};
27 vector<int> res = sol.findClosestElements(arr, 4, 3);
28 cout << "K Closest (Optimal Binary Search): ";
29 for (int v : res) cout << v << " ";
30 cout << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(log(N - K) + K) — O(log(N - K) + K) due to binary search and output extraction.
  • Space complexity: O(1) — O(1) auxiliary space (excluding result array).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Sort by Absolute DifferenceO(N log N)O(N)Sort all elements using custom comparator (|a - x|, a). Take first k elements and sort them ascending.Full O(N log N) sorting.
2.Better — Max-Heap of Size KO(N log K)O(K)Maintain a Max-Heap of size K with pair (|arr[i] - x|, arr[i]). Evict further elements as we iterate.Push/pop operations for all N elements.
3.Optimal — Binary Search on Window StartOptimalO(log(N - K) + K)O(1) auxiliaryBinary search for window start index in [0, N - K]. Compare distances from x to arr[mid] and arr[mid + k].None. Optimal.

Common Pitfalls & Crucial Edge Cases

Searching range [0, N-1] instead of [0, N - K]

Window must have size k, so starting index cannot exceed N - K.

Incorrect comparison in binary search

Comparing x - arr[mid] vs arr[mid + k] - x without considering algebraic signs.

Forgetting to sort heap output

Max-Heap extracts elements in non-ascending order; must sort before returning.

Crucial Edge Cases to Validate:

  • k == arr.length — Entire array is returned.
  • x < arr[0] — Target is smaller than all elements; returns first k elements.
  • x > arr[n - 1] — Target is larger than all elements; returns last k elements.
  • Ties (|a - x| == |b - x|) — Invariant correctly chooses smaller element value.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the Max-Heap approach first to demonstrate general heap knowledge, then observe that the array is sorted and optimize with Binary Search.
  2. Highlight the window start binary search condition.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must the k closest elements in a sorted array form a contiguous window?

Back to DSA Sheet