FunctionRacerProblemsRace

Pairs Within Reach

EasyTwo pointersPython, JavaScript, TypeScript, Java, C++

nums is sorted in non-decreasing order. Count the pairs of positions (i, j) with i < j such that nums[j] - nums[i] <= d, that is, the two items differ by at most d.

Equal items always qualify, since they differ by 0, and positions are what is counted, so equal values at different positions make different pairs. For each position j, the partners i that qualify form a block ending just before j, and the start of that block only ever moves right as j grows, so one trailing index counts them all in a single pass.

Example 1

nums [1,2,4,7]
d 2
returns 2

The pairs (1, 2) and (2, 4) differ by at most 2; (1, 4), (1, 7), (2, 7) and (4, 7) do not.

Example 2

nums [1,1,1]
d 0
returns 3

Every pair of the three equal items qualifies: 3 pairs.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Two pointers problems