Watch 10 video solutions for K-diff Pairs in an Array, a medium level problem involving Array, Hash Table, Two Pointers. This walkthrough by Ayushi Sharma has 14,583 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.lengthi != j|nums[i] - nums[j]| == kNotice 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 <= 104-107 <= nums[i] <= 1070 <= k <= 107Problem Overview: You are given an integer array nums and an integer k. The task is to count the number of unique pairs (i, j) where the absolute difference between the numbers is exactly k. Duplicate values in the array can exist, but each pair should be counted only once.
Approach 1: HashMap Method (O(n) time, O(n) space)
This approach uses a frequency map built with a hash table. First iterate through the array and store the frequency of every number. Then iterate over the keys and check whether num + k exists in the map. If it does, you found a valid pair. The edge case occurs when k == 0; in that situation you only count numbers whose frequency is greater than 1 because the pair must consist of two equal values.
The key insight is constant-time lookup using hashing. Instead of checking every pair, you reduce the problem to checking whether the complementary value exists. Each lookup takes O(1) average time, so scanning all numbers gives overall O(n) time. This approach works well for unsorted arrays and is typically the most straightforward solution in interviews.
Approach 2: Sorting and Two Pointers (O(n log n) time, O(1) extra space)
This approach first sorts the array using a sorting algorithm, which costs O(n log n). After sorting, use the two pointers technique. Initialize two indices left and right. Move right forward to increase the difference and move left forward to decrease it. When nums[right] - nums[left] == k, record the pair and skip duplicates to ensure uniqueness.
The sorted order allows you to compare differences efficiently without a hash map. Because the pointers only move forward, the scan after sorting runs in O(n). This method is useful when memory usage must remain minimal or when the array is already sorted.
Recommended for interviews: The HashMap method is usually the expected optimal solution because it achieves O(n) time and handles duplicates cleanly with frequency counts. The sorting + two pointers approach is also common and demonstrates strong understanding of array scanning techniques. Mentioning both shows awareness of tradeoffs between time complexity and extra space.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Method | O(n) | O(n) | General case for unsorted arrays; fastest approach using constant-time hash lookups |
| Sorting + Two Pointers | O(n log n) | O(1) extra | When memory usage should be minimal or the array is already sorted |