Valid Triangle Number
Understanding the Problem
Three side lengths form a valid triangle if and only if the sum of any two sides is strictly greater than the third. So for sides a, b, and c, all three of these must hold: a + b > c, a + c > b, and b + c > a.
Sorting the sides simplifies this. If a <= b <= c, only a + b > c needs checking. The other two hold automatically: c is the largest side, so b + c >= a + b > c >= a gives b + c > a, and a + c >= a + b > c >= b gives a + c > b. Adding the largest side to either of the others always clears the third.
So the problem reduces to: sort the array, then count all triplets (i, j, k) where i < j < k and nums[i] + nums[j] > nums[k].
Key Constraints:
1 <= nums.length <= 1000→ With n up to 1000, O(n^3) means a billion operations, which is too slow. O(n^2 log n) or O(n^2) should work fine.0 <= nums[i] <= 1000→ Values can be zero. A triangle cannot have a side of length 0, so any triplet containing a zero is automatically invalid.
Approach 1: Brute Force
Intuition
Check every possible triplet. Pick three elements, and test whether the two smaller ones sum to more than the largest. If they do, count it.
Three nested loops enumerate all combinations of three elements. Sorting the array first means each triplet needs one comparison instead of three, because the indices i < j < k already correspond to the smallest, middle, and largest of the three.
Algorithm
- Sort the array in ascending order.
- Use three nested loops with indices i < j < k to enumerate all triplets.
- For each triplet, since the array is sorted, check if
nums[i] + nums[j] > nums[k]. - If the condition holds, increment the count.
- Return the count.
Example Walkthrough
Code
- Time Complexity: O(n^3). Three nested loops, each iterating up to n times. Sorting is O(n log n) but dominated by the cubic term.
- Space Complexity: O(1). Only a few variables beyond the sort's internal space.
The cubic loop is too slow for n = 1000. The next approach fixes the two smaller sides and uses binary search to locate the boundary where the third side becomes too large, replacing the innermost loop with a logarithmic search.
Approach 2: Sorting + Binary Search
Intuition
After sorting, for a fixed pair (i, j), we need the count of indices k > j where nums[k] < nums[i] + nums[j]. The values nums[j+1], nums[j+2], ..., nums[n-1] are in non-decreasing order, so every value below the sum forms a contiguous block starting at j+1. Binary search finds the right boundary of that block in O(log n), and the count of valid k values is boundary - j.
Algorithm
- Sort the array.
- For each pair (i, j) where i < j:
- Compute the target sum
nums[i] + nums[j]. - Binary search in
nums[j+1..n-1]for the rightmost index where the value is still less than the target sum. - Add
(rightmost_index - j)to the count. - Return the count.
Example Walkthrough
Code
- Time Complexity: O(n^2 log n). Two nested loops give O(n^2) pairs. For each pair, a binary search over at most n elements takes O(log n).
- Space Complexity: O(1). Beyond the sort's internal space, we use only a few variables.
The binary search restarts from scratch for each pair, discarding work between iterations. The next approach fixes the largest side and uses two pointers to count all valid pairs for it in a single linear sweep, removing the logarithmic factor.
Approach 3: Sorting + Two Pointers (Optimal)
Intuition
Instead of fixing the two smaller sides and searching for the largest, fix the largest side nums[k] and use two pointers to count valid pairs. This brings the work down to O(n^2).
After sorting, iterate k from the end of the array to index 2. For each k, set left = 0 and right = k - 1. Now check whether nums[left] + nums[right] > nums[k]:
- If yes, then every index from left to right-1 also pairs with right to form a valid triangle. So we add
right - leftto the count and decrement right. - If no, the sum is too small. Increment left to try a larger value.
When nums[left] + nums[right] > nums[k], any index between left and right-1 paired with right also satisfies the inequality, because the array is sorted and a larger left value only increases the sum. That accounts for right - left pairs at once, and right then moves down to a smaller largest-of-the-two side.
When nums[left] + nums[right] <= nums[k], right is the largest available partner for left, so no smaller right could satisfy the inequality with this left. Advancing left to a larger value is the only move that can help, and it never skips a valid pair.
Algorithm
- Sort the array in ascending order.
- Iterate k from
n - 1down to2(fixing the largest side). - For each k, set
left = 0andright = k - 1. - While
left < right: - If
nums[left] + nums[right] > nums[k], addright - leftto the count, then decrement right. - Otherwise, increment left.
- Return the count.
Example Walkthrough
Code
- Time Complexity: O(n^2). Sorting takes O(n log n). The outer loop runs n times, and for each k, the two-pointer scan runs in O(k) time. The total work across all k values is O(n^2).
- Space Complexity: O(1). Only a few integer variables beyond the sort's internal O(log n) space.