algoadvance

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

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

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), (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

Clarifying Questions

1. Can nums contain duplicate elements?
   • Yes, nums can contain duplicates.
2. What should be returned if there are no such k-diff pairs?
   • The function should return 0.
3. Is the order of the pairs important?
   • No, the order does not matter, just the count of unique pairs.
4. Can k be zero?
   • Yes, and in that case, we look for elements that appear at least twice.

Strategy

1. Handling k == 0:
   • We need to count elements that appear more than once.
2. Handling k > 0:
   • We use a set to keep track of elements we have seen so far and check if the complement (num + k) or (num - k) exists in the set.

Code

Let’s implement the above strategy:

def findPairs(nums, k):
    if k < 0:
        return 0
    
    seen = set()
    diff_pairs = set()
    
    for num in nums:
        if k == 0:
            if num in seen:
                diff_pairs.add(num)
        else:
            if num + k in seen:
                diff_pairs.add((num, num + k))
            if num - k in seen:
                diff_pairs.add((num - k, num))
        seen.add(num)
    
    return len(diff_pairs)

# Example usage:
print(findPairs([3, 1, 4, 1, 5], 2))  # Output: 2
print(findPairs([1, 2, 3, 4, 5], 1))  # Output: 4
print(findPairs([1, 3, 1, 5, 4], 0))  # Output: 1

Time Complexity

• Space Complexity: O(n)
  • We use a set to keep track of the numbers seen, and another set to track the pairs, both contributing to O(n) space.
• Time Complexity: O(n)
  • We iterate through the list once, and set operations (add, check membership) are average O(1), leading to O(n) overall.

This approach is efficient given the constraints and should work within the limits for typical input sizes.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?