LeetCode 2006 - Count Number of Pairs With Absolute Difference K

LeetCode Problem 2006

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Counting

Solution

Problem Understanding

The problem gives us an integer array nums and an integer k. We need to count how many pairs of indices (i, j) satisfy two conditions:

i < j
|nums[i] - nums[j]| == k

The notation |x| represents the absolute value of x, meaning the distance between two numbers regardless of direction. For example, both 3 - 1 and 1 - 3 have an absolute difference of 2.

The input array can contain duplicate values, and every valid pair of indices must be counted separately. This is important because the same numeric values can appear at multiple positions. For example, in [1,2,2,1] with k = 1, the answer is 4 because each 1 can pair with each 2.

The constraints are relatively small:

1 <= nums.length <= 200
1 <= nums[i] <= 100
1 <= k <= 99

These constraints tell us several things:

The array is small enough that even an O(n^2) brute-force solution would pass comfortably.
The values are also bounded within a small range.
Since k >= 1, we never need to count pairs with identical values.

Even though brute force is acceptable here, the problem is still a good opportunity to practice frequency counting with a hash map.

Some important edge cases include:

Arrays with duplicate numbers, because multiple index combinations may produce the same value pair.
Arrays where no valid pairs exist.
Arrays where every element can pair with multiple others.
Very small arrays, such as length 1, where the answer must always be 0.

Approaches

Brute-Force Approach

The most direct solution is to check every possible pair of indices (i, j) where i < j.

For each pair:

Compute abs(nums[i] - nums[j])
If the result equals k, increment the answer.

This approach is correct because it explicitly evaluates every possible pair exactly once. Since no pair is skipped, every valid pair is counted.

However, the time complexity is O(n^2) because we use two nested loops. For an array of length n, there are approximately n * (n - 1) / 2 pairs to examine.

With n <= 200, this is still perfectly acceptable, but we can do better conceptually.

Optimal Hash Map Approach

The key observation is that for a current number x, we only care whether we have already seen:

x - k
x + k

If either exists among previously processed numbers, then those earlier values form valid pairs with x.

We can maintain a frequency map that stores how many times each number has appeared so far.

As we iterate through the array:

The number of previously seen values equal to x - k contributes directly to the answer.
The number of previously seen values equal to x + k also contributes directly to the answer.

After counting those matches, we record the current number in the frequency map.

This works because we process the array from left to right, ensuring every counted pair automatically satisfies i < j.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	`O(n^2)`	`O(1)`	Checks every possible pair directly
Optimal	`O(n)`	`O(n)`	Uses a hash map to count previously seen values

Algorithm Walkthrough

Optimal Hash Map Algorithm

Initialize a variable pair_count to 0.

This variable stores the total number of valid pairs found so far. 2. Create an empty hash map called frequency.

The map will store how many times each number has appeared earlier in the array. 3. Iterate through each number num in nums.

We process the array from left to right so that all values already stored in the map correspond to earlier indices. 4. Check whether num - k exists in the map.

If it does, then every previous occurrence of num - k forms a valid pair with the current num.

Add frequency[num - k] to pair_count. 5. Check whether num + k exists in the map.

If it does, then every previous occurrence of num + k also forms a valid pair with the current num.

Add frequency[num + k] to pair_count. 6. Insert the current number into the map.

Increment frequency[num] by 1. 7. After processing all elements, return pair_count.

Why it works

The algorithm maintains the invariant that the frequency map contains counts only for elements that appear before the current index.

For each current value num, any earlier value equal to num - k or num + k satisfies:

|num - previous_value| == k

Since every pair is counted exactly when the second element is processed, each valid pair is counted once and only once.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        frequency = defaultdict(int)
        pair_count = 0

        for num in nums:
            pair_count += frequency[num - k]
            pair_count += frequency[num + k]

            frequency[num] += 1

        return pair_count

The implementation uses defaultdict(int) so missing keys automatically return 0. This removes the need for explicit existence checks.

The variable frequency stores how many times each number has appeared earlier in the array. For every current number, we immediately count how many previous numbers differ by exactly k.

The order of operations matters. We first count matching previous values, then insert the current value into the map. This guarantees we never pair an element with itself and ensures all counted pairs satisfy i < j.

Finally, the function returns the accumulated pair count.

Go Solution

func countKDifference(nums []int, k int) int {
    frequency := make(map[int]int)
    pairCount := 0

    for _, num := range nums {
        pairCount += frequency[num-k]
        pairCount += frequency[num+k]

        frequency[num]++
    }

    return pairCount
}

The Go implementation follows the same logic as the Python version.

Go maps return the zero value for missing keys, so accessing frequency[num-k] is safe even when the key does not exist.

Unlike Python, Go does not need a special defaultdict structure because integer map lookups naturally default to 0.

There are no integer overflow concerns here because the maximum number of pairs is small given the constraints.

Worked Examples

Example 1

Input:

nums = [1,2,2,1]
k = 1

We process the array left to right.

Step	Current Number	frequency Before	Matches Found	pair_count After	frequency After
1	1	{}	0	0	{1:1}
2	2	{1:1}	frequency[1] = 1	1	{1:1, 2:1}
3	2	{1:1, 2:1}	frequency[1] = 1	2	{1:1, 2:2}
4	1	{1:1, 2:2}	frequency[2] = 2	4	{1:2, 2:2}

Final answer:

Example 2

Input:

nums = [1,3]
k = 3

Step	Current Number	frequency Before	Matches Found	pair_count After
1	1	{}	0	0
2	3	{1:1}	0	0

Final answer:

Example 3

Input:

nums = [3,2,1,5,4]
k = 2

Step	Current Number	frequency Before	Matches Found	pair_count After
1	3	{}	0	0
2	2	{3:1}	0	0
3	1	{3:1, 2:1}	frequency[3] = 1	1
4	5	{3:1, 2:1, 1:1}	frequency[3] = 1	2
5	4	{3:1, 2:1, 1:1, 5:1}	frequency[2] = 1	3

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	`O(n)`	Each element is processed once with constant-time hash map operations
Space	`O(n)`	The frequency map may store up to `n` distinct numbers

The algorithm performs a single pass through the array. Each lookup and insertion into the hash map takes average constant time, so the overall runtime is linear.

The extra memory usage comes from storing element frequencies. In the worst case, all numbers are distinct, so the map stores n entries.

Test Cases

from typing import List
from collections import defaultdict

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        frequency = defaultdict(int)
        pair_count = 0

        for num in nums:
            pair_count += frequency[num - k]
            pair_count += frequency[num + k]
            frequency[num] += 1

        return pair_count

solution = Solution()

assert solution.countKDifference([1,2,2,1], 1) == 4  # Provided example with duplicates
assert solution.countKDifference([1,3], 3) == 0  # No valid pairs
assert solution.countKDifference([3,2,1,5,4], 2) == 3  # Multiple scattered pairs

assert solution.countKDifference([1], 1) == 0  # Single element array
assert solution.countKDifference([1,1,1,1], 1) == 0  # All identical values
assert solution.countKDifference([1,2,3,4,5], 1) == 4  # Consecutive increasing numbers
assert solution.countKDifference([1,3,5,7], 2) == 3  # Every adjacent pair works
assert solution.countKDifference([10,8,6,4,2], 2) == 4  # Decreasing sequence
assert solution.countKDifference([1,100], 99) == 1  # Maximum possible k
assert solution.countKDifference([2,2,2,3,3], 1) == 6  # Many duplicate combinations

Test	Why
`[1,2,2,1], k=1`	Validates duplicate pair counting
`[1,3], k=3`	Validates no matching pairs
`[3,2,1,5,4], k=2`	Validates unordered values
`[1], k=1`	Tests minimum array length
`[1,1,1,1], k=1`	Ensures identical values are not incorrectly counted
`[1,2,3,4,5], k=1`	Tests consecutive matches
`[1,3,5,7], k=2`	Tests multiple valid adjacent differences
`[10,8,6,4,2], k=2`	Tests descending order input
`[1,100], k=99`	Tests largest valid difference
`[2,2,2,3,3], k=1`	Tests combinational duplicate counting

Edge Cases

One important edge case is an array containing only one element. Since a valid pair requires two different indices, the answer must always be 0. The implementation handles this naturally because the loop never finds any previously seen matching values.

Another important case involves many duplicate values. For example, [2,2,2,3,3] with k = 1 should produce 6 valid pairs because each 2 can pair with each 3. A naive implementation might accidentally count only unique value pairs instead of index pairs. The frequency map approach correctly counts all combinations by storing occurrence counts.

A third edge case occurs when no valid pairs exist. For example, [1,3] with k = 3 has no pair whose absolute difference equals 3. The algorithm handles this safely because missing hash map entries contribute 0 to the answer.

Another subtle case is input order. Valid pairs may appear in increasing order, decreasing order, or mixed order. Since the algorithm checks both num - k and num + k, it correctly identifies pairs regardless of whether the earlier number is larger or smaller than the current number.