Comment: Amazon 6 months SDE Internship Interview Experience

Approach 3 sort the array. since X - arr[i] will be monotonic. we can apply Binary Search here. we will look for k+1 closet element. Predicate : X - arr[i] <= arr[i+(k+1)] - X Predicate will reduce our problem to F* T*  pattern and we are interested in finding the position (index) of first True(T).  Complexity  TC is O(nlogn) due to sorting  SC is O(1).   Pseudocode lo = 0, hi = n-k-1; while(lo<hi){ mid = lo+(hi-lo)/2; if(x-arr[mid] <= arr[mid+k+1]-x){ hi = mid; } else ...