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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

K-diff Pairs in an Array

Number: 532

Difficulty: Medium

Paid? No

Companies: Salesforce, Google, tcs, Amazon, Apple, Microsoft, Adobe, Uber, Yahoo

Problem Description

Given an integer array and an integer k, find the number of unique k-diff pairs in the array. A k-diff pair is defined as a pair of numbers (nums[i], nums[j]) such that:

  • 0 <= i, j < nums.length and i != j
  • The absolute difference between the pair equals k. Note that for a pair (a, b), the order does not matter and you should count each unique pair only once.

Key Insights

  • For k < 0, the answer is always 0 because the absolute difference cannot be negative.
  • When k is 0, you are looking for numbers that appear at least twice.
  • For k > 0, it is efficient to use a hash set or a hash map to check if each number's complement (number + k) exists.
  • Uniqueness is ensured by processing each number only once from the set of unique numbers.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array since we iterate over the array and then over the unique numbers. Space Complexity: O(n), for storing the frequency count or the unique elements in a hash map or hash set.

Solution

The solution first checks if k is negative, returning 0 immediately if true. For k equals 0, we count numbers that appear more than once using a frequency map. For k greater than 0, a set of unique numbers is created and for each number, we check if (number + k) is also present in the set. Each valid case contributes to the result count, ensuring that only unique pairs are considered.

Code Solutions

# Define a function to count k-diff pairs in the array.
def find_pairs(nums, k):
    # If k is negative, return 0 as absolute difference can't be negative.
    if k < 0:
        return 0
    
    count = 0
    
    # k == 0: Need to find numbers that appear more than once.
    if k == 0:
        # Create a frequency map for nums.
        freq = {}
        for num in nums:
            freq[num] = freq.get(num, 0) + 1
        # Count numbers with frequency greater than 1.
        for val in freq.values():
            if val > 1:
                count += 1
    else:
        # k > 0: Use a set to check for the existence of each number's complement.
        unique_nums = set(nums)
        for num in unique_nums:
            if num + k in unique_nums:
                count += 1
    return count

# Example usage:
# print(find_pairs([3,1,4,1,5], 2))  # Expected output: 2
← Back to All Questions