Count Number of Pairs With Absolute Difference K (LeetCode 2006): Two Sum in Disguise

The problem: given an integer array nums and an integer k, count pairs (i, j) with i < j and |nums[i] - nums[j]| == k. Example: nums = [1,2,2,1], k = 1 gives 4.

Brute force

def countKDifference(nums, k):
    n = len(nums)
    return sum(1 for i in range(n) for j in range(i + 1, n) if abs(nums[i] - nums[j]) == k)

O(n^2). With n <= 200 it passes, but the interviewer will ask for linear time.

One pass with a hash map

For each value x, every earlier value equal to x - k or x + k forms a valid pair. Count them before adding x to the map.

from collections import Counter
def countKDifference(nums, k):
    seen = Counter()
    pairs = 0
    for x in nums:
        pairs += seen[x - k] + seen[x + k]
        seen[x] += 1
    return pairs

O(n) time, O(n) space. Counting before inserting is what enforces i < j and avoids double counting.

Follow-ups

Takeaway

The pattern "for each element, look up its complement among earlier elements" is Two Sum in disguise. Recognising it quickly is what this question measures.


Notes from the Linkjob AI team. If you want to rehearse explaining solutions like this live, try it free. (Disclosure: affiliated.)