Count Number of Pairs With Absolute Difference K - Solution & Explanation

Problem Overview: Given an integer array nums and an integer k, count the number of index pairs (i, j) such that i < j and |nums[i] - nums[j]| = k. The task is essentially pair counting with a fixed absolute difference constraint.

Approach 1: Brute Force Pair Check (O(n²) time, O(1) space)

The most direct solution checks every possible pair. Use two nested loops where the outer loop picks index i and the inner loop scans all indices j > i. For each pair, compute abs(nums[i] - nums[j]) and increment a counter when the difference equals k. This approach does not require additional data structures and works for any input order. However, it performs n(n-1)/2 comparisons, leading to O(n²) time complexity. It’s acceptable for small arrays and useful as a baseline to verify correctness before implementing a faster method.

Approach 2: Hash Map Frequency Counting (O(n) time, O(n) space)

A more efficient strategy uses a hash map to track how many times each value has appeared while iterating through the array. For every element x, you check whether x - k or x + k has already been seen. If they exist in the map, their frequencies represent valid pairs that satisfy the difference condition. Update the pair count accordingly, then store or increment the frequency of x in the map. Each lookup and update is O(1) on average, producing an overall O(n) time complexity with O(n) space for the frequency table.

This approach works because the difference condition can be rewritten as a - b = k or b - a = k. A hash lookup instantly tells you how many previously processed numbers satisfy either equation. The technique is a common pattern when solving pair problems with constraints on sums or differences.

The optimized method heavily relies on hash tables for constant‑time lookups and uses ideas similar to frequency tracking problems in counting. Since the input is simply scanned once, it scales efficiently even for large arrays typical in interview settings. The underlying data is still an array, but the hash map transforms the pair search from quadratic to linear time.

Recommended for interviews: Start by explaining the brute force approach to demonstrate understanding of the pair condition. Then move to the hash map solution, which reduces the complexity from O(n2) to O(n). Interviewers typically expect the hash-based counting approach because it shows familiarity with frequency maps and pair‑difference transformations.