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:
- Initialize a Hash Map (let’s call it count) and a Hash Set (let’s call it seen).
- Iterate through each element (let’s call it num) in the array.
- 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.
- 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.
- Add the current element num to the seen Hash Set.
- Repeat steps 2-5 for all elements in the array.
- 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 Mapmap = 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 HashSetset = 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; } }