K-diff Pairs in an Array
MedPrompt
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]| == 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 <= 104-107 <= nums[i] <= 1070 <= k <= 107
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through all possible pairs of elements in the array and checks if their absolute difference is equal to k. To ensure that we only count unique pairs, a Set is used to store the pairs found in a canonical form.
Algorithm
- Initialize an empty
HashSet<String>calleduniquePairsto store the unique pairs. - Iterate through the array with a pointer
ifrom0ton-1. - Inside this loop, iterate with another pointer
jfromi+1ton-1. - For each pair
(nums[i], nums[j]), check ifMath.abs(nums[i] - nums[j]) == k. - If the condition is true, form a canonical string representation of the pair, e.g.,
Math.min(nums[i], nums[j]) + "," + Math.max(nums[i], nums[j]), and add it to theuniquePairsset. - After the loops complete, return the size of
uniquePairs.
Walkthrough
We can solve this problem by checking every possible pair of numbers in the array. We use two nested loops to generate these pairs.
For each pair (nums[i], nums[j]) where i < j, we calculate the absolute difference |nums[i] - nums[j]|.
If the difference equals k, we have found a k-diff pair. However, the problem asks for unique pairs. For example, in [1, 3, 1, 3] with k=2, the pair (1, 3) should be counted only once.
To handle this, we store the found pairs in a Set. To treat (a, b) and (b, a) as the same pair, we store them in a canonical order, for instance, (min(a, b), max(a, b)). A Set of Pair objects or a Set of String representations like "min_val,max_val" can be used.
The final result is the size of this set.
import java.util.HashSet;import java.util.Set; class Solution { public int findPairs(int[] nums, int k) { if (k < 0) { return 0; } Set<String> uniquePairs = new HashSet<>(); for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (Math.abs(nums[i] - nums[j]) == k) { int min = Math.min(nums[i], nums[j]); int max = Math.max(nums[i], nums[j]); uniquePairs.add(min + "," + max); } } } return uniquePairs.size(); }}Complexity
Time
O(N^2), where N is the number of elements in `nums`. The two nested loops result in a quadratic time complexity as we compare every element with every other element.
Space
O(P), where P is the number of unique pairs. In the worst-case scenario, P can be up to N, so the space complexity is O(N).
Trade-offs
Pros
Simple to understand and implement.
Cons
Inefficient for large input arrays due to its O(N^2) time complexity, which will likely result in a 'Time Limit Exceeded' error on most platforms.
Solutions
Solution
class Solution {public int findPairs(int[] nums, int k) { Set<Integer> vis = new HashSet<>(); Set<Integer> ans = new HashSet<>(); for (int v : nums) { if (vis.contains(v - k)) { ans.add(v - k); } if (vis.contains(v + k)) { ans.add(v); } vis.add(v); } return ans.size(); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.