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

Example 1:

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

Example 2:

1
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 <= 104
  • arr is sorted in ascending order.
  • 104 <= arr[i], x <= 104

Solution:

We want to find a size k window that use x as middle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
case 1: x < (A[mid]+ A[mid + k])//2, need to move window go left
-------x----A[mid]---------|-------A[mid + k]----------

case 2: x < (A[mid] + A[mid + k])//2, need to move window go left again
-------A[mid]----x-----|--------A[mid + k]----------

case 3: x > (A[mid] + A[mid + k])//2, need to move window go right
-------A[mid]----------|-----x---A[mid + k]----------

case 4: x > (A[mid] + A[mid + k])//2, need to move window go right
-------A[mid]----------|---------A[mid + k]----x------

case 5: x == (A[mid] + A[mid + k])//2, find the window we want
-------A[mid]----------|---------A[mid + k]--------
											 x
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findClosestElements(self, nums: List[int], k: int, x: int) -> List[int]:
        left, right = 0, len(nums) - k
        
        while left < right:
            mid = (left + right) // 2
            if x > (nums[mid] + nums[mid + k]) / 2:
                left = mid + 1
            else:
                right = mid
                
        return nums[left: left + k]

time complexity: $O()$
space complexity: $O()$
reference:
related problem: