# K-diff Pairs in an Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/k-diff-pairs-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/k-diff-pairs-in-an-array
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [tcs](https://scaleengineer.com/companies/tcs), [Capital One](https://scaleengineer.com/companies/capital-one)
---
## Problem
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 <= 104`
* `-107 <= nums[i] <= 107`
* `0 <= k <= 107`

# Approaches
## Brute Force with Set
This approach iterates through all possible pairs of elements in the array and checks if their absolute difference is equal to `k`. To ensure that we only count unique pairs, a `Set` is used to store the pairs found in a canonical form.
**Time:** O(N^2), where N is the number of elements in `nums`. The two nested loops result in a quadratic time complexity as we compare every element with every other element. · **Space:** O(P), where P is the number of unique pairs. In the worst-case scenario, P can be up to N, so the space complexity is O(N).
**Pros:** Simple to understand and implement.
**Cons:** Inefficient for large input arrays due to its O(N^2) time complexity, which will likely result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
We can solve this problem by checking every possible pair of numbers in the array. We use two nested loops to generate these pairs.

For each pair `(nums[i], nums[j])` where `i < j`, we calculate the absolute difference `|nums[i] - nums[j]|`.

If the difference equals `k`, we have found a k-diff pair. However, the problem asks for *unique* pairs. For example, in `[1, 3, 1, 3]` with `k=2`, the pair `(1, 3)` should be counted only once.

To handle this, we store the found pairs in a `Set`. To treat `(a, b)` and `(b, a)` as the same pair, we store them in a canonical order, for instance, `(min(a, b), max(a, b))`. A `Set` of `Pair` objects or a `Set` of `String` representations like `"min_val,max_val"` can be used.

The final result is the size of this set.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int findPairs(int[] nums, int k) {
        if (k < 0) {
            return 0;
        }
        Set<String> uniquePairs = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (Math.abs(nums[i] - nums[j]) == k) {
                    int min = Math.min(nums[i], nums[j]);
                    int max = Math.max(nums[i], nums[j]);
                    uniquePairs.add(min + "," + max);
                }
            }
        }
        return uniquePairs.size();
    }
}
```
### Algorithm
- Initialize an empty `HashSet<String>` called `uniquePairs` to store the unique pairs.
- Iterate through the array with a pointer `i` from `0` to `n-1`.
- Inside this loop, iterate with another pointer `j` from `i+1` to `n-1`.
- For each pair `(nums[i], nums[j])`, check if `Math.abs(nums[i] - nums[j]) == k`.
- If the condition is true, form a canonical string representation of the pair, e.g., `Math.min(nums[i], nums[j]) + "," + Math.max(nums[i], nums[j])`, and add it to the `uniquePairs` set.
- After the loops complete, return the size of `uniquePairs`.

## Sorting with Two Pointers
A more efficient approach involves sorting the array first. Once sorted, we can use a two-pointer technique to find the pairs in linear time. This method avoids redundant comparisons and handles duplicates effectively.
**Time:** O(N log N), dominated by the initial sorting of the array. The two-pointer scan takes O(N) time as each pointer traverses the array at most once. · **Space:** O(log N) or O(N), depending on the implementation of the sorting algorithm used. For example, in Java, `Arrays.sort()` for primitives uses a variant of Quicksort which has O(log N) space complexity on average.
**Pros:** Significantly more efficient than the brute-force approach.; Handles duplicates elegantly after sorting.
**Cons:** The sorting step makes it slower than a hash-based approach.; The logic for handling duplicates and moving pointers can be tricky to get right.
### Explanation
This approach leverages the fact that if the array is sorted, we can search for pairs more efficiently.

First, we sort the input array `nums`.

We then use two pointers, `left` and `right`, initialized to `0` and `1` respectively.

We iterate while `right` is within the bounds of the array:
1. Calculate the difference `diff = nums[right] - nums[left]`.
2. If `diff == k`, we've found a unique pair. We increment our count. To avoid counting duplicates, we then advance the `left` pointer past any subsequent identical elements.
3. If `diff < k`, the difference is too small. We need to increase it, so we move the `right` pointer to the right (`right++`).
4. If `diff > k`, the difference is too large. We need to decrease it, so we move the `left` pointer to the right (`left++`).

We must also handle the case where `left` and `right` pointers meet, by incrementing `right` to ensure `left != right`.

This two-pointer scan on the sorted array correctly identifies unique pairs without needing an extra set for the pairs themselves, as the duplicate handling is managed by advancing the pointers past identical elements.

```java
import java.util.Arrays;

class Solution {
    public int findPairs(int[] nums, int k) {
        Arrays.sort(nums);
        int count = 0;
        int left = 0;
        for (int right = 1; right < nums.length; right++) {
            // Skip duplicates for the right pointer
            if (right < nums.length - 1 && nums[right] == nums[right + 1]) {
                continue;
            }
            // Skip duplicates for the left pointer
            while (left < right && nums[left] == nums[left + 1]) {
                left++;
            }
            
            while (left < right && nums[right] - nums[left] > k) {
                left++;
            }
            
            if (left < right && nums[right] - nums[left] == k) {
                count++;
            }
        }
        return count;
    }
}
```
An alternative, perhaps simpler two-pointer implementation:
```java
import java.util.Arrays;

class Solution {
    public int findPairs(int[] nums, int k) {
        Arrays.sort(nums);
        int count = 0;
        int left = 0;
        int right = 1;
        while (left < nums.length && right < nums.length) {
            if (left == right || nums[right] - nums[left] < k) {
                right++;
            } else if (nums[right] - nums[left] > k) {
                left++;
            } else {
                count++;
                left++;
                while (left < nums.length && nums[left] == nums[left - 1]) {
                    left++;
                }
                right = Math.max(right + 1, left + 1);
            }
        }
        return count;
    }
}
```
### Algorithm
- Sort the input array `nums`.
- Initialize `count = 0`, `left = 0`, and `right = 1`.
- Loop while `right < nums.length`.
- If `left == right` or `nums[right] - nums[left] < k`, increment `right`.
- Else if `nums[right] - nums[left] > k`, increment `left`.
- Else (a pair is found):
    - Increment `count`.
    - Increment `left`.
    - Skip any duplicates for the `left` pointer by advancing it while `nums[left] == nums[left - 1]`.
    - Move `right` to be at least `left + 1`.
- Return `count`.

## Hash-based Approach
The most optimal approach uses a hash map or a hash set to achieve linear time complexity. By storing elements and their frequencies (or just their presence), we can quickly check for the existence of the other element in a potential pair.
**Time:** O(N), where N is the number of elements in `nums`. In both cases (`k=0` and `k>0`), we iterate through the array once to populate the hash map/set, and then iterate through the unique elements (at most N), with each operation being O(1) on average. · **Space:** O(N) in the worst case, where all elements are unique. The hash map or hash set needs to store up to N distinct elements.
**Pros:** Most efficient time complexity at O(N).; The logic is straightforward and easy to reason about.
**Cons:** Requires extra space to store the hash map or hash set, which could be a concern for very large inputs with many unique elements.
### Explanation
This approach handles the problem in O(N) time by using a hash-based data structure. The logic is slightly different for `k=0` and `k>0`.

**Case 1: `k > 0`**

We want to find pairs `(x, y)` where `y = x + k`. To count unique pairs, we can first find all unique numbers in the input array. A `HashSet` is perfect for this.
1. Add all elements from `nums` into a `HashSet` to get rid of duplicates.
2. Initialize a `count` to 0.
3. Iterate through each number `num` in the hash set.
4. For each `num`, check if the set also contains `num + k`.
5. If it does, we have found a unique pair, so we increment `count`.
By iterating through the unique numbers and only checking for `num + k`, we avoid double-counting.

**Case 2: `k = 0`**

We are looking for pairs `(x, x)`, which means we need to find numbers that appear more than once in the array.
1. Use a `HashMap` to store the frequency of each number in `nums`.
2. Initialize a `count` to 0.
3. Iterate through the entries in the frequency map.
4. If a number's frequency is greater than 1, it can form a 0-diff pair. Increment `count`.

Finally, return the total `count`.

```java
import java.util.HashMap;
import java.util.Map;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int findPairs(int[] nums, int k) {
        if (k < 0) {
            return 0;
        }
        
        int count = 0;
        if (k == 0) {
            Map<Integer, Integer> freqMap = new HashMap<>();
            for (int num : nums) {
                freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
            }
            for (int freq : freqMap.values()) {
                if (freq > 1) {
                    count++;
                }
            }
        } else { // k > 0
            Set<Integer> uniqueNums = new HashSet<>();
            for (int num : nums) {
                uniqueNums.add(num);
            }
            for (int num : uniqueNums) {
                if (uniqueNums.contains(num + k)) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- If `k < 0`, return 0.
- If `k == 0`:
    - Create a `HashMap` to store frequencies of numbers in `nums`.
    - Iterate through the map's values. For each frequency greater than 1, increment a counter.
    - Return the counter.
- If `k > 0`:
    - Create a `HashSet` and add all elements from `nums` to it to get unique numbers.
    - Initialize a counter to 0.
    - Iterate through each number `num` in the `HashSet`.
    - Check if the set contains `num + k`. If it does, increment the counter.
    - Return the counter.

# Solutions
### Java

```java
class Solution {
public
  int findPairs(int[] nums, int k) {
    Set<Integer> vis = new HashSet<>();
    Set<Integer> ans = new HashSet<>();
    for (int v : nums) {
      if (vis.contains(v - k)) {
        ans.add(v - k);
      }
      if (vis.contains(v + k)) {
        ans.add(v);
      }
      vis.add(v);
    }
    return ans.size();
  }
}

```

### Python

```python
class Solution:
    def findPairs(self, nums: List[int], k: int) -> int: vis, ans = set(), set() for v in nums: if v - k in vis: ans . add(v - k) if v + k in vis: ans . add(v) vis . add(v) return len(ans)

```

### CPP

```cpp
class Solution {
public:
  int findPairs(vector<int> &nums, int k) {
    unordered_set<int> vis;
    unordered_set<int> ans;
    for (int &v : nums) {
      if (vis.count(v - k))
        ans.insert(v - k);
      if (vis.count(v + k))
        ans.insert(v);
      vis.insert(v);
    }
    return ans.size();
  }
};

```