DDSA Solutions

658. Find K Closest Elements

MediumView on LeetCode
ArrayTwo PointersBinary SearchSortingHeap (Priority Queue)

Problem Overview

Binary search for the starting position of the window of size k.

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

  1. 1Binary search: lo=0, hi=len-k.
  2. 2While lo < hi: mid = (lo+hi)/2. If x-arr[mid] > arr[mid+k]-x: lo=mid+1. Else hi=mid.
  3. 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
C#
// 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?

Related Problems