K-diff Pairs in an Array

LeetCode 532 | Difficulty: Medium

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]), where the following are true:

- `0 <= i, j < nums.length`

- `i != j`

- `|nums[i] - nums[j]| == k`

Notice that |val| denotes the absolute value of val.

Example 1:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

Input: nums = [1,2,3,4,5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

Input: nums = [1,3,1,5,4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Constraints:

- `1 <= nums.length <= 10^4`

- `-10^7 <= nums[i] <= 10^7`

- `0 <= k <= 10^7`

Topics: Array, Hash Table, Two Pointers, Binary Search, Sorting

---

Approach

Two Pointers

Use two pointers to traverse the array, reducing the search space at each step. This avoids the need for nested loops, bringing complexity from O(n²) to O(n) or O(n log n) if sorting is involved.

When to use

Array is sorted or can be sorted, and you need to find pairs/triplets that satisfy a condition.

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 161 ms)

Metric	Value
Runtime	161 ms
Memory	40.6 MB
Date	2022-02-07

Solution

public class Solution {
    public int FindPairs(int[] nums, int k)
{
    if(k<0) return 0;
    Dictionary<int, int> d = new Dictionary<int, int>();
    int count = 0;
    
    foreach (var num in nums)
    {
        if (d.ContainsKey(num))
        {
            if (k == 0 && d[num] == 1) count++;
            d[num]++;
        }
        else
        {
            if(d.ContainsKey(num-k)) count++;
            if(d.ContainsKey(num+k)) count++;
            d.Add(num, 1);
        }
    }
    
    
    return count;
}
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Binary Search	$O(log n)$	$O(1)$
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Ask: "Can I sort the array?" — Sorting often enables two-pointer techniques.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• Precisely define what the left and right boundaries represent, and the loop invariant.