Find K Closest Elements

Med

#0612Time: 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.5 companies

Patterns

Sliding Window Two Pointers

Algorithms

Binary Search Sorting

Data structures

Array Heap (Priority Queue)

Companies

Atlassian DoorDash LinkedIn Yandex

Prompt

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 <= 10⁴
arr is sorted in ascending order.
-10⁴ <= arr[i], x <= 10⁴

Approaches

4 approaches with complexity analysis and trade-offs.

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.

Algorithm

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

Walkthrough

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.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public List<Integer> findClosestElements(int[] arr, int k, int x) {7        List<Integer> list = new ArrayList<>();8        for (int num : arr) {9            list.add(num);10        }11 12        // Sort based on distance from x13        Collections.sort(list, (a, b) -> {14            int diffA = Math.abs(a - x);15            int diffB = Math.abs(b - x);16            if (diffA != diffB) {17                return diffA - diffB;18            } else {19                return a - b;20            }21        });22 23        // Take the first k elements24        List<Integer> result = new ArrayList<>(list.subList(0, k));25 26        // Sort the result in ascending order27        Collections.sort(result);28 29        return result;30    }31}

Complexity

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.

Trade-offs

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.

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.

Algorithm

1. Initialize a max PriorityQueue (max heap). The comparator should place the element "farthest" from x at the top.
1. 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.
1. Iterate through each element num in the input array arr.
1. Add num to the priority queue.
1. If the size of the priority queue exceeds k, remove the top element using poll().
1. After the loop, the priority queue holds the k closest elements.
1. Convert the priority queue to a list and sort it in ascending order.
1. Return the sorted list.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4import java.util.PriorityQueue;5 6class Solution {7    public List<Integer> findClosestElements(int[] arr, int k, int x) {8        // Max heap9        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> {10            int diffA = Math.abs(a - x);11            int diffB = Math.abs(b - x);12            if (diffA != diffB) {13                return diffB - diffA; // Farthest distance has higher priority14            } else {15                return b - a; // Larger element has higher priority16            }17        });18 19        for (int num : arr) {20            maxHeap.offer(num);21            if (maxHeap.size() > k) {22                maxHeap.poll();23            }24        }25 26        List<Integer> result = new ArrayList<>(maxHeap);27        Collections.sort(result);28        return result;29    }30}

Complexity

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.

Trade-offs

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.

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.

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.
1. Initialize a result list, preferably a LinkedList or ArrayDeque for efficient additions at both ends.
1. Repeat k times to collect k elements:
1. 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.
1. If both pointers are valid, compare the distances: x - arr[left] vs arr[right] - x.
1. 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.
1. Otherwise, add arr[right] to the back of the result list and increment right.
1. After k iterations, the deque will contain the k closest elements in sorted order.
1. Convert the deque to a list and return it.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.LinkedList;3import java.util.List;4 5class Solution {6    public List<Integer> findClosestElements(int[] arr, int k, int x) {7        int n = arr.length;8        // Find the insertion point for x9        int right = 0;10        while(right < n && arr[right] < x) {11            right++;12        }13        int left = right - 1;14 15        LinkedList<Integer> result = new LinkedList<>();16        while (k-- > 0) {17            if (left < 0) {18                result.addLast(arr[right++]);19            } else if (right >= n) {20                result.addFirst(arr[left--]);21            } else if (x - arr[left] <= arr[right] - x) {22                result.addFirst(arr[left--]);23            } else {24                result.addLast(arr[right++]);25            }26        }27        return result;28    }29}

Complexity

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.

Trade-offs

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.

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.

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.
1. The search space for the starting index is [0, arr.length - k].
1. Initialize two pointers, low = 0 and high = arr.length - k.
1. Perform a binary search on this range of indices.
1. In each step, calculate mid = low + (high - low) / 2. This mid is a potential starting index.
1. 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).
1. 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.
1. 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.
1. When the loop terminates (low == high), low is the optimal starting index.
1. Create and return a list of k elements from arr starting at index low.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<Integer> findClosestElements(int[] arr, int k, int x) {6        int low = 0;7        int high = arr.length - k;8 9        while (low < high) {10            int mid = low + (high - low) / 2;11            // If x is closer to arr[mid+k] than arr[mid],12            // it means our window is too far to the left.13            // We should move the window to the right.14            if (x - arr[mid] > arr[mid + k] - x) {15                low = mid + 1;16            } else {17                // Otherwise, the current window is better or equal,18                // so the optimal window can be at `mid` or to its left.19                high = mid;20            }21        }22 23        // The result is the subarray of size k starting at `low`24        List<Integer> result = new ArrayList<>(k);25        for (int i = 0; i < k; i++) {26            result.add(arr[low + i]);27        }28        return result;29    }30}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class 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 ); } };

1class 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 ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class 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 ; } }

1class 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 ); } };

1class 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 ]

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.