Valid Triangle Number
MediumCount triples that form a triangle
Sort the sticks; if the two shorter ones together are longer than the longest, they can make a triangle.
The idea
Sort the sides. Fix the longest side, then use two pointers: if the two shorter sides already beat it, every pair between them works too — count them all at once.
2
2
3
4
0
1
2
3
Step 1 of 7. Sort the sides. Three sides form a triangle when the two shorter ones beat the longest. Values: 2, 2, 3, 4.
1/7
Optimal
timeO(n²)spaceO(1)
Fix the long side, count valid pairs.
1let count = 0;2nums.sort((a, b) => a - b);3for (let k = n - 1; k >= 2; k--) {4 let l = 0, r = k - 1;5 while (l < r) {6 if (nums[l] + nums[r] > nums[k]) {7 count += r - l; r--;8 } else l++;9 }10}11return count;Input
- array
- [2, 2, 3, 4]
Memory
- k
- —
- L
- —
- R
- —
Output
- count
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [2, 2, 3, 4]
- Output:
- 3
- Explanation:
- 3 valid triangles can be formed.
Example 2
- Input:
- nums = [4, 2, 3, 4]
- Output:
- 4
- Explanation:
- 4 valid triangles here.
Example 3
- Input:
- nums = [1, 1, 1]
- Output:
- 1
- Explanation:
- An equilateral trio counts as 1.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.