How do you solve K-diff Pairs in an Array on LeetCode?

K-diff Pairs in an Array (LeetCode #532) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a HashMap allows for efficient counting and checking of pairs.

What is the brute force solution for K-diff Pairs in an Array?

The brute force approach for K-diff Pairs in an Array is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every possible pair of numbers in the array to see if their absolute difference equals k. This is simple to understand but inefficient for larger arrays. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for K-diff Pairs in an Array?

Always clarify the problem statement and constraints before diving into coding. Discuss your thought process and approach with the interviewer. Consider edge cases, such as empty arrays or large values of k.

What are common mistakes when solving K-diff Pairs in an Array?

Not handling the case where k is 0 correctly. Forgetting to check for unique pairs when counting.

#532

K-diff Pairs in an Array

Medium

ArrayHash TableTwo PointersBinary SearchSortingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a HashMap to count occurrences of each number. This allows us to efficiently find pairs that meet the k-diff condition without checking every possible pair.

⚙️

Algorithm

6 steps

1Step 1: Create a HashMap to count occurrences of each number in the array.
2Step 2: Iterate through the keys in the HashMap.
3Step 3: For each key, check if k is 0. If so, count how many times the key appears (at least 2 times for a valid pair).
4Step 4: If k is greater than 0, check if the key + k exists in the HashMap.
5Step 5: If it exists, increment the count of unique pairs.
6Step 6: Return the count of unique pairs.

solution.py20 lines

1# Full working Python code
2
3def findPairs(nums, k):
4    if k < 0:
5        return 0
6    count = 0
7    num_count = {}
8    for num in nums:
9        num_count[num] = num_count.get(num, 0) + 1
10    for num in num_count:
11        if k == 0:
12            if num_count[num] > 1:
13                count += 1
14        else:
15            if num + k in num_count:
16                count += 1
17    return count
18
19# Example usage:
20print(findPairs([3,1,4,1,5], 2))  # Output: 2

ℹ

Complexity note: The time complexity is O(n) because we traverse the array once to count occurrences and then traverse the keys in the HashMap. The space complexity is O(n) due to the storage of counts in the HashMap.

1Using a HashMap allows for efficient counting and checking of pairs.
2When k is 0, we need to check for duplicates instead of pairs.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.