NeetCode #239LC-658MediumSliding WindowNC 250
← Back to All Problems#239 · #658 · Find K Closest Elements(找到 K 个最接近的元素)
📌 Problem Statement & Constraints
Given a sorted integer array
arr, an integer k and an integer x, return the k closest integers to x in ascending order. Ties are broken by preferring the smaller value. Constraints: 1 <= k <= arr.length <= 10^4, arr is sorted ascending.💡 Core Algorithmic Approaches
- Start with the whole array as the window and shrink it until exactly
kelements remain. - Compare the two ends: if
abs(arr[l] - x) <= abs(arr[r] - x), drop the right end; otherwise drop the left end. - The
<=implements the tie-break: equal distances prefer the smaller (left) value, so the right end is discarded. - The remaining window is sorted by construction, so no final sort is needed.
💻 Benchmark Python3 Implementation
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
l, r = 0, len(arr) - 1
while r - l + 1 > k: # shrink until exactly k remain
if abs(arr[l] - x) <= abs(arr[r] - x):
r -= 1 # tie-break prefers the smaller value
else:
l += 1
return arr[l:r + 1]
# Binary-search variant: find the window start directly, O(log n + k)
class Solution2:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
lo, hi = 0, len(arr) - k # the start of the window is in [lo, hi]
while lo < hi:
mid = (lo + hi) // 2
# compare dropping the left end vs dropping the right end
if x - arr[mid] > arr[mid + k] - x:
lo = mid + 1
else:
hi = mid
return arr[lo:lo + k]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n) for the shrinking version, O(log(n - k) + k) for the binary-search version.
💾 Space Complexity
O(k) for the returned slice.
⚠️ Interview Pitfalls & Follow-ups
- Using
<instead of<=for the tie-break: that would prefer the larger value, contradicting the problem statement. - Sorting by distance and then re-sorting the result: works, but O(n log n) and the window approach is simpler.
- Shrinking by more than one element per step: the window must lose exactly one element per iteration to stay correct.
- Assuming
xis inside the array range: it may be outside, and the window logic handles that naturally.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner