Count Number of Pairs With Absolute Difference K

Difficulty: Easy | Acceptance: 85.40% | Paid: No Topics: Array, Hash Table, Counting

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 if x >= 0 -x if x < 0

• Examples
• Constraints
• Brute Force
• Hash Map Frequency Count
• Sorting + Binary Search
• One-pass Hash Map
• Counting Array

Examples

Input: nums = [1,2,2,1], k = 1
Output: 4
Explanation:
The pairs with an absolute difference of 1 are:
- (0, 1) with |1 - 2| = 1
- (0, 2) with |1 - 2| = 1
- (1, 3) with |2 - 1| = 1
- (2, 3) with |2 - 1| = 1

Input: nums = [1,3], k = 3
Output: 0
Explanation: |1 - 3| = 2 ≠ 3

Input: nums = [3,2,1,5,4], k = 2
Output: 3
Explanation:
The pairs with an absolute difference of 2 are:
- (0, 2) with |3 - 1| = 2
- (0, 3) with |3 - 5| = 2
- (1, 4) with |2 - 4| = 2

Constraints

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

Brute Force

Intuition Check every possible pair (i, j) where i < j and count those with absolute difference k.

Steps

• Iterate through all indices i from 0 to n-1
• For each i, iterate through j from i+1 to n-1
• If |nums[i] - nums[j]| == k, increment count
• Return the total count

from typing import List

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        count = 0
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if abs(nums[i] - nums[j]) == k:
                    count += 1
        return count

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple but inefficient for large arrays

Hash Map Frequency Count

Intuition Count frequency of each number, then for each unique value x, check if x + k exists and multiply frequencies.

Steps

• Build a frequency map of all numbers in nums
• For each unique number x in the map
• If x + k exists in the map, add freq[x] * freq[x + k] to count
• Return the total count

from typing import List
from collections import Counter

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        freq = Counter(nums)
        count = 0
        for num in freq:
            if num + k in freq:
                count += freq[num] * freq[num + k]
        return count

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Efficient single pass with hash map

Sorting + Binary Search

Intuition Sort the array and use binary search to find all elements equal to nums[i] + k for each i.

Steps

• Sort the array
• For each index i, compute target = nums[i] + k
• Use binary search to find the range of indices where nums[j] == target and j > i
• Add the count of such indices to the result
• Return total count

from typing import List
import bisect

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        count = 0
        for i in range(n):
            target = nums[i] + k
            left = bisect.bisect_left(nums, target, i + 1)
            right = bisect.bisect_right(nums, target, i + 1)
            count += right - left
        return count

Complexity

• Time: O(n log n)
• Space: O(1) or O(n) depending on sorting
• Notes: Useful when array is already sorted

One-pass Hash Map

Intuition Build frequency map while iterating, checking for complements (num - k and num + k) that were seen before.

Steps

• Initialize an empty frequency map and count = 0
• For each number num in nums
• Add freq[num - k] and freq[num + k] to count
• Increment freq[num] by 1
• Return count

from typing import List
from collections import defaultdict

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        freq = defaultdict(int)
        count = 0
        for num in nums:
            count += freq[num - k] + freq[num + k]
            freq[num] += 1
        return count

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Most elegant single-pass solution

Counting Array

Intuition Since nums[i] ≤ 100, use a fixed-size array instead of hash map for O(1) access.

Steps

• Create a frequency array of size 101 initialized to 0
• Count frequency of each number in nums
• For each value i from 1 to 100
• If i + k ≤ 100, add freq[i] * freq[i + k] to count
• Return count

from typing import List

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        freq = [0] * 101
        for num in nums:
            freq[num] += 1
        count = 0
        for i in range(1, 101):
            if i + k <= 100:
                count += freq[i] * freq[i + k]
        return count

Complexity

• Time: O(n)
• Space: O(1) - fixed size array
• Notes: Optimal for given constraints