2006. Count Number of Pairs With Absolute Difference K

EasyArrayHash TableCounting

Problem Description

The goal of this problem is to find the total number of unique pairs (i, j) in a given integer array nums wherein the absolute difference between the numbers at positions i and j is exactly k. The condition is that i should be less than j, which implies that we're looking at pairs where the first element comes before the second element in the array order. The absolute value here means that if the result of the subtraction is negative, we consider its positive value instead.

To put it simply, we iterate over the array, and for each element, we check how many elements that come after it have a difference of k.

Intuition

The solution makes use of a hash map to efficiently track the counts of numbers we have seen so far. This is a common strategy in problems where we need to quickly access the count or existence of elements based on their value, which is often referred to as the frequency map pattern.

When we look at an element num in the array, there are two numbers that could form a valid pair with it: num + k and num - k. For each num, the solution checks if num + k and num - k have been seen before (i.e., they are in the hash map). If they are, it adds the count of how many times they've been seen to our answer because each of those instances forms a valid pair with our current num.

We then update the count of the current num in the hash map, increasing it by 1, to keep track of how many times it has been seen for future iterations.

This approach works because by increasing the count of the current number after checking for pairs, we ensure that we only count pairs where i < j. Hence, we are systematically building and utilizing a frequency map to keep count of potential complements for every element as we iterate through the array.

Solution Approach

The solution makes use of the Counter data structure from Python's collections module, which is essentially a hash map (or dictionary) designed for counting hashable objects. The keys in this hash map are the distinct elements from nums and the values are the counts of how many times they appear. Here's how the solution is implemented:

Initialize a variable ans to count the number of valid pairs found. It starts at 0.
Create a Counter object cnt which will store the frequency of each number encountered in nums.
Iterate over each number num in the nums array:
- For the current number num, check if num - k is in the counter. If it is, it means there are numbers previously seen that, when subtracted from num, give k. We add the count of num - k to ans.
- Similarly, check if num + k is in the counter. If it is, add the count of num + k to ans. This counts the cases where the previous numbers were smaller than num and had a difference of k.
- After checking for pairs, increment the count of num in the cnt Counter to account for its occurrence.
After finishing the loop, return the value of ans, which now contains the total number of valid pairs.

The algorithm operates in O(n) time complexity, where n is the number of elements in nums. This is because the operation of checking and updating the counter is O(1), and we only iterate through the array once.

The key algorithms and data structures used in this solution include:

Looping through Arrays: The for loop iterates through each element in nums to check for possible pairs.
Hash Map (Counter): Utilizes the Counter data structure to store and access frequency of elements in constant time (O(1)).
Incremental Counting: Maintains the count of valid pairs in variable ans as the array is processed.

By employing the Counter, we are able to maintain a running total of pair counts as the nums array is iterated over, thus avoiding the need for nested loops that would significantly increase the computational complexity (potential O(n^2) if using brute force approach).

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's assume we are given a small integer array nums = [1, 5, 3, 4, 2] and we must find the number of unique pairs (i, j) such that the absolute difference between nums[i] and nums[j] is k = 2. Following the solution approach:

Initialize ans to 0 as no pairs have been counted yet.
Create a Counter object cnt which is initially empty.

Now, let's iterate over each number num in nums:

For the first number 1, we check if 1 - 2 (which is -1) and 1 + 2 (which is 3) are in the counter. Neither are because the counter is empty, so we don't change ans. Then we add 1 to the counter, so cnt becomes Counter({1: 1}).
Moving to the second number 5, we look for 5 - 2 (equals 3) and 5 + 2 (equals 7). Neither are in the counter, so ans remains 0. Then we update cnt, now Counter({1: 1, 5: 1}).
Next, 3 is checked against the counter. We look for 3 - 2 (which is 1) and 3 + 2 (which is 5). We find 1 in the counter with a count of 1. So we increment ans by 1. We do not find 5 because we only count pairs where i < j, to avoid re-counting. Update the counter with 3, now Counter({1: 1, 5: 1, 3: 1}).
For 4, we do the same. We find 4 - 2 = 2 is not in the counter but 4 + 2 = 6 isn't in the counter either. So, ans is still 1. Update cnt to Counter({1: 1, 5: 1, 3: 1, 4: 1}).
Lastly, for 2, 2 - 2 equals 0 (not present in the counter) but 2 + 2 equals 4 which is in the counter with a count of 1. Thus, we increment ans by 1 making it 2. Final update to the counter leaves it as Counter({1: 1, 5: 1, 3: 1, 4: 1, 2: 1}).

After finishing the iteration, ans is 2, implying there are two unique pairs where the difference is exactly k = 2: these are (1, 3) and (2, 4) based on the original positions in the array (nums[0] and nums[2], nums[4] and nums[3] respectively).

The solution has efficiently counted the pairs without re-counting or using nested loops, showcasing the advantage of using a Counter to keep track of frequencies and significantly simplifying the search process for complements that result in the required difference k.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def countKDifference(self, nums: List[int], k: int) -> int:
5        # Initialize the answer to 0
6        pair_count = 0
7
8        # Initialize the counter that will keep track of the occurrences of elements
9        num_counter = Counter()
10
11        # Loop through each number in the input list
12        for num in nums:
13            # For the current number, add the count of the number that is 'k' less and 'k' more than the current number
14            # This is because we're looking for pairs that have a difference of k
15            pair_count += num_counter[num - k] + num_counter[num + k]
16
17            # Increment the count of the current number in our counter
18            num_counter[num] += 1
19
20        # Return the total count of pairs that have a difference of k
21        return pair_count
22

1class Solution {
2  
3    /**
4     * Counts the number of unique pairs in the array with a difference of k.
5     *
6     * @param nums The array of integers to process.
7     * @param k The difference to look for between pairs of numbers.
8     * @return The count of pairs with the specified difference.
9     */
10    public int countKDifference(int[] nums, int k) {
11        // Initialize answer to 0 to keep count of pairs
12        int countPairs = 0;
13      
14        // Array to store counts of each number, considering the constraint 1 <= nums[i] <= 100
15        int[] countNumbers = new int[110];
16      
17        // Iterate through each number in the input array
18        for (int num : nums) {
19
20            // If current number minus k is non-negative, add the count of that number to the total
21            // as it represents a pair where num - (num - k) = k
22            if (num >= k) {
23                countPairs += countNumbers[num - k];
24            }
25
26            // If current number plus k is within the allowed range (less than or equal to 100),
27            // add the count of that number to the total as it represents a pair where (num + k) - num = k
28            if (num + k <= 100) {
29                countPairs += countNumbers[num + k];
30            }
31
32            // Increment the count for the current number
33            ++countNumbers[num];
34        }
35
36        // Return total count of pairs
37        return countPairs;
38    }
39}
40

1class Solution {
2public:
3    int countKDifference(vector<int>& nums, int k) {
4        int countPairs = 0; // Initialize a variable to store the number of pairs
5        int countNumbers[110] = {}; // Initialize an array to count occurrences of numbers
6
7        // Iterate through each number in the input vector
8        for (int number : nums) {
9            // Check if the (number - k) is non-negative as array indices cannot be negative
10            if (number >= k) {
11                // Add the count of (number - k) to the number of pairs as they satisfy the condition of having a difference of k
12                countPairs += countNumbers[number - k];
13            }
14            // Check if the (number + k) is within the bounds of the countNumbers array
15            if (number + k <= 100) {
16                // Add the count of (number + k) to the number of pairs as they satisfy the condition of having a difference of k
17                countPairs += countNumbers[number + k];
18            }
19            // Increment the count of the current number
20            ++countNumbers[number];
21        }
22
23        // Return the total number of pairs with a difference of k
24        return countPairs;
25    }
26};
27

1function countKDifference(nums: number[], k: number): number {
2    let countPairs = 0; // Initialize count of pairs with difference k
3    let numberFrequency = new Map<number, number>(); // Initialize a map to keep track of frequencies of numbers
4
5    // Iterate over each number in the array
6    for (let num of nums) {
7        // Increment countPairs by the count of numbers that are k less than the current number (if any)
8        countPairs += (numberFrequency.get(num - k) || 0);
9        // Increment countPairs by the count of numbers that are k more than the current number (if any)
10        countPairs += (numberFrequency.get(num + k) || 0);
11      
12        // Update the frequency map for the current number
13        numberFrequency.set(num, (numberFrequency.get(num) || 0) + 1);
14    }
15
16    // Return the total count of pairs with difference k
17    return countPairs;
18}
19

Time and Space Complexity

The given Python code implements a function countKDifference to count pairs of elements in an array nums that have a difference of k.

Time Complexity

The time complexity of the given solution can be analyzed as follows:

The function iterates over each element in the array nums exactly once.
For each element num, it performs a constant-time operation to check and update the counts in the Counter, which is an implementation of a hash map.
Therefore, the time complexity is linear with regard to the number of elements in the list, which is O(n) where n is the length of the nums list.

Space Complexity

The space complexity of the solution can be analyzed as follows:

A Counter is used to keep track of the occurrences of each number in the list.
In the worst case, if all elements in the list are unique, the size of the Counter will grow linearly with the number of elements.
Therefore, the space complexity of the solution is O(n) where n is the number of unique elements in nums.

In summary, both the time complexity and the space complexity of the given code are O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

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

Question 1 out of 10

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

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know