Skip to content

658. Find K Closest Elements

Array Two Pointers Binary Search Sliding Window Sorting Heap (Priority Queue)

Problem - Find K Closest Elements

Medium

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 = [1,2,3,4,5], k = 4, x = 3

Output: [1,2,3,4]

Example 2:

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

Output: [1,1,2,3]

 

Constraints:

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

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        # arr.sort(key=lambda val: abs(val - x))
        # return sorted(arr[:k])

        left, right = 0, len(arr) - k

        while right > left:
            mid = (left + right) // 2
            if x - arr[mid] <= arr[mid + k] -x:
                right = mid
            else:
                left = mid +1

        return arr[left: left + k]

Submission Stats:

  • Runtime: 0 ms (100.00%)
  • Memory: 19.1 MB (62.09%)