614. Distinct Pairs a Fixed Distance Apart
Given n integers and a value k, count the DISTINCT pairs of values (x, y) with
y - x = k where both x and y appear in the array.
Pairs are compared by VALUE, so (1, 3) found twice counts once. When k is 0, a pair means
the same value appearing at two different positions.
3 1 4 1 5, k = 2 -> 2 (1,3) and (3,5)
1 1 1 1, k = 0 -> 1 the value 1 appears more than once
## Values, not positions, and the contrast with problem 269
Problem 269 asks the same-looking question and counts pairs of POSITIONS: on 1 1 1 with
k = 0 it answers 3, because three equal values give three position pairs. This counts
distinct VALUES, so the same input answers 1.
That is the counting convention of problem 606, not that of 608 or 269. 1 1 2 2 3 3 with
k = 1 answers 2 here, the value pairs (1,2) and (2,3), even though many pairs of
positions realise them.
Solve 269 first if you have not. The two are worth meeting together, because the sweep is nearly the same and the duplicate handling is entirely different.
Deciding this before writing the loop is the actual work; the sweep is short once it is settled.
## Both pointers move forward
Sort, then run two pointers in the SAME direction:
i = 0, j = 1
while i < n and j < n:
if i == j: j += 1
else if b[j] - b[i] < k: j += 1
else if b[j] - b[i] > k: i += 1
else:
count += 1
i += 1
skip i past values equal to b[i-1]
if j <= i: j = i + 1
The array is sorted, so a difference that is too small only grows by advancing j, and one
that is too large only shrinks by advancing i. Neither pointer ever rewinds, which is what
makes this linear after the sort.
## The two details that catch people
FIRST, i and j must stay distinct, otherwise k = 0 matches every element with itself and
the answer becomes the number of distinct values. The i == j branch and the
if j <= i: j = i + 1 line both exist for this.
SECOND, after recording a pair, i must skip past every copy of the value just used. Without
it, 1 1 2 with k = 1 records (1,2) twice.
## Why k is never negative
A pair with y - x = -k is the same unordered pair as one with x - y = k, so allowing
negative k would only double the wording without adding a case. The constraint fixes
k >= 0.
## Boundaries
A single element answers 0 for every k, since a pair needs two positions.
k = 0 on all-distinct values answers 0. k larger than the whole spread answers 0.
## Cost
Time O(n log n) for the sort. Space O(1) beyond the input.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ k ≤ 10^9` - `-10^9 ≤ each value ≤ 10^9`
Input
The first line contains two integers n and k.
The second line contains n integers.
Output
Print one integer, the number of distinct value pairs whose difference is k.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.