We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

K-diff Pairs in an Array

Difficulty: Medium

Problem Description

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

Key Insights

  • A pair (a, b) is considered unique if a != b and both are counted only once.
  • If k is 0, we need to count elements that appear more than once.
  • For k > 0, we can find pairs by checking for the existence of (num + k) for each num in the array.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can utilize a hash table (or set) to store the frequency of each number in the array. We then iterate through the unique numbers and check for the existence of their complements (num + k for k > 0, and duplicates for k = 0) in the hash table. This allows us to efficiently count the unique k-diff pairs.

Code Solutions

def findPairs(nums, k):
    if k < 0:
        return 0
    
    count = 0
    num_count = {}
    
    for num in nums:
        num_count[num] = num_count.get(num, 0) + 1
    
    for num in num_count:
        if k == 0:
            if num_count[num] > 1:
                count += 1
        else:
            if num + k in num_count:
                count += 1
    
    return count
← Back to All Questions