Problem

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

Example:

For array [3,1,4,1,5] and k = 2, the output will be 2 because there are two 2-diff pairs in the array, (1, 3) and (3, 5). Though we have two 1s in the input, but, we only return a count of unique pairs. So, 1 will only be counted once.

The pairs (i, j) and (j, i) are counted as the same pair. The lengths of the arrays will not exceed 10,000 and all the integers in the array input will be in the range of -1e7 to 1e7.

Approach

The problem can be solved efficently by using the sliding window and two pointers concepts. But, in our solution we're using a Hash Map (Dictionary in Python and Map in JavaScript). The steps are as follows -

• In the first loop, we fill our map where the pairs are (nums[i], i), i.e., (array element, its index).
• In the second loop, we look for a pair whose difference equals to k. If found, we increase our answer by 1 and remove the found pair from the map to avoid double counting.

Walkthrough

Let's use the given example - In [3, 1, 4, 1, 5] with k = 2, the 2-diff pairs are (1, 3) and (3, 5). So, the output will be 2.

Python Solution

1
2python
3class Solution:
4    def findPairs(self, nums, k):
5        ans = 0
6        numToDict = {}   
7        for i in range(len(nums)):
8            numToDict[nums[i]] = i
9        for i in range(len(nums)):
10            target = nums[i] + k
11            if target in numToDict and numToDict[target] != i:
12                ans += 1
13                numToDict.pop(target)
14        return ans

Java Solution

1
2java
3public class Solution {
4    public int findPairs(int[] nums, int k) {
5        int ans = 0;
6        HashMap<Integer, Integer> numToIndex = new HashMap<>();
7        for (int i = 0; i < nums.length; ++i)
8            numToIndex.put(nums[i], i);
9        for (int i = 0; i < nums.length; ++i) {
10            int target = nums[i] + k;
11            if (numToIndex.containsKey(target) && numToIndex.get(target) != i) {
12                ans++;
13                numToIndex.remove(target);
14            }
15        }
16        return ans;
17    }
18}

JavaScript Solution

1
2javascript
3class Solution {
4    findPairs(nums, k) {
5        let ans = 0;
6        let numToIndex = {};
7        for (let i = 0; i < nums.length; i++)
8            numToIndex[nums[i]] = i;
9        for (let i = 0; i < nums.length; i++) {
10            let target = nums[i] + k;
11            if (numToIndex.hasOwnProperty(target) && numToIndex[target] != i) {
12                ans++;
13                delete numToIndex[target];
14            }
15        }
16        return ans;
17    }
18}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int findPairs(vector<int>& nums, int k) {
6        int ans = 0;
7        unordered_map<int, int> numToIndex;
8        for (int i = 0; i < nums.size(); ++i)
9            numToIndex[nums[i]] = i;
10        for (int i = 0; i < nums.size(); ++i) {
11            int target = nums[i] + k;
12            if (numToIndex.find(target) != numToIndex.end() && numToIndex[target] != i) {
13                ans++;
14                numToIndex.erase(target);
15            }
16        }
17        return ans;
18    }
19};

C# Solution

1
2csharp
3public class Solution {
4    public int FindPairs(int[] nums, int k) {
5        int ans = 0;
6        Dictionary<int, int> numToIndex = new Dictionary<int, int>();
7        for (int i = 0; i < nums.Length; ++i)
8            numToIndex[nums[i]] = i;
9        for (int i = 0; i < nums.Length; ++i) {
10            int target = nums[i] + k;
11            if (numToIndex.ContainsKey(target) && numToIndex[target] != i) {
12                ans++;
13                numToIndex.Remove(target);
14            }
15        }
16        return ans;
17    }
18}

In above solutions, we store element and its index in our hash map. We then iterate over the array to find element which have a difference of k from current element. If we find such pair, we remove it from map to avoid double count. We return count as our answer.# Time Complexity

The time complexity of these solutions is O(n) because we are looping through the array twice. The first pass is to populate the dictionary/map with all the numbers in the array and their corresponding indices. The second pass is to check whether each number has a corresponding pair that is k different, so each loop runs in linear time. Here, 'n' refers to the length of the array

The space complexity is also O(n) because we're storing every number and its index in the dictionary or map, which can reach up to 'n' elements in size.

Solution Test Cases for Python

1
2python
3test = Solution()
4print(test.findPairs([3,1,4,1,5], 2)) # return 2
5print(test.findPairs([1,2,3,4,5], 1)) # return 4
6print(test.findPairs([1,3,1,5,4], 0)) # return 1
7print(test.findPairs([], 1)) # return 0
8print(test.findPairs([1,1,1,1,1], 0)) # return 1

Solution Test Cases for Java

1
2java
3public static void main(String[] args) {
4    Solution test = new Solution();
5    System.out.println(test.findPairs(new int[] {3,1,4,1,5}, 2)); // returns 2
6    System.out.println(test.findPairs(new int[] {1,2,3,4,5}, 1)); // returns 4
7    System.out.println(test.findPairs(new int[] {1,3,1,5,4}, 0)); // returns 1
8    System.out.println(test.findPairs(new int[] {}, 1)); // returns 0
9    System.out.println(test.findPairs(new int[] {1,1,1,1,1}, 0)); // returns 1
10}

Solution Test Cases for JavaScript

1
2javascript
3let test = new Solution();
4console.log(test.findPairs([3,1,4,1,5], 2));  // returns 2
5console.log(test.findPairs([1,2,3,4,5], 1));  // returns 4
6console.log(test.findPairs([1,3,1,5,4], 0));  // returns 1
7console.log(test.findPairs([], 1));  // returns 0
8console.log(test.findPairs([1,1,1,1,1], 0));  // returns 1

Solution Test Cases for C++

1
2cpp
3int main() {
4    Solution test;
5    vector<int> v1 = {3,1,4,1,5};
6    cout << test.findPairs(v1, 2) << endl; // returns 2
7    vector<int> v2 = {1,2,3,4,5};
8    cout << test.findPairs(v2, 1) << endl; // returns 4
9    vector<int> v3 = {1,3,1,5,4};
10    cout << test.findPairs(v3, 0) << endl; // returns 1
11    vector<int> v4 = {};
12    cout << test.findPairs(v4, 1) << endl; // returns 0
13    vector<int> v5 = {1,1,1,1,1};
14    cout << test.findPairs(v5, 0) << endl; // returns 1
15    return 0;
16}

Solution Test Cases for C#

1
2csharp
3public static void Main() {
4    Solution test = new Solution();
5    Console.WriteLine(test.FindPairs(new int[] {3,1,4,1,5}, 2)); // returns 2
6    Console.WriteLine(test.FindPairs(new int[] {1,2,3,4,5}, 1)); // returns 4
7    Console.WriteLine(test.FindPairs(new int[] {1,3,1,5,4}, 0)); // returns 1
8    Console.WriteLine(test.FindPairs(new int[] {}, 1)); // returns 0
9    Console.WriteLine(test.FindPairs(new int[] {1,1,1,1,1}, 0)); // returns 1
10}

By running these test cases, you can be confident that the given solutions are correct.