532. K-diff Pairs in an Array

MediumArrayHash TableTwo PointersBinary SearchSorting
Leetcode Link

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:

  1. 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.

  2. ans (answer): This set stores the unique elements that form part of a pair with the current element that satisfies the k-diff condition.

For each value v in nums, we perform two checks:

  • First, we check if v - k is in vis. If it is, it means we've already seen an element which can form a pair with v that has a difference of k (since v - (v - k) = k). We add v - k to the ans set to account for this unique pair.

  • Secondly, we check if v + k is in vis. If it is, it indicates that v can form a pair with this previously seen element satisfying the k-diff condition. In this case, we add v to the ans 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

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, and ans to store the unique values that form valid k-diff pairs.

  • We then enter a loop over each value v in nums. For each v, we perform two important checks:

    1. We check if v - k is in vis. 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 and v is exactly k. We then add v - k to the ans set, which ensures we're counting the lower number of the pair only once.
    2. We also check if v + k is in vis for the same reasons as above, but this time if the condition holds true, we add v to the ans set, considering v as the higher number in the pair.

  • Each iteration also involves adding v to vis 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 in ans. Finally, the solution function returns the size of ans, which is the count of all unique k-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).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Example Walkthrough

Let's use the array nums = [3, 1, 4, 1, 5] and k = 2 to illustrate the solution approach:

  1. Initialize two empty sets: vis = set() and ans = set().

  2. Start iterating through the array nums:

    • Take the first element v = 3. Since vis is empty, there's nothing to check, so simply add 3 to vis.
    • The next element is v = 1. Check 1 - 2 (which is -1) and 1 + 2 (which is 3) against the vis set. The value 3 is in vis, thus we can form a pair (1, 3). Add 1 to the ans set and 1 to the vis set.
    • Continue with v = 4, and check 4 - 2 = 2 and 4 + 2 = 6 against vis. Neither is in the set, so simply add 4 to vis.
    • Now v = 1 again. As 1 is already in vis, 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. Check 5 - 2 = 3 and 5 + 2 = 7 against vis. The value 3 is there; therefore, the pair (3, 5) can be formed. Add 3 to the ans set.

  3. Final sets after iteration:

    • vis = {3, 1, 4, 5}
    • ans = {1, 3}. Notice we do not have 5 in ans because we only add the smaller value of the pair to the ans set.

  4. Count the elements in the ans set, which gives us 2. Thus, there are 2 distinct pairs with an absolute difference of 2: 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

In a binary min heap, the minimum element can be found in:

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement recursion?

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 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 Two pointers is a common interview technique

Binary Search Speedrun

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

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

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ