2006. Count Number of Pairs With Absolute Difference K
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 at0
. - Create a
Counter
objectcnt
which will store the frequency of each number encountered innums
. - Iterate over each number
num
in thenums
array:- For the current number
num
, check ifnum - k
is in the counter. If it is, it means there are numbers previously seen that, when subtracted fromnum
, givek
. We add the count ofnum - k
toans
. - Similarly, check if
num + k
is in the counter. If it is, add the count ofnum + k
toans
. This counts the cases where the previous numbers were smaller thannum
and had a difference ofk
. - After checking for pairs, increment the count of
num
in thecnt
Counter to account for its occurrence.
- For the current number
- 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 EvaluatorExample 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
to0
as no pairs have been counted yet. - Create a
Counter
objectcnt
which is initially empty.
Now, let's iterate over each number num
in nums
:
-
For the first number
1
, we check if1 - 2
(which is-1
) and1 + 2
(which is3
) are in the counter. Neither are because the counter is empty, so we don't changeans
. Then we add1
to the counter, socnt
becomesCounter({1: 1})
. -
Moving to the second number
5
, we look for5 - 2
(equals3
) and5 + 2
(equals7
). Neither are in the counter, soans
remains0
. Then we updatecnt
, nowCounter({1: 1, 5: 1})
. -
Next,
3
is checked against the counter. We look for3 - 2
(which is1
) and3 + 2
(which is5
). We find1
in the counter with a count of1
. So we incrementans
by1
. We do not find5
because we only count pairs wherei < j
, to avoid re-counting. Update the counter with3
, nowCounter({1: 1, 5: 1, 3: 1})
. -
For
4
, we do the same. We find4 - 2 = 2
is not in the counter but4 + 2 = 6
isn't in the counter either. So,ans
is still1
. Updatecnt
toCounter({1: 1, 5: 1, 3: 1, 4: 1})
. -
Lastly, for
2
,2 - 2
equals0
(not present in the counter) but2 + 2
equals4
which is in the counter with a count of1
. Thus, we incrementans
by1
making it2
. Final update to the counter leaves it asCounter({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 theCounter
, 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)
wheren
is the length of thenums
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)
wheren
is the number of unique elements innums
.
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.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!