658. Find K Closest Elements - Explanation

Description

You are 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

Example 1:

Input: arr = [2,4,5,8], k = 2, x = 6

Output: [4,5]

Example 2:

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

Output: [2,3,4]

Constraints:

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

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Sorting (Custom Comparator)

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        arr.sort(key=lambda num: (abs(num - x), num))
        return sorted(arr[:k])

Time & Space Complexity

Time complexity: $O(n \log n + k \log k)$
Space complexity:
- $O(1)$ or $O(n)$ space depending on the sorting algorithm.
- $O(k)$ space for the output array.

Where $n$ is the size of the input array and $k$ is the number of closest elements to find.

2. Linear Scan + Two Pointers

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        n = len(arr)
        idx = 0
        for i in range(1, n):
            if abs(x - arr[idx]) > abs(x - arr[i]):
                idx = i

        res = [arr[idx]]
        l, r = idx - 1, idx + 1

        while len(res) < k:
            if l >= 0 and r < n:
                if abs(x - arr[l]) <= abs(x - arr[r]):
                    res.append(arr[l])
                    l -= 1
                else:
                    res.append(arr[r])
                    r += 1
            elif l >= 0:
                res.append(arr[l])
                l -= 1
            elif r < n:
                res.append(arr[r])
                r += 1

        return sorted(res)

Time & Space Complexity

Time complexity: $O(n + k \log k)$
Space complexity:
- $O(1)$ or $O(k)$ space depending on the sorting algorithm.
- $O(k)$ space for the output array.

Where $n$ is the size of the input array and $k$ is the number of closest elements to find.

3. Two Pointers

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        l, r = 0, len(arr) - 1
        while r - l >= k:
            if abs(x - arr[l]) <= abs(x - arr[r]):
                r -= 1
            else:
                l += 1

        return arr[l: r + 1]

Time & Space Complexity

Time complexity: $O(n - k)$
Space complexity: $O(k)$ for the output array.

Where $n$ is the size of the input array and $k$ is the number of closest elements to find.

4. Binary Search + Two Pointers

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        l, r = 0, len(arr) - 1
        while l < r:
            mid = (l + r) // 2
            if arr[mid] < x:
                l = mid + 1
            else:
                r = mid

        l, r = l - 1, l
        while r - l - 1 < k:
            if l < 0:
                r += 1
            elif r >= len(arr):
                l -= 1
            elif abs(arr[l] - x) <= abs(arr[r] - x):
                l -= 1
            else:
                r += 1

        return arr[l + 1:r]

Time & Space Complexity

Time complexity: $O(\log n + k)$
Space complexity: $O(k)$ for the output array.

Where $n$ is the size of the input array and $k$ is the number of closest elements to find.

5. Binary Search

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        l, r = 0, len(arr) - k
        while l < r:
            m = (l + r) // 2
            if x - arr[m] > arr[m + k] - x:
                l = m + 1
            else:
                r = m
        return arr[l:l + k]

Time & Space Complexity

Time complexity: $O(\log (n - k) + k)$
Space complexity: $O(k)$ for the output array.

Where $n$ is the size of the input array and $k$ is the number of closest elements to find.