_611.java

package com.fishercoder.solutions;

import java.util.Arrays;

/**
 * 611. Valid Triangle Number
 * Given an array consists of non-negative integers,
 * your task is to count the number of triplets chosen
 * from the array that can make triangles if we take them as side lengths of a triangle.

 Example 1:
 Input: [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

 Note:
 The length of the given array won't exceed 1000.
 The integers in the given array are in the range of [0, 1000].
 */
public class _611 {
    /**Rule: among three sides, we need to find whether the longest of the three is smaller than the sum of the two shorter one.
     * If so, then these three could form a valid triangle.*/

    public int triangleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int triplets = 0;
        for (int i = 2; i < nums.length; i++) {
            int left = 0;
            int right = i - 1;
            while (left < right) {
                if (nums[i] < nums[left] + nums[right]) {
                    triplets += (right - left);
                    right--;
                } else {
                    left++;
                }
            }
        }
        return triplets;
    }

}