public static int triangleNumber(int[] A) {
Arrays.sort(A);
int count = 0, n = A.length;
for (int i=n1;i>=2;i) {
int l = 0, r = i1;
while (l < r) {
if (A[l] + A[r] > A[i]) {
count += rl;
r;
}
else l++;
}
}
return count;
}
Java O(n^2) Time O(1) Space


@compton_scatter said in Java O(n^2) Time O(1) Space:
count += rl;
Can you please explain why is the rl being added to the count?
If you use [2,2,4,5], (2(index 0)+4(index 2)) > 5. Why do you increase the count by 2 rather than 1?

@thallam
rl
keeps track of number of pairs fromr
tol
that forms a valid triplet (follows triangle inequality property) with the third side represented byi
In this case >[2,4] and [2,4]
are the two pairs (using first 2 and second 2)

@thallam said in Java O(n^2) Time O(1) Space:
Can you please explain why is the rl being added to the count?
If you use [2,2,4,5], (2(index 0)+4(index 2)) > 5. Why do you increase the count by 2 rather than 1? The array is sorted.
 By (1), the elements at the right side of the first 2 are guaranteed to be larger than or equal to the first 2.
 By (2), if the sum of the first 2 and 4 is larger than 5, it implies that the sum of 4 and the numbers to the right of the first 2 is larger than 5.
 By (3), you can safely include all pairs between
rl
to the solution.

@thallam said in Java O(n^2) Time O(1) Space:
Can you please explain why is the rl being added to the count?
If you use [2,2,4,5], (2(index 0)+4(index 2)) > 5. Why do you increase the count by 2 rather than 1?I have a similar solution 
public class Solution {
public int triangleNumber(int[] nums) {if(nums.length < 3) return 0; Arrays.sort(nums); int hi = nums.length1, count = 0; for(; hi > 1; hi){ int lo = 0, mid = hi  1; while(lo < mid){ if(nums[lo] + nums[mid] <= nums[hi]) lo++; else{ count+=midlo; mid; } } } return count; }
}
The idea is that once we find the combination <lo, mid, hi> such that lo+mid > hi, there is no need to increment lo, for this mid and hi combination, all the lo between lo and mid will satisfy the condition. Hence we just add (midlo) to our answer count.

 Remember, the array is sorted
 If the sum of two small elements (at left index and right index) is greater than the rightmost element (largest), then it is obvious that the subsequent sum of pairs will be greater than the rightmost element.
In your case [2,2,4,5], if (2+4 > 5) then keeping the right index at the same position and increasing the left (the second 2+4 is obviously > 5)  The reason for count+=rl is to find out how many pairs satisfy this property
In this case, there are two pairs that satisfy this property (2,4) and (2,4). since the right index is decremented, the count becomes rl which is 20 (2 pairs).
I had the same doubt and I tried to work with different examples to understand.



@compton_scatter
have someone think about traverse the array from 0 to n1?
this solution is i from n1 to 0, just judge a[low]+a[high] > a[i]. When I first thought is from i from 0 to n1, low = i+1 ,high = n1; judge [high] [low] < [i] ,we get combination
C(2,lowhigh+1),but when [high] [low] > [i] ,i cannot think clearly high1 or low +1 . [high1][low] and [high][low+1] , both are possible less than [i], so i think it become more complex.