Valid Triangle Number

Problem Statement

The objective is to determine the number of possible triplets that can be selected from an integer array nums, where each triplet forms the sides of a viable triangle. To clarify, a set of three numbers can be the sides of a triangle if and only if the sum of any two sides is greater than the third side. This is referred to as the Triangle Inequality Theorem. Thus, given an array of integers, nums, the challenge is to count all such triplets that satisfy this condition.

Examples

Example 1

Input:

nums = [2,2,3,4]

Output:

3

Explanation:

Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Example 2

Input:

nums = [4,2,3,4]

Output:

4

Constraints

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

Approach and Intuition

1. To find viable triplets that can form a triangle, we should first understand the Triangle Inequality Theorem which states:

   • For any triplet (a, b, c), they can form a triangle if:
     • a + b > c
     • a + c > b
     • b + c > a However, by ensuring the numbers are sorted in non-decreasing order (a <= b <= c), we only need to check if a + b > c, because the other two conditions will inherently be satisfied.

2. A practical approach to solving this problem is:

   • Sort the array nums in non-decreasing order.
   • Iterate through the array using three indices: i, j, and k:
     • Fix index k as the largest number of the triplet.
     • For each k, initiate two pointers: i starting from the beginning of the array, and j starting from k-1.
     • Move the two pointers towards each other checking the sum of nums[i] + nums[j]:
       • If nums[i] + nums[j] is greater than nums[k], every triplet formed by using nums[i] to every nums[j - 1], along with nums[k], will satisfy the condition. Increase the triplet count by j - i, and move j one step back (decrement j).
       • If the sum is not greater, just move i one step forward (increment i).
   • Repeat the above until i < j for each fixed k.

3. By performing above steps, all relevant combinations can be checked in a systematic and efficient manner.

Example insights:

• From the first example, input [2,2,3,4] sorts to the same array as input is already sorted. By iterating k from index 2 to 3, different i and j values explore all viable triplets. For each k, adjust i and j such that the sum condition is examined.
• Similarly, for the second example, sorts of [4,2,3,4] to [2,3,4,4]. Applying the same logic yields all possible combinations that satisfy the condition.

Following this step-by-step method ensures that each possible combination is considered without redundancy, and the conditions for a valid triangle are maintained.

Solutions

public class Solution {
    public int countTriangles(int[] numbers) {
        int total = 0;
        Arrays.sort(numbers);
        for (int first = 0; first < numbers.length - 2; first++) {
            int third = first + 2;
            for (int second = first + 1; second < numbers.length - 1 && numbers[first] != 0; second++) {
                while (third < numbers.length && numbers[first] + numbers[second] > numbers[third])
                    third++;
                total += third - second - 1;
            }
        }
        return total;
    }
}