608. How Many Triples Stay Under the Target
Given n integers and a target, count the triples of POSITIONS i < j < k whose values add
to strictly less than the target.
-2 0 1 3, target 2 -> 2 (-2,0,1) and (-2,0,3)
1 2 3 4 5, target 0 -> 0
## Counting a whole block at once
The sweep looks like 606 and 607, but the step is different and that difference is the entire point.
Sort, fix a[i], and set lo = i+1, hi = n-1. Now suppose
a[i] + a[lo] + a[hi] < target
Because the array is sorted, EVERY value between lo and hi is at most a[hi]. So pairing
a[lo] with any of a[lo+1] .. a[hi] also stays under the target. That is hi - lo triples,
all confirmed by one comparison:
if a[i] + a[lo] + a[hi] < target:
count += hi - lo
lo += 1
else:
hi -= 1
Counting a block per step rather than one triple per step is what keeps this O(n^2) instead
of O(n^3).
## The off-by-one to get right
It is hi - lo, not hi - lo + 1. The pairs counted are (lo, lo+1) up to (lo, hi), which
is hi - lo of them; the pair (lo, lo) is not a pair at all.
Checking it on a tiny case is faster than reasoning about it: with lo = 1 and hi = 2 there
is exactly one pair, and hi - lo = 1.
## Why advancing lo is safe
After counting, every triple using THIS lo and any partner up to hi has been counted, and
partners beyond hi do not exist for this i. So lo is finished and moving it forward loses
nothing.
In the other branch the sum is too large, so a[hi] is too large for every partner that
remains, exactly as in 605.
## Positions, not values
Repeated values give separate triples here, because the triples are indexed by position. On
0 0 0 with target 1 the answer is 1, since there is only one triple of positions, but on
1 1 1 1 with a large target the answer is 4.
That is the opposite convention to problem 606, which collapses duplicates. Read which one a problem wants before writing the loop.
## Overflow
With n = 3000 the count reaches C(3000, 3), about 4.5 * 10^9, which overflows a signed
32 bit integer. The COUNT needs 64 bits, not just the sums.
## Cost
Time O(n^2). Space O(1) beyond the input.
Constraints - `3 ≤ n ≤ 3000` - `-10^9 ≤ each value ≤ 10^9` - `-10^9 ≤ target ≤ 10^9`
Input
The first line contains two integers n and target.
The second line contains n integers.
Output
Print one integer, the number of triples of positions whose values add to less than the target.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.