Method 3: 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, end1 and array element starting from end of the array.

Traverse the array from end (n1 to 1), and for each iteration keep the value of l = 0 and r = i1

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[r1], arr[r] and a[i], because the array is sorted , which can be directly calculated using (rl). 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.


Implementation:

C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using
namespace
std;
void
CountTriangles(vector<
int
> A)
{
int
n = A.size();
sort(A.begin(), A.end());
int
count = 0;
for
(
int
i = n  1; i >= 1; i) {
int
l = 0, r = i  1;
while
(l < r) {
if
(A[l] + A[r] > A[i]) {
// If it is possible with a[l], a[r]
// and a[i] then it is also possible
// with a[l+1]..a[r1], a[r] and a[i]
count += r  l;
// checking for more possible solutions
r;
}
else
// if not possible check for
// higher values of arr[l]
l++;
}
}
cout <<
"No of possible solutions: "
<< count;
}
int
main()
{
vector<
int
> A = { 4, 3, 5, 7, 6 };
CountTriangles(A);
}
Output:
No of possible solutions: 9

Complexity Analysis:

Time complexity: O(n^2).
As two nested loops are used, but overall iterations in comparison to the above method reduces greatly. 
Space Complexity: O(1).
As no extra space is required, so space complexity is constant

Time complexity: O(n^2).