Problem
Given an integer array nums
and an integer k
, return the number of pairs (i, j)
where i < j
such that |nums[i] - nums[j]| == k
.
The value of |x|
is defined as:
x
ifx >= 0
.-x
ifx < 0
.
Examples
Example 1:
Input: nums = [1,2,2,1], k = 1
Output: 4
Explanation: The pairs with an absolute difference of 1 are:
- [1̲,2̲,2,1]
- [1̲,2,2̲,1]
- [1,2̲,2,1̲]
- [1,2,2̲,1̲]
Example 2:
Input:
nums = [1,3], k = 3
Output:
0
Explanation: There are no pairs with an absolute difference of 3.
Example 3:
Input: nums = [3,2,1,5,4], k = 2
Output: 3
Explanation: The pairs with an absolute difference of 2 are:
- [3̲,2,1̲,5,4]
- [3̲,2,1,5̲,4]
- [3,2̲,1,5,4̲]
Solution
Method 1 - Using HashMap
Here is the approach:
- Use a HashMap:
- We can use a
HashMap
to keep track of the frequency of each element innums
as we iterate through the array. - For each element
num
innums
, check if(num + k)
or(num - k)
exists in theHashMap
. - If it does, increment the result by the frequency of those elements.
- Add the current element to the
HashMap
.
- We can use a
- Count Pairs:
- As we iterate, for each element
num
, ifnum + k
ornum - k
exists, it means there are pairs that satisfy the condition.
- As we iterate, for each element
Code
Java
public class Solution {
public int countKDifference(int[] nums, int k) {
HashMap<Integer, Integer> freqMap = new HashMap<>();
int count = 0;
for (int num : nums) {
if (freqMap.containsKey(num + k)) {
count += freqMap.get(num + k);
}
if (freqMap.containsKey(num - k)) {
count += freqMap.get(num - k);
}
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
return count;
}
}
Python
def countKDifference(nums, k):
freq_map = {}
count = 0
for num in nums:
if num + k in freq_map:
count += freq_map[num + k]
if num - k in freq_map:
count += freq_map[num - k]
if num in freq_map:
freq_map[num] += 1
else:
freq_map[num] = 1
return count
Complexity
- Time:
O(n)
, where (n) is the number of elements in the arraynums
, since we are iterating through the array and using aHashMap
for constant timeget
andput
operations. - Space:
O(n)
as we are storing elements in aHashMap
.