# Count the number of possible triangles CPP Method 3

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:

1. 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.

2. Traverse the array from end (n-1 to 1), and for each iteration keep the value of l = 0 and r = i-1

3. 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

4. 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

5. 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[r-1], 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