Count Triangles formed by the elements of array

Problem Statement

Given a sorted array of distinct integers, each of these integers can represent a length. The task at hand is to count the number of possible triangles which can be made through these lengths.

Of course, if you chose one length to be one side of the triangle, you cannot use that length again in the same triangle. This means, no triangle contains the same length more than once.

Important Note: For given sides of lengths a, b and c. A triangle can only be formed if sum of any two sides is greater than the third side. This is called the triangle inequality. The sum of any two sides must be greater than the third side.

Solution

The first solution one can think is a brute force one where, we fix two sides and evaluate for the third side to match the triangle inequality. This works fine and offers the correct result. Here is the brute force algorithm:

  1. Let us fix the ith element of an array as one side.
  2. Fix the jth element as (i+1) of the array as the other side.
  3. Iterate k from i+2 to N evaluating for each of these length to satisfy the triangle in equality A[i]+A[i+1] > A[k] .
    • This works because, if the sum of the two smaller sides is greater than the biggest side, then all three combinations of the sides will honor the triangle in equality.
  4. Repeat steps 2 and 3 till j is less than N – 1
  5. Repeat all the above steps till i < N – 2.

Here is the source code for the brute force method.

 

Let us analyze the running time of the above code.

  • For s1 = 0 , the s2 loop runs N-2 times and the s3 loop runs for N-2 times.
  • For s1 = 1, the s2 loop runs N-3 times and so does the s3 loop.
  • This continues till, s1 = N – 3, in which case the s2 loop runs for N – (N-3) – 1, which is equal to 2 times and so on.

If we sum up the total running time it would generate the following series.
1 + 2 * 2 + 3 * 3 + … + (N-3)  * ( N-3) + (N-2) * (N-2) , which clearly is the sum of N-2 consecutive squares.

This equals to ((N-2) * (N-1) * (2N – 3) ) / 6 . This clearly is a O(N3) solution. This is the worst case running time and not a strict bound. As you can see, we break out from the loop when the first element disobeys the triangle in equality.

An efficient solution

We can possibly do better because we know a lot of things about the array. The array is a sorted one and the triangle in equality allows us to discard a range of the elements without even testing for triangle existence.

May be we need to look at the array from both the sides because we know that for two sides of length A[N] and A[N-1], if we find the first element A[k] such that it satisfies the triangle in equality, then all the elements within the range k to N – 1 will create one triangle each.

We can re do this activity by fixing A[N-1]  and A[N-2] as two sides and so on.

Here is the source code for the same:

Explanation

Here are few images to explain the idea.

In the first iteration of the outer loop,

  • We fix one side at end, to the last element of the array
  • We fix another side at k, the element just before the end.
  • A start pointer, points at the first element of the array and tests for triangle inequality.
    • If the triangle inequality is not satisfied, then move start one step at a time. (Steps 2, 3 and 4 in the below diagram).
    • If the triangle equality is satisfied, then everything between start and k will form one triangle each. (which is not the case in iteration 1)

 

Count Triangles

 

In the second iteration of the outer loop,

  • Fix one side to end which is second last element of the array.
  • Fix the other side to k, one less than end.
  • The start pointer is again set to the beginning of the array. Test for triangle inequality
    • If the triangle inequality satisfies, then all elements between start and k will form one triangle each. For e.g.: {2,7,8}, {4,7,8},{6,7,8} are the three possible triangles.
    • Now, we can re fix the second side by decreasing k by 1 (See step 2 in below diagram) and if it satisfies the triangle inequality then all elements between start and k will form one triangle each. Here the triangle inequality is not satisfying. So, we increase start by 1 (see step 3 in the below diagram. Hence one triangle is possible {4, 6, 8}.

Count Triangles

In the third iteration of the outer loop,

  • Fix one side to end which is third last element of the array.
  • Fix the other side to k, one less than end.
  • The start pointer is again set to the beginning of the array. Test for triangle inequality
    • If the triangle inequality satisfies, then all elements between start and k will form one triangle each. For e.g.: {2, 6,7}, {4,6,7} are the two possible triangles.
    • Now, we can re fix the second side by decreasing k by 1 (See step 2 in below diagram) and if it satisfies the triangle inequality then all elements between start and k will form one triangle each. Here the triangle inequality is not satisfying.

Count Triangles

In the fourth iteration of the outer loop,

  • Fix one side to end which is fourth last element of the array.
  • Fix the other side to k, one less than end.
  • The start pointer is again set to the beginning of the array. Test for triangle inequality
    • If the triangle inequality satisfies, then all elements between start and k will form one triangle each. However, the triangle inequality is not satisfying. Hence zero triangles.

triangle4

The process clearly is of the order O(N2) as the outer loop runs for the length of the array and the inner loop from 0 to i where i is the current iteration of the outer loop.

This is an improvement over our brute force method.