Binary Search and Two Pointers - 18 ms


  • 2

    Noticing the array is sorted, so we can using binary search to get a rough area of target numbers, and then expand it to the left k-1 more and right k-1 more elements, then searching from the left to right. If the left element is more close or equal to the target number x than the right element, then move the right index to the left one step. Otherwise, move the left index to right one step. Once, the element between the left and right is k, then return the result.

    Java

    public class Solution {
    	public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
    		int index = Collections.binarySearch(arr, x);
    		if (index == -1)
    			return arr.subList(0, k);
    		else if (index >= arr.size())
    			return arr.subList(arr.size() - k, arr.size());
    		else {
    			if (index < 0)
    				index = -index - 1;
    			int left = Math.max(0, index - k - 1), right = Math.min(arr.size() - 1, index + k - 1);
    
    			while (right - left > k - 1) {
    				if (left < 0 || (x - arr.get(left)) <= (arr.get(right) - x))
    					right--;
    				else if (right > arr.size() - 1 || (x - arr.get(left)) > (arr.get(right) - x))
    					left++;
    				else
    					System.out.println("unhandled case: " + left + " " + right);
    			}
    
    			return arr.subList(left, right + 1);
    		}
    	}
    }
    

    Here is an updated version.

    public class Solution {
    	public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
    		int n = arr.size();
    		if (x <= arr.get(0)) {
    			return arr.subList(0, k);
    		} else if (arr.get(n - 1) <= x) {
    			return arr.subList(n - k, n);
    		} else {
    			int index = Collections.binarySearch(arr, x);
    			if (index < 0)
    				index = -index - 1;
    			int low = Math.max(0, index - k - 1), high = Math.min(arr.size() - 1, index + k - 1);
    
    			while (high - low > k - 1) {
    				if (low < 0 || (x - arr.get(low)) <= (arr.get(high) - x))
    					high--;
    				else if (high > arr.size() - 1 || (x - arr.get(low)) > (arr.get(high) - x))
    					low++;
    				else
    					System.out.println("unhandled case: " + low + " " + high);
    			}
    			return arr.subList(low, high + 1);
    		}
    	}
    }
    

  • 0

    I think the time complexity is O(logn + k). Right?


  • 0

    @Mr.Bin Yes the complexity is correct.
    Additionally,
    This piece : if (left < 0 isnt required as you have already ensured that left >= 0 in int left = Math.max(0, index - k - 1)
    Similar reasoning applies for else if (right > arr.size() - 1


  • 0

    @soumyadeep2007 said in Binary Search and Two Pointers - 18 ms:

    (left <

    No. The reason is if the target element x is not in the array, it will error out. Taking the following case for example:
    [0,0,1,2,3,3,4,7,7,8]
    3
    5


  • 0
    C

    @Mr.Bin Correct me if I'm wrong, but if you expand the range k elements to the left and right (instead of k-1), wouldn't that handle the case when the target is and is not in the array?

    Then, in the while loop, you could simplify the logic to two cases:

    if (x - arr.get(low)) <= arr.get(high) - x) {
        high--
    } else {
        low++;
    }
    

  • 0

    @chokobo Yes, it will handle it. Expanding more element (>k-1) won't be an issue as long as staying the range of this array.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.