Valid Triangle Number
From LeetCode. Counting triangles from side lengths. Solve the geometry problem "Valid Triangle Number".
Examples
Input: [1,2,3]
Output: 0
Input: [2,3,4]
Output: 0
Hints
Sort the array first. For any sorted triple `(i, j, k)` with `i < j < k`, the only inequality you need to verify is `nums[i] + nums[j] > nums[k]` — the other two are automatically satisfied.
Use the two-pointer technique: fix `i` from `0` to `n-3`, then advance `k` outward as `j` moves right. For each `(i, j)`, find the first `k` where the sum check fails — all indices between `j+1` and `k-1` are valid third sides.
The count of valid triangles for a given `(i, j)` is `k - j - 1`. Accumulate this across all `(i, j)` pairs. This runs in O(n²), which passes for the typical 1000-element input limit.
Valid Triangle Number
**From LeetCode.** Counting triangles from side lengths. Solve the geometry problem "Valid Triangle Number".