658. Find K Closest Elements - Detailed Explanation

Problem Statement

Description:
You are given a sorted integer array arr, and two integers k and x. Your task is to find the k closest integers to x in the array. The result should also be sorted in ascending order. An integer a is considered closer to x than an integer b if:

• |a - x| < |b - x|, or
• If |a - x| == |b - x|, then a < b.

It is guaranteed that the answer is unique. The k closest integers form a contiguous subarray of arr.

Examples:

1. Example 1:

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

   • Output: [1,2,3,4]

   • Explanation:

     The absolute differences with 3 are:
     |1-3|=2, |2-3|=1, |3-3|=0, |4-3|=1, |5-3|=2.
     The four numbers with the smallest differences are 1, 2, 3, and 4.
     Although [2,3,4,5] also has the same differences for 2, 3, 4, and 5, when the absolute differences are equal (for 1 and 5), the smaller value is preferred.

2. Example 2:

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

   • Output: [1,2,3,4]

   • Explanation:

     All elements are to the right of -1. The closest 4 elements are simply the first four numbers.

3. Example 3:

   • Input: arr = [1,2,3,4,5], k = 4, x = 6

   • Output: [2,3,4,5]

   • Explanation:

     The absolute differences are:
     |1-6|=5, |2-6|=4, |3-6|=3, |4-6|=2, |5-6|=1.
     The closest four are 2, 3, 4, and 5.

Constraints:

• 1 <= k <= arr.length

• 1 <= arr.length <= 10^4

• arr is sorted in ascending order.

• -10^4 <= arr[i], x <= 10^4

Hints

• Contiguous Subarray:
  The problem guarantees that the k closest numbers form a contiguous subarray. This observation allows you to consider sliding window or binary search techniques to find the correct window.

• Binary Search for the Window Start:
  Instead of checking every possible subarray, you can perform binary search over the possible starting indices (from 0 to arr.length - k). For a candidate starting index i, compare the distances between x and arr[i] versus x and arr[i+k] to decide whether to move the window left or right.

• Two-Pointer / Sliding Window:
  Alternatively, you can use two pointers to shrink the window until its size becomes k, always removing the element (from either the left or right) that is farther from x.

Multiple Approaches

Approach 1: Binary Search (Optimal)

Idea:
Since arr is sorted, the k closest elements form a contiguous subarray. We can binary search on the starting index of this subarray. Let left be the starting index and right be arr.length - k. For a given index mid in [left, right], compare the distance from x to arr[mid] with the distance from x to arr[mid+k]:

• If x - arr[mid] > arr[mid+k] - x, it means that the subarray starting at mid is too far left and we need to move right.
• Otherwise, move left.

Finally, the best starting index will yield the window of k elements that are closest to x.

Step-by-step:

1. Initialize left = 0 and right = arr.length - k.

2. While left < right:

   • Let mid = left + (right - left) / 2.
   • If x - arr[mid] > arr[mid+k] - x, then set left = mid + 1; else, set right = mid.

3. Return arr[left ... left+k-1] as the answer.

Approach 2: Two-Pointer / Sliding Window

Idea:
Initialize two pointers at the start and end of the array and then narrow the window until its size equals k. At each step, compare the absolute difference between x and the elements at the ends of the current window, and remove the element that is farther away from x.

Step-by-step:

1. Initialize two pointers: left = 0 and right = arr.length - 1.

2. While right - left + 1 > k:

   • If |arr[left] - x| > |arr[right] - x|, increment left (drop the left element).
   • Otherwise, decrement right (drop the right element).

3. Return the subarray from arr[left] to arr[right].

Note: Although the sliding window approach works well, the binary search approach is more efficient (especially when arr is large) with a time complexity of O(log(n-k) + k).

Step-by-Step Walkthrough (Binary Search Approach)

Let’s walk through an example with:

• arr = [1, 2, 3, 4, 5]
• k = 4
• x = 3

Step 1: Initialize the Search Boundaries

• Set left = 0 and right = arr.length - k = 5 - 4 = 1.

Step 2: First Iteration of Binary Search

• Compute mid = 0 + (1 - 0) / 2 = 0.

• Compare distances:

  • |x - arr[mid]| = |3 - 1| = 2
  • |arr[mid+k] - x| = |arr[0+4] - 3| = |5 - 3| = 2

• Since 2 is not greater than 2 (i.e. the condition x - arr[mid] > arr[mid+k] - x is false), we set right = mid = 0.

Step 3: End of Binary Search

• Now left == right == 0.
• The window starting at index 0 is [1, 2, 3, 4].

Step 4: Return the Result

• The final answer is [1, 2, 3, 4].

Note: If x were closer to the right side, the binary search would adjust left accordingly.