656. Triples a Fixed Step Apart
A STRICTLY INCREASING list is given, along with a step d. Count the triples of positions
i < j < k with
a[j] - a[i] = d and a[k] - a[j] = d
0 1 4 6 7 10, d = 3 -> 2 (1,4,7) and (4,7,10)
4 5 6 7 8 9, d = 2 -> 2
1 2 3, d = 5 -> 0
## Fix the middle, not the first
Both conditions mention a[j], so fixing the MIDDLE value turns one three-way question into
two independent two-way ones: is a[j] - d present before j, and is a[j] + d present after
it.
Fixing a[i] instead leaves a[j] and a[k] chained to each other and gains nothing.
## Three cursors, all moving forward
i = 0, k = 0
for j in 0 .. n-1:
while i < j and a[j] - a[i] > d: i += 1
while k < n and a[k] - a[j] < d: k += 1
if a[j] - a[i] == d and a[k] - a[j] == d: count += 1
As j advances, the position where a[j] - d would sit only moves forward, and so does the
position where a[j] + d would sit. So neither helper cursor ever retreats, and the whole
scan is linear.
## Why strict increase matters twice
FIRST, it means a value appears at most once, so each triple is counted exactly once and there are no runs to tally.
SECOND, it is what makes both cursors monotone. On a merely non-decreasing list, equal values
would let the same a[j] - d be matched from several positions and the count would need runs
rather than a single index, as in problem 629.
The statement says strictly increasing precisely so that neither complication arises, and noticing which guarantee is doing which job is part of reading a problem properly.
## The counting is by VALUE here
Because values are distinct, counting positions and counting values coincide. That is a happy accident of the constraint rather than a choice, and it is worth saying so: in 608 and 659 the distinction is real and changes the answer.
## Boundaries
Fewer than three values gives 0. A step larger than the whole spread gives 0.
An evenly spaced list of n values with matching d gives n - 2 triples, which is the check
to run on 0 2 4 6 8 with d = 2: the answer is 3.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ d ≤ 10^9` - `0 ≤ each value ≤ 10^9` - the list is strictly increasing
Input
The first line contains two integers n and d.
The second line contains n integers in strictly increasing order.
Output
Print one integer, the number of triples a step d apart.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.