Hex.*

LC658 - Find K Closest Elements

Posted on In
Datastructure and Algorithm: DAY 86. Leetcode: 280/2736

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:

1
2
|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
2
3
4
1 <= k <= arr.length
1 <= arr.length <= 104
arr is sorted in ascending order.
-104 <= arr[i], x <= 104

Solutions

The answer must be a continuous window; numbers are excluded from the left and right ends of the window, leaving k numbers at the end

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# O(n) time | O(1) space
class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        n = len(arr)
        left, right = 0, n-1
        remaining = n - k
        ans = []
        
        for _ in range(remaining):
            if abs(arr[left] - x) > abs(arr[right] - x):
                left +=1
            else:
                right -=1
        
        for i in range(left, right+1):
            ans.append(arr[i])
        return ans