Problem

An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if it is possible to build a triangle with sides of lengths A[P], A[Q] and A[R]. In other words, triplet (P, Q, R) is triangular if 0 <= P < Q < R < N and: 

        A[P] + A[Q] > A[R],

        A[Q] + A[R] > A[P],

        A[R] + A[P] > A[Q].

For example, consider array A such that: 

      A[0] = 10    A[1] = 2    A[2] = 5

      A[3] = 1     A[4] = 8    A[5] = 12

There are four triangular triplets that can be constructed from elements of this array, namely (0, 2, 4), (0, 2, 5), (0, 4, 5), and (2, 4, 5). 

Write a function:

    function solution($A);

that, given an array A consisting of N integers, returns the number of triangular triplets in this array.

For example, given array A such that: 

  A[0] = 10    A[1] = 2    A[2] = 5

  A[3] = 1     A[4] = 8    A[5] = 12

the function should return 4, as explained above. 

Write an efficient algorithm for the following assumptions:

        N is an integer within the range [0..1,000];

        each element of array A is an integer within the range [1..1,000,000,000]. 

Note:

If the number of elements in the given list is less than 3, then no triangle can be formed.

For any existing single triangle, the sum of any two sides is bigger than the third side. This has been mentioned in the problem (task) with: 

        A[P] + A[Q] > A[R],

        A[Q] + A[R] > A[P],

        A[R] + A[P] > A[Q].

where P, Q and R are different indexes, which are not necessarily consecutive, in the given array. Accept that without proof. 

It can be shown mathematically, that if the sum of the shorter two sides of a supposed triangle, is greater than the third side, then a triangle can be formed. This means that the sum of any two sides of a triangle, is greater than the third side. Accept that without proof. The reader can also consult some other document for these proves, if he/she wishes, or try to prove them himself/herself, by carrying out experiments. As a result of the first rule, there is need for sort ascending, in the solution function.

Strategy

Let x, y and z be the different indexes where  0 <= x < y < z < n 

Have a for-loop that iterates from x=0 to less than x=n-2.

Have a nested for-loop that iterates from y=x+1 to less than x=n-1.

Have an innermost nested for-loop that iterates from z=y+1 to less than n.

There is a normal caterpillar here, though the front legs start at zero based index 2. The back legs start at zero based index 1. The y variable represents the back legs and the z variable represents the front legs. 

The while-condition for the innermost for-loop is:

    (z<n) && (A[x] + A[y] > A[z]) 

This applies the idea of the sum of the shorter two edges, being greater than the third longest edge, for a triangle.

Smart Program

The program is (read the code and comments): 

<?php
    function solution($A) {
        $n = count($A);
        if ($n<3) 
            return 0;
        
        sort($A);    //sort ascending
        
        $counter = 0;
        for ($x=0; $x < $n-2; $x++) {
            for ($y=$x+1; $y<$n-1; $y++) {    //moving back legs forward
                for ($z=$y+1; ($z<$n) && ($A[$x] + $A[$y] > $A[$z]); $z++) {    //moving front legs forward
                    $counter += 1;  
                }
            }
        }

        return $counter;
    }

    $A = [10, 2, 5, 1, 8, 12];
    $ret = solution($A);
    echo $ret . "\n";
?>

The output is 4. At app.codility.com/programmers the scoring and detected time complexity for this solution() function is: 

    Task score : 100% -  Correctness : 100% ; Performance : 100%

    Detected time complexity : O(N²)

The caterpillar works with the y and z for-loops to reduce the time complexity from O(n³) to O(n²) 

Remarks

Two techniques have been used to solve the problem. The techniques are: sorting and the caterpillar method.