Find K Closest Elements

Problem

Given a sorted array and integer x, return the k closest elements to x as a sorted list.

Constraints

• 1 ≤ k ≤ arr.length ≤ 10⁴

Approach — Two Pointers

This is a Two Pointers problem. The idea: walk two indices through the data together (or toward each other), turning an O(n²) pair search into one linear pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(1) extra space.

Solution code

Python

class Solution:
    def findClosestElements(self, arr, k, x):
        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

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        // Binary-search the LEFT endpoint of the answer window [left, left + k).
        // Range of valid lefts: [0, arr.length - k].
        int left = 0;
        int right = arr.length - k;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // Compare the candidate window [mid, mid + k) vs (mid, mid + k]:
            // if x is closer to the right edge, shift the window right.
            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;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.