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 condition for the triplets representing the lengths of the sides of a triangle, to form a valid triangle, is that the sum of any two sides should always be greater than the third side alone. i.e. , , .
The simplest method to check this is to consider every possible triplet in the given array and checking if the triplet satisfies the three inequalities mentioned above. Thus, we can keep a track of the of the number of triplets satisfying these inequalities. When all the triplets have been considered, the gives the required result.
Complexity Analysis
Time complexity : . Three nested loops are there to check every triplet.
Space complexity : . Constant space is used.
Algorithm
If we sort the given array once, we can solve the given problem in a better way. This is because, if we consider a triplet such that , we need not check all the three inequalities for checking the validity of the triangle formed by them. But, only one condition would suffice. This happens because and . Thus, adding any number to will always produce a sum which is greater than either or considered alone. Thus, the inequalities and are satisfied implicitly by virtue of the property .
From this, we get the idea that we can sort the given array. Then, for every pair considered starting from the beginning of the array, such that (leading to ), we can find out the count of elements (), which satisfy the inequality . We can do so for every pair considered and get the required result.
We can also observe that, since we've sorted the array, as we traverse towards the right for choosing the index (for number ), the value of could increase or remain the same(doesn't decrease relative to the previous value). Thus, there will exist a right limit on the value of index , such that the elements satisfy . Any elements beyond this value of won't satisfy this inequality as well, which is obvious.
Thus, if we are able to find this right limit value of (indicating the element just greater than ), we can conclude that all the elements in array in the range (both included) satisfy the required inequality. Thus, the of elements satisfying the inequality will be given by .
Since the array has been sorted now, we can make use of Binary Search to find this right limit of . The following animation shows how Binary Search can be used to find the right limit for a simple example.
!?!../Documents/Valid_Triangle_Binary.json:1000,563!?!
Another point to be observed is that once we find a right limit index for a particular pair chosen, when we choose a higher value of for the same value of , we need not start searching for the right limit from the index . Instead, we can start off from the index directly where we left off for the last chosen.
This holds correct because when we choose a higher value of (higher or equal than the previous one), all the , such that will obviously satisfy for the new value of chosen.
By taking advantage of this observation, we can limit the range of Binary Search for to shorter values for increasing values of considered while choosing the pairs .
Complexity Analysis
Time complexity : . In worst case inner loop will take (binary search applied times).
Space complexity : . Sorting takes space.
Algorithm
As discussed in the last approach, once we sort the given array, we need to find the right limit of the index for a pair of indices chosen to find the of elements satisfying for the triplet to form a valid triangle.
We can find this right limit by simply traversing the index 's values starting from the index for a pair chosen and stopping at the first value of not satisfying the above inequality. Again, the of elements satisfying for the pair of indices chosen is given by as discussed in the last approach.
Further, as discussed in the last approach, when we choose a higher value of index for a particular chosen, we need not start from the index . Instead, we can start off directly from the value of where we left for the last index . This helps to save redundant computations.
The following animation depicts the process:
!?!../Documents/Valid_Triangle_Linear.json:1000,563!?!
Complexity Analysis
Time complexity : . Loop of and will be executed times in total, because, we do not reinitialize the value of for a new value of chosen(for the same ). Thus the complexity will be O(n^2+n^2)=O(n^2).
Space complexity : . Sorting takes O(logn) space.
Analysis written by: @vinod23