Triangle-Ready Triplets
MediumTwo Pointers
Problem
A workshop has rods of lengths sides. Three rods at different positions can form a triangle with positive area when the two shorter ones together are strictly longer than the longest.
Return how many index triplets i < j < k can form such a triangle.
Example 1
- Input:
- sides = [4, 2, 3, 5]
- Output:
- 3
(4, 2, 3), (4, 2, 5) and (4, 3, 5) work; (2, 3, 5) fails because 2 + 3 = 5 is not strictly longer than 5.
Example 2
- Input:
- sides = [1, 1, 10]
- Output:
- 0
Constraints
- 1 ≤ sides.length ≤ 1000
- 0 ≤ sides[i] ≤ 1000
Hint
Show the first hint
After sorting, only one of the three triangle inequalities can fail. Which one?
Walkthrough
How to approach it
01Clarify before coding
- Strictly greater? Yes, a degenerate triangle (a + b = c) does not count.
- Counted by positions, not by distinct lengths? By positions.
- Can lengths be zero? Yes; a zero-length rod never forms a triangle.
02Brute force
Check all triples and test the three inequalities.
Cost: O(n³): about 1.7·10^8 triples for n = 1000.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.