Find K Closest Elements

Description

You are given a sorted integer array arr, and two integers k and x. Your task is to find the k integers in the array that are closest to x. Return these k integers sorted in ascending order.

Closeness is determined by absolute difference: an integer a is closer to x than b if |a - x| < |b - x|. If two integers have the same absolute difference from x (i.e., |a - x| == |b - x|), the smaller integer is considered closer.

The result will always be a contiguous subarray of the original sorted array, because in a sorted array, the k closest elements to any value form a consecutive segment.

Examples

Example 1

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

Output: [1, 2, 3, 4]

Explanation: The distances from x=3 are: |1-3|=2, |2-3|=1, |3-3|=0, |4-3|=1, |5-3|=2. The four closest elements are 2 (distance 1), 3 (distance 0), 4 (distance 1), and either 1 or 5 (both distance 2). Since 1 < 5, the tie-breaker favors 1. So the answer is [1, 2, 3, 4].

Example 2

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

Output: [1, 1, 2, 3]

Explanation: The value x = -1 is smaller than all elements. The distances are: |1-(-1)|=2, |1-(-1)|=2, |2-(-1)|=3, |3-(-1)|=4, |4-(-1)|=5, |5-(-1)|=6. The four closest are the four with smallest distances: the two 1s (distance 2 each), then 2 (distance 3), then 3 (distance 4). Result: [1, 1, 2, 3].

Example 3

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

Output: [2, 3, 4, 5]

Explanation: The value x = 6 is larger than all elements. Distances are: |1-6|=5, |2-6|=4, |3-6|=3, |4-6|=2, |5-6|=1. The four closest are 5 (distance 1), 4 (distance 2), 3 (distance 3), and 2 (distance 4). Sorted ascending: [2, 3, 4, 5].

Constraints

1 ≤ k ≤ arr.length
1 ≤ arr.length ≤ 10^4
arr is sorted in ascending order
-10^4 ≤ arr[i], x ≤ 10^4

Editorial

Brute Force

Intuition

The most direct way to solve this is to sort all elements by how close they are to x, then pick the first k elements.

For each element, we compute the absolute difference |arr[i] - x|. We sort the array by this distance (with the tie-breaking rule: if two elements have the same distance, the smaller one comes first). After sorting, the first k elements are the closest. Finally, we sort those k elements in ascending order for the output.

Think of it like lining up people by how far they live from a meeting point. Everyone computes their commute distance, stands in order from shortest to longest commute, and you pick the first k people. Then you rearrange those k people alphabetically (by value) for the final roster.

Step-by-Step Explanation

Let's trace through with arr = [1, 2, 3, 4, 5], k = 4, x = 3:

Step 1: Compute distances from x=3 for each element.

arr[0]=1: |1-3| = 2
arr[1]=2: |2-3| = 1
arr[2]=3: |3-3| = 0
arr[3]=4: |4-3| = 1
arr[4]=5: |5-3| = 2

Step 2: Sort by distance (tie-break: smaller value first).

Distance 0: [3]
Distance 1: [2, 4] (2 < 4, so 2 comes first)
Distance 2: [1, 5] (1 < 5, so 1 comes first)
Sorted order: [3, 2, 4, 1, 5]

Step 3: Pick the first k=4 elements: [3, 2, 4, 1]

Step 4: Sort these 4 elements in ascending order: [1, 2, 3, 4]

Result: [1, 2, 3, 4]

Brute Force — Sort by Distance, Pick K Closest — Watch how we compute distances from x, sort elements by closeness, pick k elements, then sort the result.

Algorithm

Sort the array using a custom comparator:
- Compare |a - x| vs |b - x|
- If equal, the smaller element comes first
Take the first k elements from the sorted array
Sort these k elements in ascending order
Return the sorted result

Code

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        vector<int> sorted_arr = arr;
        
        sort(sorted_arr.begin(), sorted_arr.end(), [x](int a, int b) {
            int diffA = abs(a - x);
            int diffB = abs(b - x);
            if (diffA == diffB) return a < b;
            return diffA < diffB;
        });
        
        vector<int> result(sorted_arr.begin(), sorted_arr.begin() + k);
        sort(result.begin(), result.end());
        return result;
    }
};

class Solution:
    def findClosestElements(self, arr: list[int], k: int, x: int) -> list[int]:
        sorted_arr = sorted(arr, key=lambda a: (abs(a - x), a))
        result = sorted_arr[:k]
        result.sort()
        return result

import java.util.*;

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> sortedArr = new ArrayList<>();
        for (int num : arr) sortedArr.add(num);
        
        sortedArr.sort((a, b) -> {
            int diffA = Math.abs(a - x);
            int diffB = Math.abs(b - x);
            if (diffA == diffB) return a - b;
            return diffA - diffB;
        });
        
        List<Integer> result = sortedArr.subList(0, k);
        Collections.sort(result);
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Sorting the entire array by distance takes O(n log n). Picking the first k elements is O(k). Sorting the result is O(k log k). The dominant term is O(n log n).

Space Complexity: O(n)

We create a copy of the array for sorting, which takes O(n) space. The result array takes O(k) space.

Why This Approach Is Not Efficient

The brute force completely ignores the fact that the input array is already sorted. Sorting a sorted array by a different criterion takes O(n log n), but we should be able to leverage the existing order.

A crucial observation: in a sorted array, the k closest elements to x always form a contiguous subarray. Why? Because if elements a < b < c are in the array and both a and c are among the k closest but b is not, then b must be closer to x than at least one of a or c (since b lies between them), creating a contradiction.

This means we don't need to sort at all — we just need to find the correct starting position of a window of size k. This can be done more efficiently.

Better Approach - Two Pointers Shrinking

Intuition

Since the k closest elements form a contiguous subarray, we can start with the entire array and repeatedly remove the element that is farthest from x, until only k elements remain.

We use two pointers: left at the start and right at the end of the array. At each step, we compare the distances of the boundary elements:

If |arr[left] - x| > |arr[right] - x|, the left element is farther — remove it by moving left forward.
If |arr[right] - x| > |arr[left] - x|, the right element is farther — remove it by moving right backward.
If they're equidistant, the tie-breaker says we prefer smaller values, so we remove the right element (the larger one).

We repeat until right - left + 1 == k.

Imagine a group photo where everyone lines up by height. The photographer needs only k people closest to a marker. They start trimming from whichever end is farther from the marker, one person at a time, until k people remain.

Step-by-Step Explanation

Let's trace through with arr = [1, 2, 3, 4, 5], k = 4, x = 3:

Step 1: Initialize left=0, right=4. Window size = 5. We need to remove 5-4 = 1 element.

Step 2: Compare boundaries:

|arr[0] - 3| = |1 - 3| = 2
|arr[4] - 3| = |5 - 3| = 2
Equal distance! Tie-break: prefer smaller value → remove arr[right]=5.
Move right to 3.

Step 3: Window is [1, 2, 3, 4], size = 4 = k. Done!

Result: [1, 2, 3, 4].

Let's also trace Example 2: arr = [1, 1, 2, 3, 4, 5], k = 4, x = -1:

Step 1: left=0, right=5. Need to remove 6-4 = 2 elements.

Step 2: Compare: |arr[0]-(-1)| = |1+1| = 2, |arr[5]-(-1)| = |5+1| = 6.

6 > 2, so remove arr[5]=5. right=4.

Step 3: Compare: |arr[0]-(-1)| = 2, |arr[4]-(-1)| = |4+1| = 5.

5 > 2, so remove arr[4]=4. right=3.

Step 4: Window is [1, 1, 2, 3], size = 4 = k. Done!

Result: [1, 1, 2, 3].

Two Pointers Shrinking — Trimming the Farthest Element — Watch how we start with the full array and repeatedly remove the boundary element farthest from x until exactly k elements remain.

Algorithm

Initialize left = 0 and right = arr.length - 1
While right - left + 1 > k (window is larger than needed):
- If |arr[left] - x| > |arr[right] - x|: move left forward (left element is farther)
- Otherwise: move right backward (right element is farther, or equidistant — prefer smaller)
Return arr[left..right] (the remaining k elements)

Code

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int left = 0;
        int right = arr.size() - 1;
        
        while (right - left + 1 > k) {
            if (abs(arr[left] - x) > abs(arr[right] - x)) {
                left++;
            } else {
                right--;
            }
        }
        
        return vector<int>(arr.begin() + left, arr.begin() + right + 1);
    }
};

class Solution:
    def findClosestElements(self, arr: list[int], k: int, x: int) -> list[int]:
        left = 0
        right = len(arr) - 1
        
        while right - left + 1 > k:
            if abs(arr[left] - x) > abs(arr[right] - x):
                left += 1
            else:
                right -= 1
        
        return arr[left:right + 1]

import java.util.*;

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0;
        int right = arr.length - 1;
        
        while (right - left + 1 > k) {
            if (Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) {
                left++;
            } else {
                right--;
            }
        }
        
        List<Integer> result = new ArrayList<>();
        for (int i = left; i <= right; i++) {
            result.add(arr[i]);
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n - k)

We perform exactly n - k comparisons and pointer movements, one per iteration of the while loop. Each iteration removes one element from consideration. This is linear in the number of elements we need to discard.

Space Complexity: O(k)

We need O(k) space for the output array. The algorithm itself uses O(1) extra space (just two pointers).

Why This Approach Is Not Efficient

The two-pointer shrinking approach runs in O(n - k) time. When k is small relative to n, this is essentially O(n) — we still touch nearly every element.

But we have a sorted array, which screams binary search. The k closest elements form a contiguous window of size k. Instead of linearly removing elements one by one, we can binary search for the optimal starting position of this window in O(log n) time.

The key insight: if we're choosing between window starting at index mid vs starting at mid + 1, we compare x - arr[mid] with arr[mid + k] - x. If x - arr[mid] is larger, the window starting at mid includes an element too far to the left, so we move right. This binary search finds the perfect left boundary in O(log(n - k)) time.

Optimal Approach - Binary Search for Window Start

Intuition

We know the answer is a contiguous window of exactly k elements. The starting index of this window can range from 0 to n-k. We need to find the best starting index.

Consider a candidate starting index mid. The window would be arr[mid], arr[mid+1], ..., arr[mid+k-1]. The element just outside the right end is arr[mid+k]. We compare the distance from x to the left boundary (arr[mid]) vs the distance to the element just beyond the right boundary (arr[mid+k]):

If x - arr[mid] > arr[mid + k] - x: the left boundary is farther from x than the element that would replace it on the right. We should shift the window rightward — move left to mid + 1.
Otherwise: the window is fine where it is, or should shift leftward — move right to mid.

This binary search converges to the optimal starting position in O(log(n-k)) time.

Think of it like finding the best seat at a long dinner table. You want to sit closest to a friend at position x. Instead of checking every seat, you jump to the middle, see if the seats to the left or right are closer to your friend, and halve your search space each time.

Step-by-Step Explanation

Let's trace through with arr = [1, 2, 3, 4, 5], k = 4, x = 3:

Step 1: The window has size k=4. Possible starting indices: 0 to 5-4 = 1.

Binary search range: left=0, right=1.

Step 2: mid = (0 + 1) / 2 = 0.

Window starting at 0: [1, 2, 3, 4]. Right boundary element: arr[0+4] = arr[4] = 5.
Compare: x - arr[mid] = 3 - 1 = 2. arr[mid+k] - x = 5 - 3 = 2.
Is 2 > 2? No. So the current position is acceptable — set right = mid = 0.

Step 3: left=0, right=0. left == right, search done. Starting index = 0.

Result: arr[0..3] = [1, 2, 3, 4].

Let's also trace with arr = [1, 1, 2, 3, 4, 5], k = 4, x = -1:

Step 1: Possible starting indices: 0 to 6-4 = 2.

Binary search range: left=0, right=2.

Step 2: mid = (0 + 2) / 2 = 1.

Window starting at 1: [1, 2, 3, 4]. Right boundary: arr[1+4] = arr[5] = 5.
Compare: x - arr[mid] = -1 - 1 = -2. Since x < arr[mid], use arr[mid] - x = 1 - (-1) = 2.
Actually, the comparison is: x - arr[mid] = -1 - 1 = -2. arr[mid+k] - x = 5 - (-1) = 6.
Is -2 > 6? No. Set right = mid = 1.

Step 3: left=0, right=1. mid = (0 + 1) / 2 = 0.

Window starting at 0: [1, 1, 2, 3]. Right boundary: arr[0+4] = arr[4] = 4.
Compare: x - arr[mid] = -1 - 1 = -2. arr[mid+k] - x = 4 - (-1) = 5.
Is -2 > 5? No. Set right = mid = 0.

Step 4: left=0, right=0. Done. Starting index = 0.

Result: arr[0..3] = [1, 1, 2, 3].

Binary Search for Optimal Window Start Position — Watch how binary search narrows down the best starting index for the k-element window by comparing boundary distances at each midpoint.

Algorithm

Set left = 0 and right = n - k (range of possible starting indices)
While left < right:
- Compute mid = (left + right) / 2
- If x - arr[mid] > arr[mid + k] - x:
  - The left boundary of the window at mid is farther from x than the element just beyond the right boundary. Shift window right: left = mid + 1
- Else:
  - The window is acceptable at mid (or should move left): right = mid
Return arr[left..left+k-1]

Code

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int left = 0;
        int right = arr.size() - k;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (x - arr[mid] > arr[mid + k] - x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return vector<int>(arr.begin() + left, arr.begin() + left + k);
    }
};

class Solution:
    def findClosestElements(self, arr: list[int], k: int, x: int) -> list[int]:
        left = 0
        right = len(arr) - k
        
        while left < right:
            mid = (left + right) // 2
            
            if x - arr[mid] > arr[mid + k] - x:
                left = mid + 1
            else:
                right = mid
        
        return arr[left:left + k]

import java.util.*;

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0;
        int right = arr.length - k;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (x - arr[mid] > arr[mid + k] - x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        List<Integer> result = new ArrayList<>();
        for (int i = left; i < left + k; i++) {
            result.add(arr[i]);
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(log(n - k) + k)

The binary search runs over a range of size n - k, so it takes O(log(n - k)) iterations. Each iteration does O(1) work (just comparing two array elements). After finding the starting index, we copy k elements to the result in O(k). Total: O(log(n - k) + k).

When k is much smaller than n, this is significantly faster than the O(n) two-pointer approach. For example, with n=10,000 and k=5, the binary search takes about 14 steps instead of 9,995 comparisons.

Space Complexity: O(k)

We only need O(k) space for the output array. The binary search itself uses O(1) extra space (just three integer variables: left, right, mid).

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Find K Closest Elements

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Two Pointers Shrinking

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Binary Search for Window Start

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis