Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 658 with 18 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 658 # by problem number
lcpy gen -s find_k_closest_elements # by problem name
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 < bInput: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]
Input: arr = [1,1,2,3,4,5], k = 4, x = -1
Output: [1,1,2,3]
1 <= k <= arr.length1 <= arr.length <= 10^4arr is sorted in ascending order.-10^4 <= arr[i], x <= 10^4class Solution:
# Time: O(log(n-k))
# Space: O(1)
def find_closest_elements(self, arr: list[int], k: int, x: int) -> list[int]:
"""
Find k closest elements to x using binary search on window positions.
Time: O(log(n-k)) - Binary search on n-k possible window positions
Space: O(1) - Only using constant extra variables
Algorithm:
- Search space: all possible left boundaries for k-element window [0, n-k]
- For each position mid, compare window boundaries: arr[mid] vs arr[mid+k]
- If arr[mid] farther from x, move search right; otherwise move left
- Leverages sorted array property for O(log) efficiency vs O(n) linear scan
Example: arr=[0,1,2,3,4], k=3, x=3
Windows: [0,1,2], [1,2,3], [2,3,4]
Distances: max(2,1), max(0,1), max(1,1) → choose [1,2,3]
"""
# Binary search to find the left boundary of the k-element window
left, right = 0, len(arr) - k
while left < right:
mid = (left + right) // 2
# Compare distances: arr[mid] vs arr[mid + k]
# If arr[mid] is farther from x than arr[mid + k], move left boundary right
if x - arr[mid] > arr[mid + k] - x:
left = mid + 1
else:
right = mid
return arr[left : left + k]
| Time | Space |
|---|---|
| O(log(n-k)) | O(1) |