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.
This approach uses a HashMap to track the frequency of each element in the array. For each unique element, we will check if there's another element that can form a k-diff pair with it. When k is zero, we need to check if there are duplicates present in the list.
The code uses a frequency map stored as an array from -10000 to 10000 to count occurrences of each number. For a k-difference, if k is zero, we count pairs from duplicates. Otherwise, we look for the presence of the number plus k.
Time Complexity: O(n) because we iterate over the array and then over the hashmap that is bounded by a constant size. Space Complexity: O(n) to store the frequency map.
This approach involves sorting the array initially, then using two pointers to determine unique k-diff pairs. The array being sorted helps us efficiently reduce potential pair checks, and ensure pairs are considered only once.
After sorting, two pointers start from the beginning. We adjust pointers depending on the difference relative to k. Duplicates are handled by skipping same values.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) if disregard input.
Since k is a fixed value, we can use a hash table ans to record the smaller value of the pairs, which allows us to determine the larger value. Finally, we return the size of ans as the answer.
We traverse the array nums. For the current number x, we use a hash table vis to record all the numbers that have been traversed. If x-k is in vis, we add x-k to ans. If x+k is in vis, we add x to ans. Then, we add x to vis. Continue traversing the array nums until the end.
Finally, we return the size of ans as the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
| Approach | Complexity |
|---|---|
| HashMap Method | Time Complexity: O(n) because we iterate over the array and then over the hashmap that is bounded by a constant size. Space Complexity: O(n) to store the frequency map. |
| Sorting and Two Pointers | Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) if disregard input. |
| Hash Table | — |
| 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 |
K diff Pairs in an Array | Leetcode 532 | Arrays • Ayushi Sharma • 14,583 views views
Watch 9 more video solutions →Practice K-diff Pairs in an Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor