Find K Closest Elements

Medium
368.

Find K Closest Elements

Find K Closest Elements is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Meta interviews.

Given a sorted integer array arr, and two integers k and x, return the k elements closest to x, sorted ascending.

An element a is closer than b when |a - x| < |b - x|, or when the distances tie 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,2,3,4,5], k = 4, x = -1
Output
[1,2,3,4]

Example 3

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

Constraints

  • 1 <= k <= arr.length <= 40
  • 1 <= arr[i], x <= 10000
  • arr is sorted in ascending order.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
var findClosestElements = function(arr, k, x) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find K Closest Elements — Solution in Python, Java & C++

Find K Closest Elements solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find K Closest Elements is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Meta interviews.

Problem statement

Given a sorted integer array arr, and two integers k and x, return the k elements closest to x, sorted ascending.

An element a is closer than b when |a - x| < |b - x|, or when the distances tie 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,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]

Example 3

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

Constraints

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

Hints for Find K Closest Elements

  1. Hint 1

    The answer is a contiguous window of length k — the array is sorted, so the closest elements sit together.

  2. Hint 2

    Binary search for the window's left edge among 0 … n - k.

  3. Hint 3

    Compare x - arr[mid] with arr[mid + k] - x: if the left edge is further away, slide right.

How to solve Find K Closest Elements

The answer is a contiguous window of length k; binary search its left edge in 0 .. n - k by comparing the distance of the window's left end with the element just past its right end.

Approach

  1. Set lo = 0, hi = n - k.
  2. While lo < hi: mid = (lo + hi) / 2; if x - arr[mid] > arr[mid + k] - x, lo = mid + 1; else hi = mid.
  3. Return arr[lo : lo + k].

Why it works

Sliding the window right swaps arr[mid] for arr[mid + k], which is an improvement exactly when the left element is further from x (ties keep the smaller value). That predicate is monotone in mid, so binary search finds the optimal edge.

Complexity

  • Time — O(log(n - k) + k)
  • Space — O(k)

Pitfalls

  • Use > not >= so ties prefer the left window, matching the "smaller wins" rule.

Reference solution

Python

def findClosestElements(arr, k: int, x: int):
    lo, hi = 0, len(arr) - k
    while lo < hi:
        mid = (lo + hi) // 2
        if x - arr[mid] > arr[mid + k] - x:
            lo = mid + 1
        else:
            hi = mid
    return arr[lo:lo + k]

Java

public static int[] findClosestElements(int[] arr, int k, int x) {
    int lo = 0, hi = arr.length - k;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1;
        else hi = mid;
    }
    return Arrays.copyOfRange(arr, lo, lo + k);
}

C++

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

JavaScript

var findClosestElements = function(arr, k, x) {
    let lo = 0, hi = arr.length - k;
    while (lo < hi) {
        const mid = Math.floor((lo + hi) / 2);
        if (x - arr[mid] > arr[mid + k] - x) lo = mid + 1;
        else hi = mid;
    }
    return arr.slice(lo, lo + k);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms