Easy Java Solution, Using two pointers and one Hash Map, O(N)


  • 0
    R
        public int findPairs(int[] nums, int k) {
            Arrays.sort(nums);
            int i = 0;
            int j = 0;
            int count = 0;
            Map<String, Integer> mp = new HashMap<>();
            while(j<nums.length){
                 
                // move 'right' pointer till you have difference less than k
                while(j<nums.length && Math.abs(nums[j] - nums[i]) < k){
                    j++;
                }
    
                // move 'left' pointer till you have difference greater or equal to k, Process it now.
                // Use a map to avoid duplicates
                while( j<nums.length && i<j &&  (Math.abs(nums[j]-nums[i]) >= k) ){
                    if(i!=j && (Math.abs(nums[j]-nums[i]) == k)){
                        String key = nums[j]+"#"+nums[i];
                        if(!mp.containsKey(key)){
                            mp.put(key,1);
                        }
                    }
                    i++;
                }
                j++;
            }
            
            return mp.size();   // Return the size of map, number of desired pairs
            
        }
    }
    

Log in to reply
 

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