Count how many triplets in an array can form the sides of a valid triangle.
Problem
Given an integer array nums, count the number of index triplets (i, j, k) with i < j < k such that the three values can be the side lengths of a non-degenerate triangle.
A triplet forms a valid triangle if the sum of any two sides is strictly greater than the third side.
Return the total number of valid triplets.
Notes
- Side lengths must be positive.
- Because the array may contain repeated values, different index triplets are counted separately.
- You only need to return the count, not the actual triplets.
Input Format
- An integer array
nums. - Each value represents a possible side length.
Output Format
- Return an integer: the number of index triplets that can form a triangle.
Constraints
3 <= nums.length1 <= nums[i]- The answer fits in a 32-bit signed integer for typical interview constraints.
Example 1
Input
nums = [2,2,3,4]
Output
3
Explanation
The valid triplets are (2,3,4), (2,3,4), and (2,2,3) using different indices. After sorting, you can count all index triplets whose three sides satisfy the triangle inequality.
Example 2
Input
nums = [4,2,3,4]
Output
4
Explanation
The four valid triplets correspond to the index combinations that form side lengths (2,3,4), (2,4,4), (3,4,4), and another (2,3,4) using the remaining 4.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.