Mar 4, 2022·

# 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)`.