Tag: sliding windows

658. Find K Closest Elements – Solution

Question

Difficulty: medium
Topics: Array, Two Pointers, Binary Search, Sliding Window

Given a sorted integer array 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 < b

Example 1:Input: arr = [1,2,3,4,5], k = 4, x = 3 Output: [1,2,3,4]

Example 2:Input: arr = [1,2,3,4,5], k = 4, x = -1 Output: [1,2,3,4]

Solution

This was a question that I struggled a lot. It was harder than usual binary search problems. There are many ways to think for this problem.

Solution 1: O(N⋅log(N)+k⋅log(k))

compute the distances between the elements and x, sort it and display the first k elements. When displaying it, sort again.

Solution 2: O(log(N)+k) – Bin. Search + 2 Pointers

Search the index of element closest to x. Then, start l and r pointers from there and expand them based on the smallest distance.

Solution 3: O(log(N−k)) – Find the left bound.

Search the left bound with binary search. Let l = 0 and r = N-k which is the maximum index that a left bound can be.

compute the mid point. Now, assuming the mid is the left bound, mid+k is the right bound. Then,

If value at mid is closer to x:

  • mid and further cannot be the left bound because then the right bound would be more distant from x than mid.

But, since there can be an even better left bound in the left side, we continue the bin search with the left side.

so we do r = mid;

If value at mid+k is closer to x:

  • index at mid or lower can’t be left bound. The left bound is somewhere between mid+1 ~ mid+k

so we do l = mid+1;

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int l = 0, r = arr.size() - k;
        while (l < r){
            int mid = (l+r)/2;
            if (x - arr[mid] > arr[mid+k] - x){
                l = mid + 1;
            }
            else{
                r = mid;
            }
        }
        return vector<int>(arr.begin() + l, arr.begin() + l + k);
    }
};

There is another way of seeing this: (from lee215’s solution post)

We compare the distance between x - A[mid] and A[mid + k] - x
If we assume A[mid] ~ A[mid + k] is sliding window

case 1: x – A[mid] < A[mid + k] – x, need to move window go left
——-x—-A[mid]—————–A[mid + k]———-

case 2: x – A[mid] < A[mid + k] – x, need to move window go left again
——-A[mid]—-x—————–A[mid + k]———-

case 3: x – A[mid] > A[mid + k] – x, need to move window go right
——-A[mid]——————x—A[mid + k]———-

case 4: x – A[mid] > A[mid + k] – x, need to move window go right
——-A[mid]———————A[mid + k]—-x——

Reflection

I think whenever using binary search, I should think about based on what criteria I will choose the left side or the right side given a mid point. This was particularly harder because I didn’t think of finding the left bound. Let’s remember that when finding a range, I can try to find only left or right bound.