Problem Statement

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,
• |nums[i] - nums[j]| == k.

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

Example 1

Input: nums = [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: nums = [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: nums = [1,3,1,5,4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Constraints

• 1 <= nums.length <= 10^4.
• -10^7 <= nums[i] <= 10^7.
• 0 <= k <= 10^7.

Solution 1: Building the unique pairs using std::set

In this problem, two pairs (a,b) and (b,a) are counted once. You can use the property that elements of std::set are sorted and unique to build up the unique pairs.

1. Make each pair be a std::set<int> of two integers, so two pairs (a,b) and (b,a) are sorted and counted once.
2. Let pairs be the set of unique k-diff pairs you want to compute. Make it a std::set as well.
3. Search all satisfied pairs in the nums and insert them to the pairs.

Example 1

For nums = [3,1,4,1,5] and k = 2. The second pair of (3,1) with 1 = nums[3] is not inserted to the set pairs since (3,1) was already there.

Code

#include <vector>
#include <iostream>
#include <set>
using namespace std;
int findPairs(vector<int>& nums, int k) {
    set<set<int> > pairs;
    for (int i = 0; i < nums.size() - 1; i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (abs(nums[j] - nums[i]) == k) {

                // {nums[i], nums[j]} is sorted and compared with the elements of pairs
                pairs.insert({nums[i], nums[j]});
            }
        }
    }
    return pairs.size();
}
int main() {
    vector<int> nums{3,1,4,1,5};
    cout << findPairs(nums, 2) << endl;
    nums = {1,2,3,4,5};
    cout << findPairs(nums, 1) << endl;
    nums = {1,3,1,5,4};
    cout << findPairs(nums, 0) << endl;
}

Output:
2
4
1

Complexity

• Runtime: O(N*N*logN), where N = nums.size().
• Extra space: O(N*N).

Solution 2: Inserting only the representative of each pair

The inserted pair {nums[i], nums[j]} is always sorted and their difference is always k. You could choose only the smaller value as the representative for their insertion to the set pairs.

It means instead of storing pairs

pairs = {(a, a + k), (b, b + k), (c, c + k), ...}

you can store only the representatives since you need only the number of elements at the end of the day.

pairs = {a, b, c, ...}

Code

#include <vector>
#include <iostream>
#include <set>
using namespace std;
int findPairs(vector<int>& nums, int k) {
    set<int> pairs;
    for (int i=0; i < nums.size() - 1; i++) {
        for (int j=i+1; j < nums.size(); j++) {
            if (abs(nums[j] - nums[i]) == k) {
                pairs.insert(min(nums[i], nums[j]));
            }
        }
    }
    return pairs.size();
}
int main() {
    vector<int> nums{3,1,4,1,5};
    cout << findPairs(nums, 2) << endl;
    nums = {1,2,3,4,5};
    cout << findPairs(nums, 1) << endl;
    nums = {1,3,1,5,4};
    cout << findPairs(nums, 0) << endl;
}

Output:
2
4
1

Complexity

• Runtime: O(N*N*logN), where N = nums.size().
• Extra space: O(N).

Solution 3: Counting instead of insertion using the std::unordered_map

A pair (a, a + k) belongs to the final pairs if both a and a + k belong to nums. You can use an std::unordered_map to mark the presence of the elements of nums.

In case of k = 0 the final result is simply counting the duplicates in the nums. Letting the value of each key in the map be its number of presence will be helpful.

Code

#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;
int findPairs(vector<int>& nums, int k) {
    unordered_map<int,int> numFreq;
    int result = 0;
    for (const auto& n : nums) {
        numFreq[n]++;
    }
    for (const auto& nf : numFreq) {
        if (k == 0) {
            if (nf.second > 1) {
                result++;
            }
        } else if (numFreq.find(nf.first + k) != numFreq.end()) {
            result++;
        }
    }
    return result;
}
int main() {
    vector<int> nums{3,1,4,1,5};
    cout << findPairs(nums, 2) << endl;
    nums = {1,2,3,4,5};
    cout << findPairs(nums, 1) << endl;
    nums = {1,3,1,5,4};
    cout << findPairs(nums, 0) << endl;
}

Output:
2
4
1

Complexity

• Runtime: O(N), where N = nums.size().
• Extra space: O(N).