Problem Description

The K-diff Pairs in an Array problem asks you to find the number of unique pairs in an array nums where the absolute difference between the two elements of each pair is exactly k. A pair is defined as (i, j) where i < j and |nums[i] - nums[j]| == k.

• Each pair should be counted only once, regardless of order.
• Do not reuse the same element at the same index for multiple pairs.
• For k = 0, count pairs of duplicate elements.
• The array can contain both positive and negative numbers.
• Return the total number of unique pairs.

Thought Process

At first glance, a straightforward way to solve this problem is to check every possible pair in the array and see if their difference is k. However, this brute-force approach would take a long time for large arrays because it checks every combination.

To optimize, we need a way to quickly determine if a complement exists for each element. Using a hash map (dictionary) allows us to check for the required difference in constant time. We also need to ensure we count each unique pair only once, which can be handled by careful bookkeeping.

The main challenge is handling duplicates and ensuring that each valid pair is only counted once, especially when k is zero.

Solution Approach

Here is a step-by-step approach to solving the problem efficiently:

1. Use a hash map (dictionary): Count the frequency of each unique number in nums. This allows for constant-time checks for the presence of numbers.
2. Iterate through unique numbers: For each unique number x in the map:
   • If k > 0, check if x + k exists in the map. If it does, count this as a unique pair.
   • If k == 0, check if the count of x is at least 2 (i.e., there is a duplicate). Each such number forms a pair with itself.
3. Count unique pairs: For each valid condition above, increment the result counter.
4. Return the result: The final count gives the number of unique pairs with difference k.

This approach is efficient because it avoids redundant pair checking and leverages the fast lookup capability of hash maps.

Example Walkthrough

Let's walk through an example:
nums = [3, 1, 4, 1, 5], k = 2

1. Build the frequency map:
   • 1: 2
   • 3: 1
   • 4: 1
   • 5: 1
2. Iterate through unique numbers:
   • For 3: 3 + 2 = 5 exists in map ⇒ pair (3,5)
   • For 1: 1 + 2 = 3 exists ⇒ pair (1,3)
   • For 4: 4 + 2 = 6 does not exist
   • For 5: 5 + 2 = 7 does not exist
3. Total unique pairs: (1,3) and (3,5) ⇒ 2 pairs

Notice how each pair is only counted once, and duplicates are handled naturally by the map.

Time and Space Complexity

Brute-force approach:
- Time complexity: O(n^2) because it checks every pair.
- Space complexity: O(1) (ignoring input storage).

Optimized hash map approach:
- Time complexity: O(n) to build the map and O(n) to iterate through unique keys, so overall O(n).
- Space complexity: O(n) for storing the frequency map.

The optimized approach is much more efficient for large arrays.

Summary

To solve the K-diff Pairs in an Array problem efficiently, we use a hash map to count frequencies and quickly check for required complements. By carefully handling the cases where k is zero and ensuring that each unique pair is counted only once, we achieve an elegant and fast solution that works well for all valid inputs.

Code Implementation

from collections import Counter

class Solution:
    def findPairs(self, nums, k):
        if k < 0:
            return 0
        count = 0
        freq = Counter(nums)
        if k == 0:
            for num in freq:
                if freq[num] > 1:
                    count += 1
        else:
            for num in freq:
                if num + k in freq:
                    count += 1
        return count
      

#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (k < 0) return 0;
        unordered_map<int, int> freq;
        for (int num : nums) {
            freq[num]++;
        }
        int count = 0;
        if (k == 0) {
            for (auto &p : freq) {
                if (p.second > 1) count++;
            }
        } else {
            for (auto &p : freq) {
                if (freq.count(p.first + k)) count++;
            }
        }
        return count;
    }
};
      

import java.util.HashMap;

class Solution {
    public int findPairs(int[] nums, int k) {
        if (k < 0) return 0;
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        int count = 0;
        if (k == 0) {
            for (int num : freq.keySet()) {
                if (freq.get(num) > 1) count++;
            }
        } else {
            for (int num : freq.keySet()) {
                if (freq.containsKey(num + k)) count++;
            }
        }
        return count;
    }
}
      

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findPairs = function(nums, k) {
    if (k < 0) return 0;
    let freq = new Map();
    for (let num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    let count = 0;
    if (k === 0) {
        for (let [num, val] of freq.entries()) {
            if (val > 1) count++;
        }
    } else {
        for (let num of freq.keys()) {
            if (freq.has(num + k)) count++;
        }
    }
    return count;
};