Valid Triangle Number

LeetCode Q 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]

Solution

Solution : Two pointers

Brute-force method:

for (i = 0; i < len - 2; i++) {
	for (j = i + 1; j < len - 1; j++) {
		for (k = j + 1; k < len; k++) {
			if (nums[i] + nums[j] > nums[k]) count++;
		}
	}
}

Time complexity is O(n^3).

We can simply the above method using two pointers, then the ime complexity becomes O(n^2).

Code:

public int triangleNumber(int[] nums) {
	
	Arrays.sort(nums);

	int res = 0;
	for (int k = nums.length - 1; k >= 2; k--) {
		
		int l = 0, right = k - 1;
		
		while (l < r) {
			if (nums[l] + nums[r] > nums[k]) {
				res += (r - l);
				r--;
			} else {
				l++;
			}
		}
	}

	return res;
}