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 <= 107This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) if disregard input.
| 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. |
K Inverse Pairs Array - Leetcode 629 - Python • NeetCodeIO • 17,603 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