532. K-diff Pairs in an Array
Problem Description
The challenge is to count the distinctive pairs (nums[i], nums[j])
in a given array of integers nums
where each pair meets certain criteria. These criteria are that i
and j
are distinct indices in the array (they are not the same), and the absolute difference between the values at these indices is exactly k
. The absolute difference is denoted as |nums[i] - nums[j]|
and must equal k
. A further constraint is that each pair must be unique; that is, even if multiple pairs have the same numbers, they should only be counted once.
Intuition
The solution rests on using a set data structure, which naturally only stores unique elements, thus eliminating duplicate pairs. The main idea is to iterate through nums
and at each step determine if there is a corresponding value that, when added or subtracted by k
, matches the current element. Two sets are used:
-
vis
(visited): This set keeps track of the elements we have seen so far. As we traverse the array, we add elements to this set. -
ans
(answer): This set stores the unique elements that form part of a pair with the current element that satisfies thek-diff
condition.
For each value v
in nums
, we perform two checks:
-
First, we check if
v - k
is invis
. If it is, it means we've already seen an element which can form a pair withv
that has a difference ofk
(sincev - (v - k) = k
). We addv - k
to theans
set to account for this unique pair. -
Secondly, we check if
v + k
is invis
. If it is, it indicates thatv
can form a pair with this previously seen element satisfying thek-diff
condition. In this case, we addv
to theans
set.
After completing the loop, the size of the ans
set reflects the total count of unique k-diff
pairs, because we've only stored one element from each unique pair, and duplicates are not allowed by the set property. This is the number we return.
Learn more about Two Pointers, Binary Search and Sorting patterns.
Solution Approach
The implementation makes use of Python sets and straightforward conditional statements within a loop. Here's a step-by-step breakdown:
-
We first define two sets:
vis
to keep track of the integers we have encountered so far as we iterate through the array, andans
to store the unique values that form validk-diff
pairs. -
We then enter a loop over each value
v
innums
. For eachv
, we perform two important checks:- We check if
v - k
is invis
. Since set elements are unique, this check is constant time on average,O(1)
. If this condition is true, it means there is another number in the array such that the difference between it andv
is exactlyk
. We then addv - k
to theans
set, which ensures we're counting the lower number of the pair only once. - We also check if
v + k
is invis
for the same reasons as above, but this time if the condition holds true, we addv
to theans
set, consideringv
as the higher number in the pair.
- We check if
-
Each iteration also involves adding
v
tovis
set, thus expanding the set of seen numbers and preparing for the subsequent iterations. -
After the loop finishes, we have accumulated all unique numbers that can form
k-diff
pairs inans
. Finally, the solution function returns the size ofans
, which is the count of all uniquek-diff
pairs in the array.
The algorithm's time complexity is O(n)
where n
is the number of elements in nums
, because it goes through the list once and set operations like adding and checking for existence are O(1)
on average. The space complexity is also O(n)
since at most, the vis
and ans
sets can grow to the size of the entire array in the worst-case scenario (no duplicates).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use the array nums = [3, 1, 4, 1, 5]
and k = 2
to illustrate the solution approach:
-
Initialize two empty sets:
vis = set()
andans = set()
. -
Start iterating through the array
nums
:- Take the first element
v = 3
. Sincevis
is empty, there's nothing to check, so simply add3
tovis
. - The next element is
v = 1
. Check1 - 2
(which is-1
) and1 + 2
(which is3
) against thevis
set. The value3
is invis
, thus we can form a pair(1, 3)
. Add1
to theans
set and1
to thevis
set. - Continue with
v = 4
, and check4 - 2 = 2
and4 + 2 = 6
againstvis
. Neither is in the set, so simply add4
tovis
. - Now
v = 1
again. As1
is already invis
, no new pairs can be formed that haven't already been counted. Therefore, continue to the next number without making any changes. - Lastly,
v = 5
. Check5 - 2 = 3
and5 + 2 = 7
againstvis
. The value3
is there; therefore, the pair(3, 5)
can be formed. Add3
to theans
set.
- Take the first element
-
Final sets after iteration:
vis = {3, 1, 4, 5}
ans = {1, 3}
. Notice we do not have5
inans
because we only add the smaller value of the pair to theans
set.
-
Count the elements in the
ans
set, which gives us2
. Thus, there are 2 distinct pairs with an absolute difference of2
: these are(1, 3)
and(3, 5)
.
This walkthrough demonstrates the implementation of the solution approach where we end up with the distinct pairs and the count of these unique pairs is the final answer. The time and space complexity for this approach is linear with respect to the number of elements in the nums
array.
Solution Implementation
1from typing import List
2
3class Solution:
4 def findPairs(self, nums: List[int], k: int) -> int:
5 # Set to keep track of unique numbers seen so far.
6 visited = set()
7
8 # Set to keep track of unique pairs that satisfy the condition.
9 # Pairs are identified by the smaller number in the pair.
10 unique_pairs = set()
11
12 for number in nums:
13 # If the current number minus k was already seen,
14 # add the smaller number of the pair (number - k) to the set of unique pairs.
15 if number - k in visited:
16 unique_pairs.add(number - k)
17
18 # If the current number plus k was already seen,
19 # add the current number to the set of unique pairs as it
20 # represents the smaller number in the pair (current number, number + k).
21 if number + k in visited:
22 unique_pairs.add(number)
23
24 # Mark the current number as seen.
25 visited.add(number)
26
27 # The number of unique pairs is the size of the set.
28 return len(unique_pairs)
29
30# Example usage:
31# sol = Solution()
32# print(sol.findPairs([3, 1, 4, 1, 5], 2)) # Output: 2
33
1class Solution {
2 public int findPairs(int[] nums, int k) {
3 // Initialize a hash set to store the unique elements we've seen
4 Set<Integer> seen = new HashSet<>();
5 // Initialize a hash set to store the unique pairs we've found
6 Set<Integer> uniquePairs = new HashSet<>();
7
8 // Loop through all elements in the array
9 for (int num : nums) {
10 // Check if there's a number in the array such that num - k is already in 'seen'
11 if (seen.contains(num - k)) {
12 // If so, add the smaller number of the pair to 'uniquePairs'
13 uniquePairs.add(num - k);
14 }
15 // Check if there's a number in the array such that num + k is already in 'seen'
16 if (seen.contains(num + k)) {
17 // If so, add the current number to 'uniquePairs'
18 uniquePairs.add(num);
19 }
20 // Add the current number to the set of seen numbers
21 seen.add(num);
22 }
23
24 // The number of unique pairs that have a difference of k is the size of 'uniquePairs'
25 return uniquePairs.size();
26 }
27}
28
1class Solution {
2public:
3 int findPairs(vector<int>& nums, int k) {
4 unordered_set<int> visited; // Set to keep track of visited numbers
5 unordered_set<int> foundPairs; // Set to store unique pairs that satisfy the condition
6
7 for (int& number : nums) { // Iterate over each number in the given array
8 // Check if there's a number in visited set such that the difference between
9 // the current number and that number equals k
10 if (visited.count(number - k)) {
11 // If such a number is found, insert the smaller number of the pair into foundPairs
12 foundPairs.insert(number - k);
13 }
14
15 // Check if there's a number in visited set such that the difference between
16 // that number and the current number equals k
17 if (visited.count(number + k)) {
18 // If such a number is found, insert the current number into foundPairs
19 foundPairs.insert(number);
20 }
21
22 // Mark the current number as visited
23 visited.insert(number);
24 }
25
26 // The result is the number of unique pairs found, which is the size of foundPairs set
27 return foundPairs.size();
28 }
29};
30
1let visited = new Set<number>(); // Set to keep track of visited numbers
2let foundPairs = new Set<number>(); // Set to store unique indices whose elements satisfy the condition
3
4function findPairs(nums: number[], k: number): number {
5 visited.clear(); // Clear sets before use
6 foundPairs.clear();
7
8 // Iterate over each number in the given array nums
9 nums.forEach((number) => {
10 // Check if there is a number in the visited set such that
11 // the difference between the current number and that number equals k
12 if (visited.has(number - k)) {
13 // If such a number is found, insert the smaller number of the pair into foundPairs
14 foundPairs.add(number - k);
15 }
16
17 // Check if there is a number in the visited set such that
18 // the difference between that number and the current number equals k
19 if (visited.has(number + k)) {
20 // If such a number is found, insert the current number into foundPairs
21 foundPairs.add(number);
22 }
23
24 // Mark the current number as visited
25 visited.add(number);
26 });
27
28 // The result is the number of unique pairs found, which is the size of the foundPairs set
29 return foundPairs.size();
30}
31
32// Example usage:
33// let numPairs = findPairs([3, 1, 4, 1, 5], 2);
34// console.log(numPairs); // Should log the number of unique pairs found with difference k
35
Time and Space Complexity
The provided Python code entails iterating through the given list of numbers and checking for the existence of certain values within a set. Here is an analysis of its time complexity and space complexity:
Time Complexity:
The time complexity is O(n)
, where n
is the length of the input list nums
. This is because the code consists of a single loop that iterates through each element in the list exactly once. The operations within the loop (checking for existence in a set, adding to a set, and adding to another set) all have constant time complexity, i.e., O(1)
.
Space Complexity:
The space complexity of the code is also O(n)
. Two sets, vis
and ans
, are used to keep track of the numbers that have been visited and the unique pairs that satisfy the condition, respectively. In the worst-case scenario, the vis
set could potentially contain all the elements from the input list nums
, resulting in O(n)
space usage. The ans
set might contain at most min(n, n/2)
elements, since it stores the smaller value of each pair, leading to O(n)
space requirement as well. Hence, the overall space complexity is O(n)
due to these two sets.
Therefore, the complete complexity analysis of the code snippet is O(n)
time and O(n)
space.
Learn more about how to find time and space complexity quickly using problem constraints.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Want a Structured Path to Master System Design Too? Donāt Miss This!