Problem Description

You are given an array of integers nums and an integer k. Your task is to find the number of unique k-diff pairs in the array.

A k-diff pair is defined as a pair of integers (nums[i], nums[j]) from the array that satisfies all of the following conditions:

1. Both indices i and j are valid positions in the array: 0 <= i, j < nums.length
2. The indices must be different: i != j
3. The absolute difference between the two values equals k: |nums[i] - nums[j]| == k

The key requirement is that pairs must be unique - meaning if you have multiple occurrences of the same pair of values, they should be counted only once.

For example:

• If nums = [3, 1, 4, 1, 5] and k = 2, the k-diff pairs are (1, 3) and (3, 5), so the answer is 2
• If nums = [1, 2, 3, 4, 5] and k = 1, there are four k-diff pairs: (1, 2), (2, 3), (3, 4), (4, 5), so the answer is 4
• If nums = [1, 3, 1, 5, 4] and k = 0, the only k-diff pair is (1, 1) (since 1 appears twice), so the answer is 1

The solution uses a hash table approach where we track the smaller value of each valid pair to ensure uniqueness. As we traverse the array, we check if the current number can form a valid k-diff pair with previously seen numbers by checking if x - k or x + k exists in our visited set.

Intuition

The key insight is that for any number x in the array, it can form a k-diff pair in only two possible ways:

1. With a smaller number: (x - k, x) where the difference is x - (x - k) = k
2. With a larger number: (x, x + k) where the difference is (x + k) - x = k

Since we want to count unique pairs, we need a way to avoid counting the same pair multiple times. A clever approach is to always store the smaller value of each pair in a set. This ensures that even if we encounter the same pair from different positions in the array, we only count it once.

As we traverse the array, for each number x:

• If we've already seen x - k, then (x - k, x) forms a valid pair, and we store x - k (the smaller value)
• If we've already seen x + k, then (x, x + k) forms a valid pair, and we store x (the smaller value)

By using this approach with two sets - one (vis) to track all numbers we've seen so far, and another (ans) to store the smaller values of valid pairs - we can efficiently find all unique k-diff pairs in a single pass through the array.

The beauty of this solution is that it naturally handles duplicates and ensures uniqueness. For example, if we have [1, 3, 1, 5, 4] with k = 2, when we encounter the second 1, we won't add a duplicate pair because 1 - 2 = -1 would be the same smaller value we might have already stored.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The solution uses a hash table strategy with two sets to efficiently find all unique k-diff pairs in a single pass through the array.

Data Structures Used:

• ans: A set that stores the smaller value of each valid k-diff pair to ensure uniqueness
• vis: A set that keeps track of all numbers we've encountered so far

Algorithm Steps:

1. Initialize two empty sets: ans for storing unique pairs (represented by their smaller values) and vis for tracking visited numbers.

2. Iterate through each number x in the array:

   a. Check for smaller partner: If x - k exists in vis, it means we can form a pair (x - k, x) with difference k. Add x - k to ans (the smaller value of the pair).

   b. Check for larger partner: If x + k exists in vis, it means we can form a pair (x, x + k) with difference k. Add x to ans (the smaller value of the pair).

   c. Mark current number as visited: Add x to vis for future iterations.

3. Return the size of ans, which represents the count of unique k-diff pairs.

Why this works:

• By storing only the smaller value of each pair in ans, we automatically handle uniqueness - even if the same pair appears multiple times through different combinations, it will only be stored once
• The order of traversal doesn't matter because we check both directions (x - k and x + k) for each number
• The time complexity is O(n) since we traverse the array once, and set operations are O(1) on average
• The space complexity is O(n) for storing the visited numbers and unique pairs

Example walkthrough with nums = [3, 1, 4, 1, 5] and k = 2:

• Process 3: vis = {3}, ans = {}
• Process 1: Check 1-2=-1 (not in vis), check 1+2=3 (in vis), add 1 to ans. vis = {3, 1}, ans = {1}
• Process 4: Check 4-2=2 (not in vis), check 4+2=6 (not in vis). vis = {3, 1, 4}, ans = {1}
• Process 1: Check 1-2=-1 (not in vis), check 1+2=3 (in vis), add 1 to ans (already there). vis = {3, 1, 4}, ans = {1}
• Process 5: Check 5-2=3 (in vis), add 3 to ans. Check 5+2=7 (not in vis). vis = {3, 1, 4, 5}, ans = {1, 3}
• Final answer: len(ans) = 2

Example Walkthrough

Let's walk through a detailed example with nums = [1, 2, 4, 4, 3, 3, 0, 9, 2, 3] and k = 3.

We'll track two sets:

• vis: numbers we've seen so far
• ans: smaller values of valid k-diff pairs (for uniqueness)

Step-by-step process:

1. Process 1:

   • Check if 1 - 3 = -2 is in vis? No
   • Check if 1 + 3 = 4 is in vis? No
   • Add 1 to vis
   • State: vis = {1}, ans = {}

2. Process 2:

   • Check if 2 - 3 = -1 is in vis? No
   • Check if 2 + 3 = 5 is in vis? No
   • Add 2 to vis
   • State: vis = {1, 2}, ans = {}

3. Process 4:

   • Check if 4 - 3 = 1 is in vis? Yes! Form pair (1, 4), add 1 to ans
   • Check if 4 + 3 = 7 is in vis? No
   • Add 4 to vis
   • State: vis = {1, 2, 4}, ans = {1}

4. Process 4 (duplicate):

   • Check if 4 - 3 = 1 is in vis? Yes! Add 1 to ans (already exists)
   • Check if 4 + 3 = 7 is in vis? No
   • Add 4 to vis (already exists)
   • State: vis = {1, 2, 4}, ans = {1}

5. Process 3:

   • Check if 3 - 3 = 0 is in vis? No
   • Check if 3 + 3 = 6 is in vis? No
   • Add 3 to vis
   • State: vis = {1, 2, 3, 4}, ans = {1}

6. Process 3 (duplicate):

   • Check if 3 - 3 = 0 is in vis? No
   • Check if 3 + 3 = 6 is in vis? No
   • Add 3 to vis (already exists)
   • State: vis = {1, 2, 3, 4}, ans = {1}

7. Process 0:

   • Check if 0 - 3 = -3 is in vis? No
   • Check if 0 + 3 = 3 is in vis? Yes! Form pair (0, 3), add 0 to ans
   • Add 0 to vis
   • State: vis = {0, 1, 2, 3, 4}, ans = {0, 1}

8. Process 9:

   • Check if 9 - 3 = 6 is in vis? No
   • Check if 9 + 3 = 12 is in vis? No
   • Add 9 to vis
   • State: vis = {0, 1, 2, 3, 4, 9}, ans = {0, 1}

9. Process 2 (duplicate):

   • Check if 2 - 3 = -1 is in vis? No
   • Check if 2 + 3 = 5 is in vis? No
   • Add 2 to vis (already exists)
   • State: vis = {0, 1, 2, 3, 4, 9}, ans = {0, 1}

10. Process 3 (another duplicate):

    • Check if 3 - 3 = 0 is in vis? Yes! Form pair (0, 3), add 0 to ans (already exists)
    • Check if 3 + 3 = 6 is in vis? No
    • Add 3 to vis (already exists)
    • State: vis = {0, 1, 2, 3, 4, 9}, ans = {0, 1}

Final Result: The set ans contains {0, 1}, representing 2 unique k-diff pairs:

• Pair (0, 3) with difference 3
• Pair (1, 4) with difference 3

The answer is 2.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because the algorithm iterates through the array exactly once, and for each element, it performs constant-time operations: checking membership in sets (O(1) average case), adding elements to sets (O(1) average case), and performing arithmetic operations (x - k and x + k).

The space complexity is O(n). In the worst case, both the ans set and the vis set can contain up to n distinct elements. The vis set will contain all unique elements from the input array, which can be at most n elements. The ans set stores the smaller values of valid pairs, which in the worst case (when k = 0 and all elements are unique) can also be up to n elements. Therefore, the total space used is proportional to n.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Handling the k=0 Special Case Incorrectly

The Pitfall: When k = 0, we're looking for pairs where both numbers are the same (i.e., duplicates). The current solution has a subtle bug: it adds numbers to seen_numbers immediately, so when we encounter the same number again, it will find itself and incorrectly count pairs.

Example of the Bug: With nums = [1, 1, 1, 1] and k = 0:

• First 1: Nothing found, add to seen
• Second 1: Finds 1-0=1 and 1+0=1 in seen, adds 1 to unique_pairs
• Third 1: Again finds 1 in seen, but 1 is already in unique_pairs
• Fourth 1: Same as above

This seems to work, but consider nums = [1, 2, 1] and k = 0:

• Process 1: Nothing found
• Process 2: Nothing found
• Process 1: Finds 1 in seen, adds to unique_pairs

The issue is more apparent with the order-dependent nature when we have multiple distinct duplicates.

The Correct Approach: For k = 0, we should count how many numbers appear at least twice:

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        if k == 0:
            # Special case: count numbers that appear at least twice
            from collections import Counter
            freq = Counter(nums)
            return sum(1 for count in freq.values() if count >= 2)
      
        # For k > 0, use the original approach
        unique_pairs = set()
        seen_numbers = set()
      
        for current_num in nums:
            if current_num - k in seen_numbers:
                unique_pairs.add(current_num - k)
          
            if current_num + k in seen_numbers:
                unique_pairs.add(current_num)
          
            seen_numbers.add(current_num)
      
        return len(unique_pairs)

2. Negative k Values

The Pitfall: The problem states we need |nums[i] - nums[j]| == k, which means the absolute difference. Since absolute values are always non-negative, a negative k should return 0 immediately.

The Fix: Add validation at the beginning:

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        if k < 0:
            return 0
      
        # Rest of the solution...

3. Understanding Pair Uniqueness

The Pitfall: Developers might misunderstand what "unique pairs" means. The pairs (1, 3) and (3, 1) are considered the same pair since we're dealing with absolute difference. The solution correctly handles this by always storing the smaller value of each pair, but it's important to understand why this works.

Key Insight: By consistently storing the smaller value and checking both x - k and x + k, we ensure:

• Each valid pair is found exactly once (regardless of order)
• Duplicate pairs from different index combinations are automatically deduplicated