⚡Flashcard Drill➔
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

  1. Start with the whole array as the window and shrink it until exactly k elements remain.
  2. Compare the two ends: if abs(arr[l] - x) <= abs(arr[r] - x), drop the right end; otherwise drop the left end.
  3. The <= implements the tie-break: equal distances prefer the smaller (left) value, so the right end is discarded.
  4. 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 x is 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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems