"""The time complexity can be greatly reduced using Two Pointer methods in just two nested loops.
Approach: First sort the array, and run a nested loop, fix an index and then try to fix an upper and lower index within which we can use all the lengths to form a triangle with that fixed index.
Algorithm:
Sort the array and then take three variables l, r and i, pointing to start, end-1 and array element starting from end of the array.
Traverse the array from end (n-1 to 1), and for each iteration keep the value of l = 0 and r = i-1
Now if a triangle can be formed using arr[l] and arr[r] then triangles can obviously formed
from a[l+1], a[l+2]…..a[r-1], arr[r] and a[i], because the array is sorted , which can be directly calculated using (r-l). and then decrement the value of r and continue the loop till l is less than r
If a triangle cannot be formed using arr[l] and arr[r] then increment the value of l and continue the loop till l is less than r
So the overall complexity of iterating
through all array elements reduces.
"""
def CountTriangles( A):
n = len(A);
A.sort();
count = 0;
for i in range(n - 1, 0, -1):
l = 0;
r = i - 1;
while(l < r):
if(A[l] + A[r] > A[i]):
count += r - l;
r -= 1;
else:
l += 1;
print("No of possible solutions: ", count);
if __name__ == '__main__':
A = [ 4, 3, 5, 7, 6 ];
CountTriangles(A);