609. How Many Triples Make a Triangle

Given n positive lengths, count the triples of POSITIONS i < j < k whose three lengths can form a triangle with a positive area.

Three lengths form such a triangle exactly when the sum of the two shorter ones is STRICTLY greater than the longest.

2 2 3 4 -> 3 1 2 3 -> 0 1 + 2 is not greater than 3

## One inequality, not three

The triangle inequality is usually stated three times, once per side. Sort the three lengths as x <= y <= z and two of them become free: x + z > y holds because z >= y and x > 0, and y + z > x likewise.

Only x + y > z can fail. So after sorting the whole array, there is a single condition per triple.

Equality fails: 1 2 3 is a straight line, not a triangle, which is what "positive area" means. That is the test in the sample.

## Sweep from the LARGEST side

Sort, then fix the LONGEST side a[k] and look for pairs below it:

for k from n-1 down to 2: lo = 0, hi = k-1 while lo < hi: if a[lo] + a[hi] > a[k]: count += hi - lo hi -= 1 else: lo += 1

Fixing the largest is what makes the block count work. If a[lo] + a[hi] > a[k], then every value between lo and hi is at least a[lo], so pairing any of them with a[hi] also exceeds a[k]. That is hi - lo triples in one comparison, and then a[hi] is finished.

Compare with 608, where the block was counted by advancing lo. The direction follows from which side of the inequality is being satisfied, and copying the other problem's loop without thinking is the usual error.

## Why fixing the smallest would be harder

With a[i] fixed as the SHORTEST side, the condition a[i] + a[j] > a[k] involves both remaining indices on opposite sides of the comparison, and no single pointer move settles a block. Choosing which element to fix is part of designing the sweep.

## Boundaries

Fewer than three lengths gives 0.

1 1 1 gives 1. Equal lengths always work, since x + x > x for positive x.

1 2 4 8 16 gives 0: each length is at least the sum of all smaller ones, so nothing forms a triangle.

## Overflow

Two lengths near 10^9 sum to 2 * 10^9, which FITS in a signed 32 bit integer, since the limit is 2147483647. The comparison inside the loop is therefore safe in 32 bits.

The COUNT is the quantity that does not fit. C(3000, 3) is 4495501000, more than twice the limit, so the answer needs 64 bits even though every value being compared to build it does not. That split is the point: the width a problem needs is a property of the OUTPUT as much as of the input. Both need 64 bits.

## Cost

Time O(n^2). Space O(1) beyond the input.

Constraints - `3 ≤ n ≤ 3000` - `1 ≤ each length ≤ 10^9`