Course4all
Join us on telegram
Home/dsa/Binary Search/Find K Closest Elements

Find K Closest Elements

Master this topic with zero to advance depth.

Find K Closest Elements

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.

Examples

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

Level I: Brute Force (Sort by Distance)

Intuition

Calculate the absolute difference of each element from xx. Sort the array based on these distances. In case of a tie, the smaller element comes first. Return the first kk elements.

⏱ $O(N \\log N)$💾 $O(N)$

Detailed Dry Run

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

  • Distances: [2, 1, 0, 1, 2]
  • Sorted by (dist, val): [(0,3), (1,2), (1,4), (2,1), (2,5)]
  • Take k=4: [3, 2, 4, 1]
  • Sort Result: [1, 2, 3, 4].
java
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> list = new ArrayList<>();
        for (int n : arr) list.add(n);
        Collections.sort(list, (a, b) -> {
            int d1 = Math.abs(a - x);
            int d2 = Math.abs(b - x);
            if (d1 == d2) return a - b;
            return d1 - d2;
        });
        List<Integer> res = list.subList(0, k);
        Collections.sort(res);
        return res;
    }
}
Approach 2

Level II: Binary Search + Two Pointers

Intuition

Use binary search to find the position closest to xx. Then expand outwards using two pointers to find the kk closest elements.

⏱ $O(\\log N + K)$💾 $O(K)$

Detailed Dry Run

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

  1. BS for 3: index 2.
  2. L=1, R=3. Compare arr[1]=2 and arr[3]=4.
  3. Keep expanding until k=4 is reached.
java
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int n = arr.length;
        int l = 0, r = n - 1;
        int pos = 0;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] <= x) {
                pos = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        l = pos; r = pos + 1;
        while (r - l - 1 < k) {
            if (l < 0) r++;
            else if (r >= n) l--;
            else if (Math.abs(arr[l] - x) <= Math.abs(arr[r] - x)) l--;
            else r++;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = l + 1; i < r; i++) res.add(arr[i]);
        return res;
    }
}
Approach 3

Level III: Optimal (Binary Search on Window Start)

Intuition

We want a contiguous window of k elements from the sorted array. Binary search for the LEFT endpoint of that window. For a candidate window starting at mid, compare if x - arr[mid] (distance to left edge) is greater than arr[mid+k] - x (distance to right edge). If left edge is farther, shift window right.

⏱ O(log(N-K)) — binary search on start index.💾 O(1) extra — the result itself is O(K).

Detailed Dry Run

Input: arr=[1,2,3,4,5], k=4, x=3 | Step | l | r | mid | arr[mid] | arr[mid+k] | dist left | dist right | Decision | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | 1 | 0 | 1 | 0 | 1 | 5 | 3-1=2 | 5-3=2 | Equal, go left: r=0 | | l==r==0 → window=[arr[0]..arr[3]]=[1,2,3,4]** |

java
import java.util.*;

public class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int l = 0, r = arr.length - k; // r is the max valid start index
        while (l < r) {
            int mid = l + (r - l) / 2;
            // Compare distances of left and right edges of the window
            if (x - arr[mid] > arr[mid + k] - x) l = mid + 1; // left too far, shift right
            else r = mid;                                        // right too far or equal, shift left
        }
        List<Integer> res = new ArrayList<>();
        for (int i = l; i < l + k; i++) res.add(arr[i]);
        return res;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.findClosestElements(new int[]{1,2,3,4,5}, 4, 3)); // [1,2,3,4]
        System.out.println(sol.findClosestElements(new int[]{1,2,3,4,5}, 4, -1)); // [1,2,3,4]
    }
}

⚠️ Common Pitfalls & Tips

The search bounds are [0, N-K] (not [0, N-1]). The tie-breaking rule is: when x - arr[mid] == arr[mid+k] - x, prefer the smaller element (i.e., r = mid, not l = mid+1).

← Previous QuestionSingle Element in a Sorted Array
Next Question →Capacity To Ship Packages Within D Days