142. Triangle Triples
A craftsman has a box of wooden sticks, and the array sides holds the length of each stick. He wants to know how many different ways there are to pick three sticks that can be joined end to end into a triangle with a positive area.
Count the triples of indices i < j < k such that the three lengths sides[i], sides[j], sides[k] satisfy the triangle rule: the sum of any two of them is strictly greater than the third. Sticks with equal lengths at different positions are different sticks, so such choices are counted separately. A stick of length 0 can never be part of a valid triple. Return the number of valid triples.
Example 1
- Input:
- sides = [4,6,3,7]
- Output:
- 3
- Explanation:
Of the four triples, (4,6,3), (4,6,7) and (6,3,7) are valid. The triple (4,3,7) is degenerate because 3+4=7 is not strictly greater than 7. The answer is 3.
Example 2
- Input:
- sides = [2,2,2,2]
- Output:
- 4
- Explanation:
Every choice of three of the four equal sticks forms a triangle, and there are 4 such choices.
Example 3
- Input:
- sides = [1,2,3]
- Output:
- 0
- Explanation:
1+2=3 is not strictly greater than 3, so the only triple is degenerate and the answer is 0.
Constraints
1 ≤ sides.length ≤ 2000
0 ≤ sides[i] ≤ 106
The answer is at most C(2000, 3), which fits in a 32-bit integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n^2)
- Space
- O(1) extra