427. Valid Triangle Number
You are given an array of non-negative integers nums, where each value is a candidate stick length. Count how many index triples i < j < k pick three sticks that could be bent into a triangle with positive area — every pair of chosen sides must sum to strictly more than the remaining side.
Triples are distinguished by index, not by value: two sticks of the same length picked at different positions count as different choices. Return the count as a single integer.
Example 1:
Input: nums = [2, 2, 3, 4]
Output: 3
Explanation: The winning combinations are 2,3,4 (using the first 2), 2,3,4 (using the second 2), and 2,2,3. The triple 2,2,4 fails because 2 + 2 = 4 is not strictly greater than 4.
Example 2:
Input: nums = [4, 2, 3, 4]
Output: 4
Explanation: Sorted, the sticks are [2, 3, 4, 4]. Valid picks: (2,3,4) twice — once per 4 — plus (2,4,4) and (3,4,4).
Constraints:
- 1 ≤ nums.length ≤ 1000
- 0 ≤ nums[i] ≤ 1000
Hints:
Order inside a triple never matters, so sort the whole array first. For sorted sides a <= b <= c, the three triangle inequalities collapse into the single check a + b > c.
Fix the LARGEST side nums[k] and hunt for pairs among the smaller values. If binary search feels natural, count, for each pair (i, j), how many larger values stay below nums[i] + nums[j].
Two pointers beat the log factor: with i at the left and j just under k, if nums[i] + nums[j] > nums[k] then every index between i and j also works with j — add j − i at once and move j down; otherwise move i up.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [2, 2, 3, 4]
Expected output: 3