# Find K Closest Elements
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-k-closest-elements)
Canonical: https://scaleengineer.com/dsa/problems/find-k-closest-elements
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [DoorDash](https://scaleengineer.com/companies/doordash), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Yandex](https://scaleengineer.com/companies/yandex), [Coupang](https://scaleengineer.com/companies/coupang)
---
## Problem
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:**

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

**Output:** \[1,2,3,4\]

**Example 2:**

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

**Output:** \[1,1,2,3\]

**Constraints:**

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

# Approaches
## Sort with Custom Comparator
The most straightforward approach is to sort the entire array based on a custom rule. The rule is the distance of each element from `x`. If two elements have the same distance, the smaller element is considered closer. This method is easy to conceptualize but not the most performant.
**Time:** O(N log N) - The dominant operation is sorting the entire array of N elements. Sorting the final k elements takes an additional O(k log k), but this is overshadowed by O(N log N). · **Space:** O(N) - We need to create a list of Integer objects from the primitive `int` array, which requires space proportional to the number of elements N.
**Pros:** Simple to understand and implement using standard library functions.
**Cons:** Highly inefficient for large arrays as it sorts the entire array, even though we only need `k` elements.; Requires extra space to convert the primitive array to a list of objects.
### Explanation
This approach leverages Java's built-in sorting capabilities. We first convert the input array `arr` into a `List<Integer>` because the `Collections.sort` method works with lists and allows for custom comparators. The core of this method is the custom `Comparator`. It compares two numbers, `a` and `b`, based on their absolute difference from `x`. If `|a - x|` is not equal to `|b - x|`, the one with the smaller difference comes first. If the differences are equal, the problem states that the smaller number (`a < b`) should come first. After sorting the entire list with this logic, the `k` closest elements will be at the beginning of the list. We then take a sublist of the first `k` elements and sort it again in natural ascending order before returning it.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> list = new ArrayList<>();
        for (int num : arr) {
            list.add(num);
        }

        // Sort based on distance from x
        Collections.sort(list, (a, b) -> {
            int diffA = Math.abs(a - x);
            int diffB = Math.abs(b - x);
            if (diffA != diffB) {
                return diffA - diffB;
            } else {
                return a - b;
            }
        });

        // Take the first k elements
        List<Integer> result = new ArrayList<>(list.subList(0, k));

        // Sort the result in ascending order
        Collections.sort(result);

        return result;
    }
}
```
### Algorithm
*   1. Convert the `int[] arr` to a `List<Integer>` to use `Collections.sort`.
*   2. Sort the list using `Collections.sort` and a custom comparator.
*   3. The comparator `(a, b)` first compares `Math.abs(a - x)` with `Math.abs(b - x)`.
*   4. If the absolute differences are equal, it compares `a` and `b` to handle the tie-breaker (`a < b` is closer).
*   5. After sorting, the `k` closest elements are the first `k` elements in the list.
*   6. Create a new list containing these first `k` elements.
*   7. Sort this new list of `k` elements in ascending order, as the custom sort does not guarantee numerical order for elements with different distances.
*   8. Return the final sorted list.

## Using a Max Heap
A more optimized approach uses a max heap (implemented with a `PriorityQueue` in Java) to keep track of the `k` closest elements found so far. This avoids sorting the entire array. We iterate through the array, and for each element, we decide if it's closer to `x` than the farthest element currently in our set of `k` closest elements, which is always at the top of the max heap.
**Time:** O(N log k) - We iterate through N elements. For each element, we perform a heap operation (add/remove) which takes O(log k) time. Sorting the final result takes O(k log k). · **Space:** O(k) - The heap stores at most k+1 elements.
**Pros:** More efficient than sorting the whole array, especially when `k` is much smaller than `N`.; A standard pattern for solving "Top K" problems.
**Cons:** Slightly more complex to implement the comparator logic for the max heap compared to the simple sorting approach.; Still processes all N elements, which is less efficient than binary search-based methods.
### Explanation
This method is a classic solution for "Top K" problems. We maintain a max heap of size `k`. The heap is ordered based on the "closeness" criteria, but in reverse: the element at the top of the heap is the one that is *least* close among the `k` elements currently in the heap. 

As we iterate through the input array `arr`, we add each element to the heap. If the heap's size becomes `k + 1`, we remove the top element (`poll()`), effectively discarding the element that is farthest from `x`. After iterating through all `N` elements, the heap contains the `k` elements from the original array that are closest to `x`. Finally, we extract these elements from the heap and sort them in ascending order to meet the output requirement.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        // Max heap
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> {
            int diffA = Math.abs(a - x);
            int diffB = Math.abs(b - x);
            if (diffA != diffB) {
                return diffB - diffA; // Farthest distance has higher priority
            } else {
                return b - a; // Larger element has higher priority
            }
        });

        for (int num : arr) {
            maxHeap.offer(num);
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }

        List<Integer> result = new ArrayList<>(maxHeap);
        Collections.sort(result);
        return result;
    }
}
```
### Algorithm
*   1. Initialize a max `PriorityQueue` (max heap). The comparator should place the element "farthest" from `x` at the top.
*   2. The comparator `(a, b)` should first compare `|a - x|` with `|b - x|`. If they are different, the one with the larger distance has higher priority. If they are equal, the larger number `b` has higher priority.
*   3. Iterate through each element `num` in the input array `arr`.
*   4. Add `num` to the priority queue.
*   5. If the size of the priority queue exceeds `k`, remove the top element using `poll()`.
*   6. After the loop, the priority queue holds the `k` closest elements.
*   7. Convert the priority queue to a list and sort it in ascending order.
*   8. Return the sorted list.

## Binary Search with Two-Pointer Expansion
Since the input array is sorted, we can leverage binary search to quickly find the element closest to `x` or its insertion point. From this 'center' point, we can use two pointers, one moving left and one moving right, to expand our window and collect the `k` closest elements one by one.
**Time:** O(log N + k) - Binary search takes O(log N) to find the starting pointers (or a linear scan as in the code, which is O(N) in worst case, but can be replaced by `Arrays.binarySearch` for O(log N)). The two-pointer expansion takes O(k) time. · **Space:** O(k) - To store the resulting k elements in the deque.
**Pros:** Very efficient with O(log N + k) time complexity.; Avoids processing or sorting the entire array.; Combines two powerful techniques: binary search and two pointers.
**Cons:** The logic for handling pointers and boundary conditions can be tricky to implement correctly.; Involves multiple steps: binary search, then a loop with pointer manipulation.
### Explanation
This efficient approach takes full advantage of the sorted input array. First, we perform a binary search to locate the index of `x`, or if `x` is not present, the index where `x` would be inserted to maintain the sorted order. This gives us a starting point. We initialize two pointers, `left` and `right`, on either side of this starting point. 

Then, we iterate `k` times. In each iteration, we compare the elements pointed to by `left` and `right` to see which is closer to `x`. We add the closer element to our result and move the corresponding pointer inward (i.e., `left--` or `right++`). We must be careful to handle the edge cases where one of the pointers moves out of the array's bounds. In such a case, we simply take elements from the pointer that is still in bounds. By adding elements from the left to the front of a deque and elements from the right to the back, we can build the final sorted list directly.

```java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int n = arr.length;
        // Find the insertion point for x
        int right = 0;
        while(right < n && arr[right] < x) {
            right++;
        }
        int left = right - 1;

        LinkedList<Integer> result = new LinkedList<>();
        while (k-- > 0) {
            if (left < 0) {
                result.addLast(arr[right++]);
            } else if (right >= n) {
                result.addFirst(arr[left--]);
            } else if (x - arr[left] <= arr[right] - x) {
                result.addFirst(arr[left--]);
            } else {
                result.addLast(arr[right++]);
            }
        }
        return result;
    }
}
```
### Algorithm
*   1. Use binary search to find the index `right` of the first element that is greater than or equal to `x`. Let `left = right - 1`.
*   2. Initialize a result list, preferably a `LinkedList` or `ArrayDeque` for efficient additions at both ends.
*   3. Repeat `k` times to collect `k` elements:
*   4. Check for boundary conditions: If `left` is out of bounds (`< 0`), we must take from the right. If `right` is out of bounds (`>= arr.length`), we must take from the left.
*   5. If both pointers are valid, compare the distances: `x - arr[left]` vs `arr[right] - x`.
*   6. If the left element is closer or equidistant (`x - arr[left] <= arr[right] - x`), add `arr[left]` to the front of the result list and decrement `left`.
*   7. Otherwise, add `arr[right]` to the back of the result list and increment `right`.
*   8. After `k` iterations, the deque will contain the `k` closest elements in sorted order.
*   9. Convert the deque to a list and return it.

## Binary Search for the Start of the Result Window
This is arguably the most elegant and efficient approach. We observe that the `k` closest elements will always form a contiguous subarray of the sorted `arr`. Instead of finding the elements one by one, we can directly find the starting index of this `k`-element subarray using a single, clever binary search.
**Time:** O(log(N-k) + k) - The binary search is performed on a range of `N-k` possible indices, taking O(log(N-k)) time. Creating the final list from the subarray takes O(k) time. · **Space:** O(k) - Required to create the output list. The algorithm itself uses O(1) extra space.
**Pros:** The most efficient and concise solution.; Finds the result window directly without expanding one by one.; Guarantees an O(log(N-k)) search time.
**Cons:** The logic of the binary search condition, comparing `arr[mid]` and `arr[mid+k]`, can be non-obvious at first glance.
### Explanation
The core idea is to reframe the problem from finding `k` elements to finding the *single best starting index* for a window of size `k`. Since the result must be a contiguous block of `k` elements from the sorted array `arr`, we just need to find where that block begins. The possible starting indices range from `0` to `n-k`.

We can binary search over this range of possible start indices. For a given `mid` index, we consider the window `arr[mid...mid+k-1]`. To decide whether to move our search left or right, we check if we can form a *better* window by shifting it one position to the right. A better window would be `arr[mid+1...mid+k]`. This is equivalent to comparing the element we would drop, `arr[mid]`, with the element we would gain, `arr[mid+k]`. If `x` is closer to `arr[mid+k]` than `arr[mid]`, it means we should favor the right side, so we move our search space by setting `low = mid + 1`. Otherwise, the current window starting at `mid` is optimal or better than any to its right, so we set `high = mid`. The loop terminates when `low` and `high` converge to the single best starting index.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int low = 0;
        int high = arr.length - k;

        while (low < high) {
            int mid = low + (high - low) / 2;
            // If x is closer to arr[mid+k] than arr[mid],
            // it means our window is too far to the left.
            // We should move the window to the right.
            if (x - arr[mid] > arr[mid + k] - x) {
                low = mid + 1;
            } else {
                // Otherwise, the current window is better or equal,
                // so the optimal window can be at `mid` or to its left.
                high = mid;
            }
        }

        // The result is the subarray of size k starting at `low`
        List<Integer> result = new ArrayList<>(k);
        for (int i = 0; i < k; i++) {
            result.add(arr[low + i]);
        }
        return result;
    }
}
```
### Algorithm
*   1. The result will be a contiguous subarray of `arr` of length `k`. The goal is to find the optimal starting index of this subarray.
*   2. The search space for the starting index is `[0, arr.length - k]`.
*   3. Initialize two pointers, `low = 0` and `high = arr.length - k`.
*   4. Perform a binary search on this range of indices.
*   5. In each step, calculate `mid = low + (high - low) / 2`. This `mid` is a potential starting index.
*   6. Compare the element `x`'s distance to `arr[mid]` (the start of the window) and `arr[mid + k]` (the first element outside the window to the right).
*   7. If `x` is farther from `arr[mid]` than from `arr[mid + k]` (i.e., `x - arr[mid] > arr[mid + k] - x`), it means the optimal window is to the right. So, we shrink the search space to `[mid + 1, high]` by setting `low = mid + 1`.
*   8. Otherwise, the current window `arr[mid...mid+k-1]` is a better candidate than any window to its right. The optimal window could be at `mid` or to its left. So, we shrink the search space to `[low, mid]` by setting `high = mid`.
*   9. When the loop terminates (`low == high`), `low` is the optimal starting index.
*   10. Create and return a list of `k` elements from `arr` starting at index `low`.

# Solutions
### Java

```java
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 ) >> 1 ; if ( x - arr [ mid ] <= arr [ mid + k ] - x ) { right = mid ; } else { left = mid + 1 ; } } List < Integer > ans = new ArrayList <>(); for ( int i = left ; i < left + k ; ++ i ) { ans . add ( arr [ i ]); } return ans ; } }
```

### CPP

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

### Python

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