2312. How Many Pairs on a Line Are Close Enough

Given n integers and a threshold d, print how many unordered pairs are at distance at most d. Pairs are unordered, so each is counted once, and d may be 0, in which case the question counts pairs of equal values.

1 3 6 10 d = 3 -> 2 (1,3) and (3,6) 5 5 d = 0 -> 1 two equal values are at distance 0 1 2 3 d = 0 -> 0 nothing is equal 0 0 0 0 d = 0 -> 6 all six pairs

## What most people try first

All pairs, which is correct and O(n^2), so at n = 200000 it is 2 * 10^10 comparisons and does not scale. The second instinct is a binary search per element for the furthest partner within d, which is a genuine O(n log n) and is fine; the two-pointer sweep below is the same idea with the search replaced by a pointer that never moves backward.

## Sort, then two pointers

Sort the values. Walk a right end j from left to right and keep a left end i as the smallest index with v[j] - v[i] <= d. Each step of j can only push i forward, never back, because v[j] only grows. Then every index in [i, j) pairs with j, which is j - i pairs:

sort v i = 0 total = 0 for j in 0 .. n-1: while v[j] - v[i] > d: i = i + 1 total = total + (j - i)

## Why it counts each pair exactly once

Every pair is counted at the moment its LARGER index becomes j, and only then, so no pair is double counted and none is missed. Equal values are handled by the same rule: with d = 0 the window holds exactly the run of values equal to v[j], so the four zeros contribute 0 + 1 + 2 + 3 = 6, which is C(4, 2) as it should be.

The pointer i moves forward at most n times in total across the whole loop, so the inner while is amortised constant and the sweep is linear after the sort.

## Why i never needs to move back

Because the values are sorted, v[j] is non-decreasing in j. If v[j] - v[i] was already small enough to admit i, increasing j can only make the difference larger, never smaller, so an index that has been pushed out of the window can never re-enter it. This monotonicity is the whole justification for the two-pointer shape, and it is exactly what the sort buys.

## Width

The values and the threshold are small: |v| <= 10^6 and 0 <= d <= 2 * 10^6, so every difference stays comfortably inside the range of a signed 32-bit integer. The COUNT does not. With n = 200000 equal values and d = 0 every pair qualifies, so the answer is C(200000, 2) = 19999900000, which is about 2 * 10^10 and overflows a signed 32-bit accumulator, whose limit is 2147483647. A truncating 32 bit build reports -1474936480 on that input, and that case is a declared test. The value is below 2^53 = 9007199254740992, so a JavaScript Number holds it exactly.

## Cost

O(n log n) for the sort, then one linear sweep.

Constraints - `2 <= n <= 200000` - `-1000000 <= v[i] <= 1000000` - `0 <= d <= 2000000` - values need not be distinct, and with `d = 0` the question counts pairs of equal values - the answer can be as large as 19999900000, which is past the top of a signed 32-bit integer