532. K-diff Pairs in an Array
Model: qwen3.5:9b
Topics: Array,Two Pointers
FAANG asked: 1
Acceptance rate: 35.5%
Problem Breakdown
We are given an integer array nums and a target difference k. We need to return the number of unique pairs (a, b) such that both elements exist in the array at different indices (i != j) and their absolute difference is exactly k.
Key constraints:
- Unique Pairs: The pair
{3, 5}is identical to{5, 3}. We count unique value combinations, not index permutations. - Index Constraint: Even if values are the same (e.g.,
[1, 1]), they must be at different indices (i != j). This implies fork=0, we need duplicates in the array to form a valid pair. - Values: Integers can be negative or large ().
Intuition
A brute-force solution would use nested loops checking every index combination where . This is . Given the constraint nums.length <= 10^4, an approach might hit Time Limit Exceeded (TLE).
We need to optimize lookups. Since we care about values and their existence, a Hash Map (Frequency Counter) allows us to check if a number exists in time on average.
The core insight is that for any value num present in the array:
- If
k > 0: We only need to look forward or backward once per unique number to avoid double counting pairs (e.g., checking ifnum + kexists covers both(num, num+k)and(num+k, num)). - If
k == 0: The pair is(x, x). This requires the valuexto appear at least twice in the array.
Approach
- Frequency Map: Create a hash map (Counter) storing every number in
numsand its frequency count. - Iterate Unique Elements: Iterate through the unique keys of this map. Iterating over values is safer than indices to handle duplicates naturally, but we must iterate only once per distinct value found.
- Check Conditions:
- If
k > 0: Check ifnum + kexists in our frequency map. If it does, increment the result counter. We do not checknum - kbecause that would double count pairs (e.g., checking for both(1,3)and(3,5)when iterating keys). - If
k == 0: Check if the current number’s frequency is greater than or equal to 2 (count[num] >= 2). This ensures we have two distinct indices with that value.
- If
- Return: Return the accumulated count.
Complexity Analysis
- Time Complexity: . Building the Counter takes one pass (). Iterating through unique keys takes at most iterations (worst case all elements are unique), and map lookups are . Total is linear.
- Space Complexity: . We store every element in a hash map for the frequency count.
Solution
from collections import Counter
from typing import List
class Solution:
def findPairs(self, nums: List[int], k: int) -> int:
# Build frequency map to handle duplicates and O(1) lookups
freq = Counter(nums)
count = 0
# Iterate over unique numbers only.
# We use .keys() because we want to process each distinct value once.
for num in freq.keys():
if k > 0:
# If k is positive, check if the target (num + k) exists.
# Checking both directions would double count pairs like {1,3} and {3,1}.
if (num + k) in freq:
count += 1
else:
# Special case for k = 0.
# We need at least two occurrences of the same number to form a pair with different indices.
if freq[num] >= 2:
count += 1
return count
Edge Cases Handled
- k=0: The code explicitly checks
freq[num] >= 2. If[1,3,1,5,4]andk=0, only the number1has frequency , so it counts as one pair. Single occurrences are ignored for . - Negative Numbers: Python’s hash map handles negative integers correctly without special logic adjustments.
- Empty Array / No Pairs: The loop simply won’t find matches, returning
0, which is correct behavior (though constraints say length ). - Duplicates in Input: Handled by the frequency counter; we iterate unique keys to ensure pair uniqueness based on values.