Solution For K Diff Pairs In An Array

Problem Statement:

Given an array nums of n integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

Solution Approach:

We can solve this problem using a Hash Map (or Hash Set). We can iterate through each element in the array, and check if its corresponding k-diff element is present in the Hash Map. If it is present, we mark it as a valid pair and move forward.

We can also keep track of the already seen elements in the array using another Hash Map (or Hash Set). This will enable us to avoid counting the same pair again.

Algorithm:

1. Initialize a Hash Map (let’s call it count) and a Hash Set (let’s call it seen).
2. Iterate through each element (let’s call it num) in the array.
3. Check if there exists an element (let’s call it num-k) such that num – num-k = k, and num-k is already present in the seen Hash Set. If yes, add the pair (num, num-k) to the count Hash Map.
4. Check if there exists an element (let’s call it num+k) such that num+k = k, and num+k is already present in the seen Hash Set. If yes, add the pair (num, num+k) to the count Hash Map.
5. Add the current element num to the seen Hash Set.
6. Repeat steps 2-5 for all elements in the array.
7. Return the size of the count Hash Map.

Python Code:

class Solution:
def findPairs(self, nums: List[int], k: int) -> int:
count = {}
seen = set()
for num in nums:
if num – k in seen:
count[(num-k, num)] = 1
if num + k in seen:
count[(num, num+k)] = 1
seen.add(num)
return len(count)

Step by Step Implementation For K Diff Pairs In An Array

class Solution {
    public int findPairs(int[] nums, int k) {
        // create a map to store the number of occurrences for each number
        Map map = new HashMap<>();
        // store the number of pairs that have a difference of k
        int count = 0;
        
        // fill the map
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        
        // iterate through the map
        for (Map.Entry entry : map.entrySet()) {
            // if k is 0, check if the number has at least 2 occurrences
            if (k == 0) {
                if (entry.getValue() >= 2) {
                    count++;
                }
            // otherwise, check if the map contains the number that is k away from the current number    
            } else {
                if (map.containsKey(entry.getKey() + k)) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

# Given an array of integers 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 are true:

# 0 <= i, j < nums.length
# i != j
# a <= b
# b - a == k
 
def findPairs(nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: int
    """
    
    # create a dictionary to store the number of times each number appears in the list
    num_count = {}
    
    # iterate through the list and update the dictionary
    for num in nums:
        if num in num_count:
            num_count[num] += 1
        else:
            num_count[num] = 1
    
    # initialize a variable to store the number of unique k-diff pairs
    pairs = 0
    
    # iterate through the dictionary
    for key in num_count:
        
        # if k == 0, we only need to check if the number appears more than once in the list
        if k == 0:
            if num_count[key] > 1:
                pairs += 1
        
        # if k != 0, we need to check if the dictionary contains key + k
        else:
            if key + k in num_count:
                pairs += 1
    
    return pairs

var findPairs = function(nums, k) {
  if (k < 0) {
    return 0;
  }
  let map = {};
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    if (map[nums[i]]) {
      map[nums[i]]++;
    } else {
      map[nums[i]] = 1;
    }
  }
  for (let key in map) {
    if (k === 0) {
      if (map[key] >= 2) {
        count++;
      }
    } else {
      if (map[parseInt(key) + k]) {
        count++;
      }
    }
  }
  return count;
};

There are two solutions given below.

Solution 1:

class Solution {
public:
    int findPairs(vector& nums, int k) {
        if (k < 0) return 0;
        int count = 0;
        unordered_map m;
        for (int num : nums) {
            m[num]++;
        }
        for (auto it = m.begin(); it != m.end(); it++) {
            if (k == 0) {
                if (it->second >= 2) count++;
            } else {
                if (m.find(it->first + k) != m.end()) count++;
            }
        }
        return count;
    }
};

Solution 2:

class Solution {
public:
    int findPairs(vector& nums, int k) {
        if (k < 0) return 0;
        int count = 0;
        unordered_set s;
        unordered_set visited;
        for (int num : nums) {
            s.insert(num);
        }
        for (int num : nums) {
            if (visited.find(num) != visited.end()) continue;
            if (k == 0) {
                if (s.count(num) >= 2) count++;
            } else {
                if (s.count(num + k)) count++;
            }
            visited.insert(num);
        }
        return count;
    }
};

public class Solution {
    public int FindPairs(int[] nums, int k) {
        //edge case
        if (nums == null || nums.Length == 0 || k < 0) {
            return 0;
        }
        
        //hashset to store unique values
        HashSet set = new HashSet();
        int count = 0;
        
        //go through each number in array
        foreach (int num in nums) {
            //if number + k is in hashset, increment count
            if (set.Contains(num + k)) {
                count++;
            }
            //if number - k is in hashset, increment count
            if (set.Contains(num - k)) {
                count++;
            }
            //add number to hashset
            set.Add(num);
        }
        return count;
    }
}