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.
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.
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.
x - k and x + k are the same key, and the code above would count each earlier duplicate twice. The problem guarantees k >= 1, but say this out loud; for k = 0 use pairs += seen[x] only.x + k in it, handling k = 0 by counting values with frequency >= 2.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.)