Java sort and binary search solution, 28ms with explanation


  • 0
    Z

    The basic idea is to sort the array and skip the duplicate pairs so we only need iterating the array once. And for a given value at nums[i], we only need to find if nums[i]+k exists in the subarray of range [i+1,end]. We can use binary search for each iteration, thus the time complexity is O(nlogn).

    	public int findPairs(int[] nums, int k) {
    		Arrays.sort(nums);
    		int count = 0;
    		int prev = Integer.MIN_VALUE;
    		for (int i = 0; i < nums.length; i++) {
    			if (nums[i] != prev) {
    				if (binary_search_pair(nums, nums[i] + k, i + 1, nums.length - 1))
    					count++;
    				prev = nums[i];
    			}
    		}
    		return count;
    	}
    
    	private boolean binary_search_pair(int nums[], int t, int st, int ed) {
    		if (st > ed)
    			return false;
    		int mid = (st + ed) / 2;
    		if (nums[mid] < t)
    			return binary_search_pair(nums, t, mid + 1, ed);
    		else if (nums[mid] > t)
    			return binary_search_pair(nums, t, st, mid - 1);
    		else
    			return true;
    	}
    

Log in to reply
 

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