2006. Count Number of Pairs With Absolute Difference K

EasyArrayHash TableCounting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums and an integer k. Your task is to count how many pairs of indices (i, j) exist where i < j and the absolute difference between the elements at these indices equals k.

In other words, you need to find all pairs where:

The first index i comes before the second index j (i.e., i < j)
The absolute difference |nums[i] - nums[j]| equals exactly k

The absolute value |x| is defined as:

x if x >= 0
-x if x < 0

For example, if nums = [1, 2, 2, 1] and k = 1, the valid pairs would be:

(0, 1) because |1 - 2| = 1
(0, 2) because |1 - 2| = 1
(2, 3) because |2 - 1| = 1
(1, 3) because |2 - 1| = 1

So the answer would be 4.

The optimal approach uses a frequency map: as we scan left to right, we count how many previously seen values differ from the current value by exactly k, then record the current value for future lookups.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

Count occurrences of each value, then for every distinct x sum count[x]*count[x+k].

Open in Flowchart

Intuition

A brute force approach checks every pair (i, j) where i < j — O(n²) total comparisons. With at most 200 elements that's 19,900 pairs, which works within the constraints. But we can do better.

The optimal approach recognizes that |nums[i] - nums[j]| == k means either nums[j] - nums[i] == k or nums[i] - nums[j] == k. Rearranging: a valid partner for nums[j] is any prior element equal to nums[j] - k or nums[j] + k.

This suggests a single-pass strategy: maintain a frequency map of numbers seen so far. When we reach index j, look up freq[nums[j] - k] and freq[nums[j] + k] — each gives the count of earlier elements that form a valid pair with nums[j]. Because we only query elements already processed (at indices < j), the ordering constraint i < j is automatically satisfied and no pair is counted twice.

After the lookups, add nums[j] to the map for future iterations. One pass, O(n) time.

Solution Approach

We use a single pass with a frequency map.

Initialize an empty map freq and a counter count = 0. For each num in nums:

Add freq.get(num - k, 0) to count — counts prior elements that are exactly k less than num.
Add freq.get(num + k, 0) to count — counts prior elements that are exactly k greater than num.
Increment freq[num] to record num for future iterations.

The two lookups handle both directions of the absolute difference in one step. Updating the map after the lookups ensures we only count elements at strictly earlier indices, preserving the i < j constraint without any extra bookkeeping.

Example Walkthrough

nums = [3, 1, 4, 1, 5], k = 2. We scan left to right, maintaining freq and count.

Step	num	freq before lookup	freq[num-2]	freq[num+2]	count
1	3	{}	freq[1] = 0	freq[5] = 0	0
2	1	{3: 1}	freq[-1] = 0	freq[3] = 1	1
3	4	{3: 1, 1: 1}	freq[2] = 0	freq[6] = 0	1
4	1	{3: 1, 1: 1, 4: 1}	freq[-1] = 0	freq[3] = 1	2
5	5	{3: 1, 1: 2, 4: 1}	freq[3] = 1	freq[7] = 0	3

Result: 3

The three pairs found: (index 0, 1) → |3−1|=2, (index 0, 3) → |3−1|=2, (index 0, 4) → |3−5|=2. Each is discovered exactly once when we process the later element in the pair.

Solution Implementation

1class Solution:
2    def countKDifference(self, nums: List[int], k: int) -> int:
3        count = 0
4        freq: dict[int, int] = {}
5        for num in nums:
6            count += freq.get(num - k, 0) + freq.get(num + k, 0)
7            freq[num] = freq.get(num, 0) + 1
8        return count
9

1class Solution {
2    public int countKDifference(int[] nums, int k) {
3        int count = 0;
4        Map<Integer, Integer> freq = new HashMap<>();
5        for (int num : nums) {
6            count += freq.getOrDefault(num - k, 0) + freq.getOrDefault(num + k, 0);
7            freq.put(num, freq.getOrDefault(num, 0) + 1);
8        }
9        return count;
10    }
11}
12

1class Solution {
2public:
3    int countKDifference(vector<int>& nums, int k) {
4        int count = 0;
5        unordered_map<int, int> freq;
6        for (int num : nums) {
7            if (freq.count(num - k)) count += freq[num - k];
8            if (freq.count(num + k)) count += freq[num + k];
9            freq[num]++;
10        }
11        return count;
12    }
13};
14

1/**
2 * Counts the number of pairs (i, j) where i < j and |nums[i] - nums[j]| = k
3 * @param nums - Array of integers
4 * @param k - Target absolute difference
5 * @returns Number of valid pairs
6 */
7function countKDifference(nums: number[], k: number): number {
8    // Initialize counter for valid pairs
9    let pairCount: number = 0;
10  
11    // Map to store frequency of each number seen so far
12    const frequencyMap: Map<number, number> = new Map<number, number>();
13  
14    // Iterate through each number in the array
15    for (const currentNum of nums) {
16        // Check for pairs with difference k
17        // Count pairs where current number minus k exists (currentNum - k = previousNum)
18        // Count pairs where current number plus k exists (currentNum + k = previousNum)
19        pairCount += (frequencyMap.get(currentNum - k) || 0) + (frequencyMap.get(currentNum + k) || 0);
20      
21        // Update frequency of current number in the map
22        frequencyMap.set(currentNum, (frequencyMap.get(currentNum) || 0) + 1);
23    }
24  
25    return pairCount;
26}
27

Time and Space Complexity

The time complexity is O(n), where n is the length of nums. We make a single pass over the array, and each hash map lookup and update is O(1) on average.

The space complexity is O(n) in the worst case, since the frequency map holds at most one entry per distinct element.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Updating the Map Before Looking Up

Updating freq[num] before the two lookups means the current element can pair with itself, producing wrong results when there are duplicates.

# INCORRECT - updates map before lookup
for num in nums:
    freq[num] = freq.get(num, 0) + 1   # Wrong order!
    count += freq.get(num - k, 0) + freq.get(num + k, 0)

Always perform the lookups first, then update the map:

# CORRECT
for num in nums:
    count += freq.get(num - k, 0) + freq.get(num + k, 0)
    freq[num] = freq.get(num, 0) + 1   # Update after

2. Checking Only One Direction

|nums[i] - nums[j]| == k holds when the difference is +k or -k. Checking only one direction misses half the pairs.

# INCORRECT - misses pairs where nums[i] > nums[j]
count += freq.get(num - k, 0)

Look up both num - k and num + k:

# CORRECT
count += freq.get(num - k, 0) + freq.get(num + k, 0)

3. Using a Sorted-Frequency Approach That Breaks Pair Ordering

Some solutions precompute a frequency array and then loop over distinct values:

# Potentially incorrect for counting ordered pairs (i < j)
from collections import Counter
freq = Counter(nums)
count = sum(freq[x] * freq[x + k] for x in freq)

This counts unordered pairs — including pairs where the higher-indexed element has the smaller value. For this problem the pair definition is symmetric (|a - b| == |b - a|), so it gives the same answer here, but the technique doesn't extend directly to problems that distinguish direction.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: