Count Possible Triangles  


Difficulty Level Medium
Frequently asked in Amazon LinkedIn Wipro
Array Math

Problem Statement  

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.

See also
Dividing Array into Pairs With Sum Divisible by K

Implementation  

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[0]),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 n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cout<<"Total number of Triangles can be formed is = "<<TrianglesCount(input_array,n);
    return 0;
}

Java Program for Count Possible Triangles

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static int TrianglesCount(int arr[], int n) 
    { 
        Arrays.sort(arr);
        int count = 0; 
        for (int i = 0; i < n - 2; ++i) { 
            int k = i + 2; 
            for (int j = i + 1; j < n; ++j) { 
                while (k < n && arr[i] + arr[j] > arr[k]) 
                    ++k; 
                if (k > j) 
                    count += k - j - 1; 
            } 
        } 
        return count; 
    } 
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        } 
        int ans = TrianglesCount(arr,n);
        System.out.println("Total number of Triangles can be formed is = " + ans);
    } 
}
5
2 3 4 5 6
Total number of Triangles can be formed is = 7

Complexity Analysis  

Time Complexity

O(n^2) where n is the number of elements present in the given array. The time complexity looks more because of 3 nested loops. It can be observed that k is initialized only once in the outermost loop. The innermost loop executes at most O(n) time for every iteration of the outermost loop, because k starts from i+2 and goes up to n for all values of j. Therefore, the time complexity is O(n^2).

Space Complexity

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

See also
4Sum

References