532. K-diff Pairs in an Array - Detailed Explanation

Problem Statement

Given an integer array nums and an integer k, a k-diff pair is a pair of integers (nums[i], nums[j]) such that:

• 0 ≤ i < j < nums.length
• |nums[i] - nums[j]| == k

Return the number of unique k-diff pairs in the array. Two pairs (a,b) and (c,d) are considered the same if they contain the same two values, regardless of order or indices.

Examples

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: The unique pairs are (1,3) and (3,5).

Input: nums = [1,2,3,4,5], k = 1
Output: 4
Explanation: Pairs are (1,2),(2,3),(3,4),(4,5).

Input: nums = [1,3,1,5,4], k = 0
Output: 1
Explanation: Only (1,1) is valid since 1 appears at least twice.

Constraints

• 1 ≤ nums.length ≤ 10⁴
• -10⁷ ≤ nums[i] ≤ 10⁷
• 0 ≤ k ≤ 10⁷

Hints

1. If k < 0, no pairs can satisfy |a - b| = k.
2. When k == 0, you’re looking for values that appear at least twice.
3. When k > 0, you want to count each value x for which x + k also appears.

Approaches

Approach 1: HashSet / Frequency Map (O(n) time, O(n) space)

1. If k < 0, immediately return 0.
2. Build a frequency map freq of all values in nums.
3. If k == 0, count how many values have freq[v] ≥ 2.
4. If k > 0, for each unique value v in freq, check if v + k exists; count one for each match.
5. Return the count.

Why it works:

• For k > 0, each distinct v forms exactly one pair (v, v+k).
• For k == 0, each value with frequency ≥2 yields exactly one distinct pair (v, v).

Approach 2: Two‑Pointer on Sorted Array (O(n log n) time, O(1) extra space)

1. Sort nums.
2. Use two pointers i and j = 1.
3. While i < nums.length and j < nums.length:
   • If i == j or nums[j] - nums[i] < k, increment j.
   • Else if nums[j] - nums[i] > k, increment i.
   • Else (nums[j] - nums[i] == k):
     • Count one unique pair; increment both i and j past any duplicates to avoid recounting.
4. Return the total count.

Why it works:

• Sorting groups duplicates and lets the difference test run in linear time with two pointers.
• Skipping over duplicates ensures uniqueness.

Step‑by‑Step Walkthrough (HashSet Approach)

nums = [3,1,4,1,5], k = 2
freq = {1:2, 3:1, 4:1, 5:1}

k > 0, so for each v:
  v=1 → check 1+2=3 in freq? yes → count=1
  v=3 → check 3+2=5? yes → count=2
  v=4 → check 6? no
  v=5 → check 7? no

Return 2

Complexity Analysis

• Time:
  • HashSet approach: O(n) to build freq + O(n) to scan keys → O(n).
  • Two‑pointer approach: O(n log n) to sort + O(n) scan → O(n log n).
• Space:
  • HashSet: O(n) for the freq map.
  • Two‑pointer: O(1) extra (sorting may use O(n) internally).

Python Code