K-diff Pairs in an Array

Problem statement

Given an array of integer nums and an integer k, return the number of unique k-diff pairs in the array.

A k-diff pair is an integer pair (nums[i], nums[j]), where the following is true:

• 0 <= i, j < nums.length

• i != j

• |nums[i] - nums[j]| == k

Notice that |val| denotes the absolute value of Val.

Constraints

• 1 <= nums.length <= 10<sup>4</sup>

• -10<sup>7</sup> <= nums[i] <= 10<sup>7</sup>

• 0 <= k <= 10<sup>7</sup>

Examples

nums = [3, 1, 4, 1, 5], k = 2

Output = 2

Sudo Code

Two Pointers Approach

1. Initialize the variables

2. Sort arrays

3. Loop till the right or left ends

   1. If diff between the right and left elements is less than k or the left and right are the same, increment right.

   2. If the diff is more than k, the increment left

   3. Else increment left and result, Skip the duplicates using a loop.

HashMap Approach

1. Initialize the map.

2. Capture the frequency of each element in the map.

3. Iterate over the map and check whether k>0 && map contains map element + k or k==0 and map element having a frequency of more than 1. If yes increment result.

Dry Run

Solution

// Two pointers approach
    public int findPairs(int[] nums, int k) {

        // 1. Initialize the variables
        int left = 0, right = 1;
        int result = 0;

        // 2. Sort arrays
        Arrays.sort(nums);

        // 3. Loop till right or left ends
        while(left < nums.length && right < nums.length){
            // 3.1 If diff between right and left element is less than k or left and right are same, increment right
            if(left == right || nums[right] - nums[left] < k){
                right++;
            // 3.2 If diff is more than k, increment left
            }else if(nums[right] - nums[left] > k){
                left++;
            }else{
            // 3.3 Else increment left and result, Skip the duplicates using loop.
                left++;
                result++;
                while(left < nums.length && nums[left] == nums[left-1]){
                    left++;
                }
            }
        }
        return result;
    }

// Hashmap approach
    public int findPairs(int[] nums, int k) {
            // 1. Initialize the map
        Map<Integer, Integer> map = new HashMap();
           // 2. Capture the frequency of each element in map
         for(int x : nums){
             map.put(x, map.getOrDefault(x, 0) + 1);
         }

         int result = 0;
            // 3. Iterate over map and check whether k>0 && map contains map element + k or  k==0 and map element having frquency more than 1. If yes increment result
         for(int i : map.keySet()){
             if((k > 0 && map.containsKey(i+k)) || (k == 0 && map.get(i) > 1)){
                 result++;
             }
         }
         return result;
     }

Time complexity Analysis

Two pointers -

Time complexity - O(nlogn)

Space complexity - O(1)

HashMap -

Time complexity - O(N)

Space complexity - O(N)

Topics Covered

Two Pointers, Hashmap

Companies

Adobe, Amazon, Facebook,