Facade design pattern
January 2, 2013
Adapter design pattern (wrapper)
January 3, 2013

Number of possible triangles from given array of numbers

Given an array of numbers, write an algorithm to count how many triangles are possible with three numbers from array as their side.
If input array is: {7, 3, 6, 4}
Then the output should be 3 because there are 3 possible triangles, viz.: {3, 4, 6}, {3, 6, 7} and {4, 6, 7}.

In a triangle, the sum of two sides is always greater than the third side. i.e a, b and c are sides of a triangle if all the three conditions are true

a + b > c
b + c > a
c + a > b

In the above case {3, 4, 7} cannot be the sides of a triangle because 3+4 is not greater than 7 (should be strictly greater than the third side, and not equal).
In the above question, we are only interested in the count of triangles. Hence the signature of the function is

int countTriangles(int* arr, int n)

Bruite force method is to have three loops and consider all possible combinations of i,j,k. This method will take O(n3) time.
O(n^2) Solution
There is another O(n2) time algorithm which sort the array and then does not traverse the entire array in all the three loops.
Algorithm:

1. Sort the array in increasing order.
2. Initialize
   i = 0;      // First Element
   j = 1;      // Second Element
   count = 0;  // Number of triangles
3. WHILE (i<n-2)
     k = j+1;
     move k forward until arr[k] becomes > (arr[i] + arr[j]) or k moves out of bound
     count = count + (k-j-1);
     increment j
     if j is at end of array
       increment i and set j=i+1
4. Print count.

Note that in this case pointer ‘k‘ is not reset every time j is incremented, because since j is increasing, we need a higher value of ‘k‘ which will be on the right side. Hence we just need to move k forward.
k is reset only when i and j both are reset, because in that case k has already reached the upper bound of array.
Code:

int countTriangles(int* arr, int n)
{
    // atleast 3 numbers are required for a triangle.
    if(n<3) return 0;
    quickSort(arr, 0, n-1);
    int count = 0;
    int i = 0;
    int j = i+1;
    while(i<n-2)
    {
        int k = j+1;
        while(k<n && arr[k] < arr[i] + arr[j])
            k++;
        count += k-j-1;
        j++;
        // If j has reached the end. then reset both i & j.
        if(j>=n)
        {
            i++;
            j = i+1;
        }
    }
    return count;
}

Time Complexity: O(n2)
Extra Space Used: O(1)

3 Comments

  1. This is not correct , for input {10, 21, 22, 100, 101, 200, 300} no . of triangles should be 6 but your code will 5 , which is wrong.
    {10, 21, 22}, {21, 100, 101}, {22, 100, 101}, {100, 101, 200} and {101, 200, 300} v {10, 100, 101}

  2. gIVA says:

    Thanks, This really quick explanation saved a hell lot of time!

  3. Kalyanasundaram says:

    Why sort?
    Am I missing something? Kindly verify and correct me. Thanks

    #include
    int main()
    {

    int array[] = {10, 21, 22, 100, 101, 200, 300};

    int size = sizeof(array)/sizeof(array[0]);
    int start = 0, end = size-1;

    int i = 0, count = 0;
    int j = i+1;
    int k = j+1;

    while(i array[k])
    {
    printf(“{%d, %d, %d} “, array[i], array[j], array[k]);
    count++;

    if(k >= size-1)
    {
    i++;
    j = i+1;
    k = j+1;
    }
    else
    {
    j++;
    k++;
    }

    }
    else if(k >= size-1)
    {
    i++;
    j = i+1;
    k = j+1;
    }
    else
    {
    j++;
    k++;
    }
    }
    printf(“\nNumber of possible triangles can be formed from the array is: %d\n”, count);
    return 0;
    }

Leave a Reply to Anonymous Cancel reply

Your email address will not be published. Required fields are marked *