Find K Closest Elements solution and explanation
Google
Infosys
9 more videos on this problem
Find K Closest Elements - Leetcode 658 - PythonNeetCode · 18:21 · 116K views
Find K Closest Elements | LeetCode 658 | Coders CampCoders Camp · 10:40 · 12K views
658. Find k closest elements | Leetcode | Medium | Java | Binary Search | Two PointersAlgorithmHQ · 11:42 · 6K views
Coding Interview: Find K Closest ElementsJames Cutajar · 19:14 · 5K views
[Java] Leetcode 658. Find K Closest Elements [Binary Search #8]Eric Programming · 15:06 · 5K views
LeetCode 658. Find K Closest ElementsHappy Coding · 10:09 · 4K views
Leetcode 658: Find K Closest Elements | Binary Search | Intuition and ApproachCode Concepts with Animesh · 33:27 · 2K views
LeetCode 658. Find K Closest Elements | JSer - JavaScript & AlgorithmJSer · 18:44 · 1K views
Coding Interview Problem - Find K Closest ElementsKnapsack · 7:18 · 1K views
LeetCode 658: Find K Closest Elements: Python MediumHashem Alsaket · 6:29 · 1K views
The 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|anda < 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.length1 <= arr.length <= 104arris sorted in ascending order.-104 <= arr[i], x <= 104
Approach overview
Problem Overview: Given a sorted array arr, an integer k, and a target x, return the k elements closest to x. If two numbers are equally close, the smaller value is preferred. The result must also remain sorted.
Approach 1: Two Pointers Shrinking Window (O(n) time, O(1) space)
This method keeps a window covering the entire array and repeatedly removes the element that is farther from x. Start with two pointers: left = 0 and right = n - 1. While the window size is larger than k, compare |arr[left] - x| and |arr[right] - x|. Remove the element with the larger distance by moving the corresponding pointer inward. Because the array is already sorted, the remaining window of size k is guaranteed to contain the closest elements. This approach uses the Two Pointers technique and works well when simplicity matters more than optimal logarithmic performance.
Approach 2: Binary Search with Sliding Window (O(log(n-k)) + O(k) time, O(1) space)
The array is sorted, which allows you to binary search the starting index of the optimal window of size k. Instead of searching for a single element, search the range [0, n-k]. For a candidate start mid, compare x - arr[mid] with arr[mid + k] - x. If the left side is larger, the window should move right; otherwise it should stay left. This works because the relative distances determine which side of the window is farther from x. After binary search finishes, the subarray arr[left : left + k] contains the answer. The window behaves like a fixed-size Sliding Window while binary search narrows the correct position using the properties of a sorted Binary Search space.
Recommended for interviews: Binary Search with Sliding Window is the expected optimal solution. It reduces the search space to log(n-k) comparisons and avoids scanning the whole array. Interviewers often accept the two-pointer shrinking approach first because it shows understanding of distance comparison, but the binary search optimization demonstrates stronger algorithmic reasoning on sorted arrays.
Approach 1: Binary Search with Sliding Window
This approach uses binary search to find the position where x would fit in the array or where it is located. From this point, a sliding window is expanded to the left and right to check k closest elements. Given the sorted nature of the array, this is efficient.
def find_closest_elements(arr, k, x):
left, right = 0, 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, right = arr.length - k;
while (left < right) {
int mid = (left + right) / 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;
}
}#include <vector>
#include <algorithm>
using namespace std;
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int left = 0, right = arr.size() - k;
while (left < right) {
int mid = (left + right) / 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);
}function findClosestElements(arr, k, x) {
let left = 0, right = arr.length - k;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (x - arr[mid] > arr[mid + k] - x)
left = mid + 1;
else
right = mid;
}
return arr.slice(left, left + k);
}#include <stdlib.h>
void merge(int* arr, int* aux, int left, int mid, int right) {
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) {
if (abs(arr[i]) <= abs(arr[j]))
aux[k++] = arr[i++];
else
aux[k++] = arr[j++];
}
while (i <= mid) aux[k++] = arr[i++];
while (j <= right) aux[k++] = arr[j++];
for (i = left; i <= right; i++) arr[i] = aux[i];
}
void mergesort(int* arr, int* aux, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergesort(arr, aux, left, mid);
mergesort(arr, aux, mid + 1, right);
merge(arr, aux, left, mid, right);
}
}
int* findKClosestElements(int* arr, int arrSize, int k, int x, int* returnSize) {
int *aux = (int*)malloc(arrSize * sizeof(int));
for (int i = 0; i < arrSize; ++i)
arr[i] -= x;
mergesort(arr, aux, 0, arrSize - 1);
for (int i = 0; i < arrSize; ++i)
arr[i] += x;
*returnSize = k;
free(aux);
return arr;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> FindClosestElements(int[] arr, int k, int x) {
int left = 0, right = arr.Length - k;
while (left < right) {
int mid = (left + right) / 2;
if (x - arr[mid] > arr[mid + k] - x)
left = mid + 1;
else
right = mid;
}
List<int> result = new List<int>();
for (int i = left; i < left + k; ++i) {
result.Add(arr[i]);
}
return result;
}
}We initiate a binary search between 0 and len(arr) - k. Depending on whether the element x is closer to the left or right side, we move the binary search mid-point. Once the position is found, the array is sliced from left to left + k to get the result.
Time Complexity: O(log(n-k) + k) where n is the length of the array, and we are moving a window over it. Space Complexity: O(k) for storing the resulting subarray.
Approach 2: Two Pointers
This approach initiates two pointers from the start and end of the array and gradually closes inwards by comparing the distance from x from both ends until the closest k elements are left. This is linear after the search initialization.
def find_closest_elements(arr, k, x):
left, right = 0, len(arr) - 1
while right - left >= 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, right = arr.length - 1;
while (right - left >= 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;
}
}#include <vector>
#include <cstdlib> // for abs
using namespace std;
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int left = 0, right = arr.size() - 1;
while (right - left >= k) {
if (abs(arr[left] - x) > abs(arr[right] - x))
left++;
else
right--;
}
return vector<int>(arr.begin() + left, arr.begin() + right + 1);
}function findClosestElements(arr, k, x) {
let left = 0, right = arr.length - 1;
while (right - left >= k) {
if (Math.abs(arr[left] - x) > Math.abs(arr[right] - x))
left++;
else
right--;
}
return arr.slice(left, right + 1);
}#include <stdlib.h>
int cmp(const void *a, const void *b) {
return abs(*(int*)a - x) - abs(*(int*)b - x);
}
int* findClosestElements(int* arr, int arrSize, int k, int x, int* returnSize) {
qsort(arr, arrSize, sizeof(int), cmp);
qsort(arr, k, sizeof(int), cmp);
*returnSize = k;
return arr;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> FindClosestElements(int[] arr, int k, int x) {
int left = 0, right = arr.Length - 1;
while (right - left >= k) {
if (Math.Abs(arr[left] - x) > Math.Abs(arr[right] - x))
left++;
else
right--;
}
List<int> result = new List<int>();
for (int i = left; i <= right; ++i)
result.Add(arr[i]);
return result;
}
}Using two pointers from both ends of the array, we check which value is closer to x and move the respective pointer inwards until only k elements are left. These k elements will be the closest to x.
Time Complexity: O(n). Space Complexity: O(k).
Approach 3: Sort
function findClosestElements(arr: number[], k: number, x: number): number[] {
let l = 0;
let r = arr.length;
while (r - l > k) {
if (x - arr[l] <= arr[r - 1] - x) {
--r;
} else {
++l;
}
}
return arr.slice(l, r);
}func findClosestElements(arr []int, k int, x int) []int {
sort.Slice(arr, func(i, j int) bool {
v := abs(arr[i]-x) - abs(arr[j]-x)
if v == 0 {
return arr[i] < arr[j]
}
return v < 0
})
ans := arr[:k]
sort.Ints(ans)
return ans
}
func abs(x int) int {
if x >= 0 {
return x
}
return -x
}impl Solution {
pub fn find_closest_elements(arr: Vec<i32>, k: i32, x: i32) -> Vec<i32> {
let n = arr.len();
let mut l = 0;
let mut r = n;
while r - l != (k as usize) {
if x - arr[l] <= arr[r - 1] - x {
r -= 1;
} else {
l += 1;
}
}
arr[l..r].to_vec()
}
}Approach 4: Binary search
function findClosestElements(arr: number[], k: number, x: number): number[] {
let left = 0;
let right = arr.length - k;
while (left < right) {
const mid = (left + right) >> 1;
if (x - arr[mid] <= arr[mid + k] - x) {
right = mid;
} else {
left = mid + 1;
}
}
return arr.slice(left, left + k);
}func findClosestElements(arr []int, k int, x int) []int {
l, r := 0, len(arr)
for r-l > k {
if x-arr[l] <= arr[r-1]-x {
r--
} else {
l++
}
}
return arr[l:r]
}impl Solution {
pub fn find_closest_elements(arr: Vec<i32>, k: i32, x: i32) -> Vec<i32> {
let k = k as usize;
let n = arr.len();
let mut left = 0;
let mut right = n - k;
while left < right {
let mid = left + (right - left) / 2;
if x - arr[mid] > arr[mid + k] - x {
left = mid + 1;
} else {
right = mid;
}
}
arr[left..left + k].to_vec()
}
}Approach 5: Default Approach
func findClosestElements(arr []int, k int, x int) []int {
left, right := 0, len(arr)-k
for 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]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search with Sliding Window | Time Complexity: O(log(n-k) + k) where n is the length of the array, and we are moving a window over it. Space Complexity: O(k) for storing the resulting subarray. |
| Two Pointers | Time Complexity: O(n). Space Complexity: O(k). |
| Sort | – |
| Binary search | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers Shrinking Window | O(n) | O(1) | When the array is sorted and you want a straightforward implementation without binary search |
| Binary Search + Sliding Window | O(log(n-k)) + O(k) | O(1) | Best choice for large arrays where you want the optimal logarithmic search |
Frequently asked questions
Is Find K Closest Elements easy or hard?
Find K Closest Elements is considered a Medium difficulty problem. The two-pointer approach is relatively straightforward, but identifying the binary search window optimization requires stronger understanding of sorted array properties.
Find K Closest Elements Python or Java solution?
The logic is identical across languages. Implement binary search to find the left boundary of the window, then return the next k elements. Python typically slices the array, while Java and C++ return a sublist or iterate to build the result.
How to solve Find K Closest Elements in O(log n)?
Use binary search to find the starting index of the k-length window that minimizes the distance to x. Search between indices 0 and n-k and compare x - arr[mid] with arr[mid + k] - x to decide which direction to move. After the search, return the subarray from start to start + k.
What is the best approach for Find K Closest Elements?
Binary Search with a fixed-size sliding window is the most efficient approach. Instead of checking every element, it binary searches the starting index of a window of size k in the sorted array. The algorithm runs in O(log(n-k)) time plus O(k) to return the result, making it faster than scanning the entire array.
What data structure is used in Find K Closest Elements?
The core solutions rely mainly on arrays combined with algorithmic techniques like binary search and two pointers. Some alternative implementations also use a heap (priority queue) to track closest elements, but the optimal interview solution avoids extra data structures.
What is the time complexity of Find K Closest Elements?
The optimal solution runs in O(log(n-k)) time using binary search to locate the best window of size k. Returning the k elements adds O(k) time. A simpler two-pointer shrinking window approach runs in O(n) time because it repeatedly removes elements from the edges.
Is Find K Closest Elements asked at Google, Amazon, or Meta?
Find K Closest Elements frequently appears in coding interviews at large tech companies including Amazon, Google, and Meta. The problem tests understanding of binary search on answer space, sliding window reasoning, and handling edge cases in sorted arrays.