658. Find K Closest Elements

Jump to Solution: Python Java C++ JavaScript C#

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:

|a - x| < |b - x|, or
|a - x| == |b - x| and a < b

Examples:

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]

Constraints:

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

Python Solution

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        # Binary search to find the starting point
        left, right = 0, len(arr) - k
        
        while left < right:
            mid = (left + right) // 2
            
            # Compare distance from x to arr[mid] and arr[mid+k]
            if x - arr[mid] > arr[mid + k] - x:
                left = mid + 1
            else:
                right = mid
        
        # Return k elements starting from left
        return arr[left:left + k]

Alternative Solution (Using Heap):

from heapq import heappush, heappop

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        # Max heap to store k closest elements
        heap = []
        
        for num in arr:
            # Calculate distance and use negative for max heap
            dist = abs(num - x)
            
            if len(heap) < k:
                heappush(heap, (-dist, -num))
            else:
                # If current element is closer than the farthest in heap
                if (-dist, -num) > heap[0]:
                    heappop(heap)
                    heappush(heap, (-dist, -num))
        
        # Extract numbers and sort them
        return sorted([-pair[1] for pair in heap])

Implementation Notes:

First solution uses binary search with O(log(n-k)) time
Second solution uses heap with O(nlogk) time
Binary search solution is more efficient for sorted input

Java Solution

class Solution {
    public List findClosestElements(int[] arr, int k, int x) {
        int left = 0;
        int 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;
            }
        }
        
        // Convert array segment to List
        List result = new ArrayList<>();
        for (int i = left; i < left + k; i++) {
            result.add(arr[i]);
        }
        
        return result;
    }
}

C++ Solution

class Solution {
public:
    vector findClosestElements(vector& arr, int k, int x) {
        int left = 0;
        int 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 k elements starting from left
        return vector(arr.begin() + left, arr.begin() + left + k);
    }
};

JavaScript Solution

/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
var findClosestElements = function(arr, k, x) {
    let left = 0;
    let 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 k elements starting from left
    return arr.slice(left, left + k);
};

C# Solution

public class Solution {
    public IList FindClosestElements(int[] arr, int k, int x) {
        int left = 0;
        int 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;
            }
        }
        
        // Return k elements starting from left
        return arr.Skip(left).Take(k).ToList();
    }
}

Alternative Solution (Using LINQ):

public class Solution {
    public IList FindClosestElements(int[] arr, int k, int x) {
        return arr.OrderBy(n => Math.Abs(n - x))
                 .ThenBy(n => n)
                 .Take(k)
                 .OrderBy(n => n)
                 .ToList();
    }
}

Implementation Notes:

First solution uses binary search for optimal performance
LINQ solution is more concise but less efficient
Both maintain the required sorting order