# CountTriangles

The trick here is to sort the array first, then you can loop all of the sides of the triangle adding the possible variations.

The result after the third loop is cs – bs – 1, meaning that all the elements between c side and bside ( both exclusive ) are valid results.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// you can write to stdout for debugging purposes, e.g. // console.log('this is a debug message'); function solution(A) { var result = 0, as, bs, cs; A = A.sort( (a, b) => a - b ); for( var as = 0; as < A.length - 2; as++ ){ cs = as+2; for( var bs = as + 1; bs < A.length - 1; bs++ ){ while( cs < A.length && ( A[as] + A[bs] ) > A[cs] ){ cs += 1; } result += cs - bs - 1; } } return result; } |

A zero-indexed 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 a zero-indexed 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.

Assume that:

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].

Complexity:

expected worst-case time complexity is O(N2);

expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.