Home » Technical Interview Questions » Array Interview Questions » Count Possible Triangles

# Count Possible Triangles

In count possible triangles problem we have given an array of n positive integers. Find the number of triangles that can be formed using three different elements of the array as the sides of a triangle.

Note: The condition of the triangle is the sum of two sides of a triangle is greater than the third side.

## Example

Input

arr[] = {2, 3, 4, 5, 6, 7}

Output

13

Explanation

All the possible triplet are-

{2, 3, 4}, {2, 4, 5}, {2, 5, 6},{2, 6, 7}, {3, 4, 5}, {3, 4, 6},{3, 5, 6}, {3, 5, 7}, {3, 6, 7}, {4, 5, 6}, {4, 5, 7}, {4, 6, 7}, {5, 6, 7}

## Algorithm for Count Possible Triangles

Now we understand the problem statement clearly. So, without wasting too much time on the theory we directly move to the algorithm used for finding the number of triangles in the array.

a. Sort the given array in increasing order.

b. Take three positions i, j, and k

• i for the first element. i is from 0 to n – 3.
• j for the second element. i is from i + 1 to n – 2.
• k for the third element. k is from i+ 2 to n -1.

c. Find the rightmost element which is smaller than the sum of the current i and j by moving k.
d. K – j – 1 is the count of triangles, for current i and j.
e. Add it to the count and increment i, j.

## C++ Program for Count Possible Triangles

```#include <bits/stdc++.h>
using namespace std;

int compare(const void* a, const void* b)
{
return *(int*)a > *(int*)b;
}
int TrianglesCount(int array[], int n)
{
qsort(array,n,sizeof(array),compare);
int count = 0;
for(int i = 0; i < n-2; ++i)
{
for (int j = i+1; j < n; ++j)
{
int k = j+1;
while (k < n && array[i] + array[j] > array[k])
{
k = k + 1;
}
count=count+k-j-1;
}
}
return count;
}
//Main function
int main()
{
int input_array[] =   {2, 3, 4, 5, 6};
int size = sizeof(input_array)/sizeof(int);
cout<<"Total number of Triangles can be formed is = "<<TrianglesCount(input_array,size);
return 0;
}```
`Total number of Triangles can be formed is = 7`

## Complexity Analysis

### Time Complexity

O(n^3) where n is the number of elements present in the given array. Here we find all the triplet possible after sort the array such that a[i]+a[j] > a[k] where i<j<k. In the worst case, the time complexity will be n^3.

### Space Complexity

O(1) because we create a few variables that lead us to constant space complexity.

References

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions 