Pairs With a Given Difference — Solution & Editorial

Back to the Problem

Frequency-count the values. For K > 0, sum cnt[x] · cnt[x+K]; for K = 0, sum C(cnt[x], 2) instead.

Complexity: O(N)

Watch out: K = 0 is the classic special case — pairs come from within each value's own count.