How to Find the K-diff Pairs in an Array with Two Pointer or Hash Map?

Given an array of 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.

Example 1:
Input: [3, 1, 4, 1, 5], k = 2
Output: 2

Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:
Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:
Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Note:

• The pairs (i, j) and (j, i) count as the same pair.
• The length of the array won’t exceed 10,000.
• All the integers in the given input belong to the range: [-1e7, 1e7].

Bruteforce and Two Pointer Algorithm to Count the K-diff Pairs

We can first sort the array in O(nlogN) complexity. Then we can easily skip the duplicates:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        sort(begin(nums), end(nums));
        int n = nums.size();
        int res = 0;
        for (int i = 0; i < n; ++ i) {
            if ((i > 0) && (nums[i] == nums[i - 1])) continue;
            for (int j = i + 1; j < n; ++ j) {
                if (nums[j] - nums[i] > k) {
                    break;
                }
                if (nums[j] - nums[i] == k) {
                    res ++;
                    break;
                }
            }
        }
        return res;
    }
};

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        sort(begin(nums), end(nums));
        int n = nums.size();
        int res = 0;
        for (int i = 0; i < n; ++ i) {
            if ((i > 0) && (nums[i] == nums[i - 1])) continue;
            for (int j = i + 1; j < n; ++ j) {
                if (nums[j] - nums[i] > k) {
                    break;
                }
                if (nums[j] - nums[i] == k) {
                    res ++;
                    break;
                }
            }
        }
        return res;
    }
};

The bruteforce algorithm iterates all O(N^2) pairs and once we have found a matching pair or the absolute difference is larger than K, we can break the inner loop immediately.

Two Pointer Algorithm in O(nlogN)

In order to use the Two-Pointer algorithm, the array has to be sorted, and that requires O(nlogN) time. If we move two pointers i and j towards the right direction when comparing the absolute difference with k, the complexity is O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        sort(begin(nums), end(nums));
        int n = nums.size();
        int res = 0;
        int i = 0, j = 0;
        while (j < n) {
            if (i == j) {
                j ++;
            }
            if ((j < n) && (nums[j] - nums[i] == k)) {
                res ++;
                i ++;
                // skip duplicates
                while (i < n && (nums[i] == nums[i - 1])) i ++;
                while (j < n && (nums[j] == nums[j - 1])) j ++;                
            } else if (j < n && (nums[j] - nums[i]) > k) {
                i ++;
            } else {
                j ++;
            }
        }
        return res;
    }
};

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        sort(begin(nums), end(nums));
        int n = nums.size();
        int res = 0;
        int i = 0, j = 0;
        while (j < n) {
            if (i == j) {
                j ++;
            }
            if ((j < n) && (nums[j] - nums[i] == k)) {
                res ++;
                i ++;
                // skip duplicates
                while (i < n && (nums[i] == nums[i - 1])) i ++;
                while (j < n && (nums[j] == nums[j - 1])) j ++;                
            } else if (j < n && (nums[j] - nums[i]) > k) {
                i ++;
            } else {
                j ++;
            }
        }
        return res;
    }
};

When the absolute difference is more than k, we increment the pointer i – which will make the difference smaller, and when the absolute difference is less than k, we increment the pointer j – that will make the difference bigger. Otherwise, we need to increment the answer, increment the counter i (make the difference smaller again), and skip the duplicates for numbers at pointer i and j.

Using Hash Map

All the above algorithms use constant space. We can however, use O(N) additional space to achieve O(N) time complexity. The solution is to use a hash map to remember the numbers and their frequencies.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (nums.empty()) return 0;
        if (k < 0) return 0;
        unordered_map<int, int> data;
        for (const auto &n: nums) {
            data[n] ++;
        }
        int res = 0;        
        for (auto it = data.begin(); it != data.end(); ++ it) {
            if (k == 0) {
                int x = it->second;
                if (x > 1) {
                    res ++;
                }
            } else {
              if (data.find(it->first - k) != data.end()) {
                  res ++;
              }
            }
        }
        return res;
    }
};

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (nums.empty()) return 0;
        if (k < 0) return 0;
        unordered_map<int, int> data;
        for (const auto &n: nums) {
            data[n] ++;
        }
        int res = 0;        
        for (auto it = data.begin(); it != data.end(); ++ it) {
            if (k == 0) {
                int x = it->second;
                if (x > 1) {
                    res ++;
                }
            } else {
              if (data.find(it->first - k) != data.end()) {
                  res ++;
              }
            }
        }
        return res;
    }
};

The edge cases: When K is negative, the answer is zero. When k is zero, then we return the number of the duplicate numbers in the array. Otherwise, it will be the same for solving the Two-Sum problem via finding the difference between the number and k.

Using Multiset

As the multiset can be use to count the duplicates in the array, we can use the unordered_multiset to achieve the task. However, if we iterating the multiset, the same numbers will be iterated as many time as they appear. To solve the problem, we can use another unordered_set (hash set) to avoid duplicate counting.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (nums.empty()) return 0;
        if (k < 0) return 0;
        unordered_multiset<int> data;
        for (const auto &n: nums) {
            data.insert(n);
        }
        int res = 0;
        unordered_set<int> v;
        for (const auto &n: data) {
            if (v.count(n)) continue;
            v.insert(n);
            if (k == 0) {
                int x = data.count(n);
                if (x > 1) res ++;
            } else {
              if (data.count(n - k)) {
                  res ++;
              }
            }
        }
        return res;
    }
};

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (nums.empty()) return 0;
        if (k < 0) return 0;
        unordered_multiset<int> data;
        for (const auto &n: nums) {
            data.insert(n);
        }
        int res = 0;
        unordered_set<int> v;
        for (const auto &n: data) {
            if (v.count(n)) continue;
            v.insert(n);
            if (k == 0) {
                int x = data.count(n);
                if (x > 1) res ++;
            } else {
              if (data.count(n - k)) {
                  res ++;
              }
            }
        }
        return res;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —