658. Find K Closest Elements

Array Two Pointers Binary Search Sorting Heap (Priority Queue)

Intuition

Binary search for the starting position of the window of size k. The optimal window starts where arr[mid] is closer to x than arr[mid+k].

Algorithm

1Binary search: lo=0, hi=len-k.
2While lo < hi: mid = (lo+hi)/2. If x-arr[mid] > arr[mid+k]-x: lo=mid+1. Else hi=mid.
3Return arr[lo..lo+k].

Common Pitfalls

•Comparison: prefer arr[mid+k]-x over x-arr[mid] when equal (left-biased window). Hi = len-k, not len-1.

658.cs

// Approach: Binary search for the left boundary of the optimal k-element
// window; compare distances x-arr[m] vs arr[m+k]-x symmetrically.
// Time: O(log(n-k)+k) Space: O(1)

public class Solution
{
    public IList<int> FindClosestElements(int[] arr, int k, int x)
    {
        int l = 0;
        int r = arr.Length - k;

        while (l < r)
        {
            int m = (l + r) / 2;
            if (x - arr[m] <= arr[m + k] - x)
                r = m;
            else
                l = m + 1;
        }

        return arr.Skip(l).Take(k).ToList();
    }
}

Was this solution helpful?