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.

Triangles.java

// if a > b and a > c, then a < b + c for a triangle to be formed
public int triangleNumber(int[] a) {
    int n = a.length;
    if(n < 3) return 0;
    int count = 0;

    Arrays.sort(a);
    for(int i = 2; i < n; i++) {
        int left = 0, right = i-1;
        while(left < right) {
            if(a[left] + a[right] > a[i]){
		// (left, right, i), (left+1, right, i) .. (right-1, right, i) are all valid
                count += right-left;
                right--;
            }
            else
                left++;
        }
    }

    return count;
}