Find K Closest Elements

Problem Description

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:

• abs(a - x) < abs(b - x), or
• abs(a - x) == abs(b - x) and a < b.

Examples

Constraints

• 1 <= k <= arr.length
• 1 <= arr.length <= 10⁴
• arr is sorted in ascending order.
• -10⁴ <= arr[i], x <= 10⁴

Window Shrinking with Two Pointers

We need to select a contiguous subarray of size k from a sorted array of size n that minimizes the distance to x. Instead of finding the closest element and expanding outward, we can start with a window covering the entire array [0, n-1]. While the window size is larger than k, we compare the distance of the elements at the boundaries to x. If the element at left is farther from x than the element at right (or if distances are equal but the left element is larger), we discard the left element by incrementing left. Otherwise, we discard the right element by decrementing right. This shrinks the window to size k in linear time.

Solution 1: Two Pointers Window Shrinkage

Start with the full array and shrink boundaries until the window contains exactly k elements.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0;
        int right = arr.length - 1;

        // Shrink window until its size is k
        while (right - left >= k) {
            if (Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) {
                left++; // discard left element
            } else {
                right--; // discard right element
            }
        }

        List<Integer> result = new ArrayList<>();
        for (int i = left; i <= right; i++) {
            result.add(arr[i]);
        }
        return result;
    }
}

class Solution:
    def findClosestElements(self, arr: list[int], k: int, x: int) -> list[int]:
        left = 0
        right = len(arr) - 1
        
        # Shrink window until its size is k
        while right - left >= k:
            if abs(arr[left] - x) > abs(arr[right] - x):
                left += 1  # discard left element
            else:
                right -= 1  # discard right element
                
        return arr[left:right + 1]

#include <vector>
#include <cmath>
#include <algorithm>

class Solution {
public:
    std::vector<int> findClosestElements(std::vector<int>& arr, int k, int x) {
        int left = 0;
        int right = arr.size() - 1;

        // Shrink window until its size is k
        while (right - left >= k) {
            if (std::abs(arr[left] - x) > std::abs(arr[right] - x)) {
                left++;
            } else {
                right--;
            }
        }

        return std::vector<int>(arr.begin() + left, arr.begin() + right + 1);
    }
};

Complexity Analysis

• Time Complexity: O(n - k) to shrink the window, plus O(k) to copy elements, resulting in a total time of O(n).
• Space Complexity: O(1) auxiliary space (excluding the output list).

Where It Breaks

If n is extremely large (e.g. n > 10^7), running a linear scan from the outer boundaries takes too many steps. Under those conditions, running a binary search to find the starting index of the window of size k in O(log(n - k)) time is much faster.

Common Mistakes

• Incorrect distance comparison: Comparing absolute distances without checking the tie-breaker rule (a < b if distances are equal). In our check, left is only incremented if its distance is strictly greater than the right side’s distance. If they are equal, we choose the smaller value (at left) and decrement right.
• Off-by-one errors on slice bounds: Accessing elements past index right or copy boundaries.

Frequently Asked Questions

Can we solve this using binary search? Yes. You can binary search for the left boundary index of the result window. The search range is [0, n - k]. For each midpoint mid, compare x - arr[mid] with arr[mid + k] - x to decide which way to shift the search range. This takes O(log(n - k)) time.

Why does two-pointer shrinkage guarantee the closest elements? Because the array is sorted, elements farther from x must reside at the outer edges. By comparing the outer edges and discarding the one with the larger distance, we preserve the elements closest to x.

← All Problems