Triangle at app.codility.com/programmers in JavaScript Explained: Determine whether a triangle can be built from a given set of edges.
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N * log(N))
Lesson 6 at app.codility.com/programmers
The solution and its explanation are given below.
Category of Article : Technology | Computers and Software | Algorithm
By: Chrysanthus Date Published: 2 Jul 2025
Problem
An array A consisting of N integers is given. A 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] = 20
Triplet (0, 2, 4) is triangular.
Write a function:
function solution(A);
that, given an array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.
For example, given array A such that:
A[0] = 10 A[1] = 2 A[2] = 5
A[3] = 1 A[4] = 8 A[5] = 20
the function should return 1, as explained above. Given array A such that:
A[0] = 10 A[1] = 50 A[2] = 5
A[3] = 1
the function should return 0.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..100,000];
- each element of array A is an integer within the range [-2,147,483,648..2,147,483,647].
Note
For any existing 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. Accept that without proof.
Now, assume that you are given three straight sticks and you are asked if they form a triangle.
It can be shown mathematically, that if the sum of the shorter two sides is greater than the third side, then a triangle can be formed. 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.
The given arrays are:
vector<int> A{10, 2, 5, 1, 8, 20};
and
vector<int> B{10, 50, 5, 1};
Strategy
It can be cumbersome to produce the solution function, the brute-force way. So, only the smart approach is explained here. The question is to know if the list has at least one triplet or no triplet at all. The question is not to know how may triplets exists in the list. It is simply to know if there is at least one triplet in the list. The tutorial (lesson) for this problem is, on sorting. It should occur to the candidate that sorting is required in the solution.So, if the list is sorted in at least O(n.log2n) time, the sorted list can be scanned in O(n) time, comparing three sets of consecutive sides, to know if the sum of the shorter two sides is greater than the third side. If the sum of two smaller numbers in the sorted ascending list, is not bigger than the next third number, then it cannot be bigger than the next fourth number. So, only three consecutive numbers have to be compared continuously, along the list.
The expected time complexity is O(n.log2n + n).
The Code
The program is:
<script type='text/javascript'>
"use strict";
function solution(A) {
let N = A.length;
A.sort((a, b) => a - b);
if (N<3)
return 0;
for (let i=0;i<N-2;i++){
if (A[i] + A[i+1] > A[i+2])
return 1;
}
return 0;
}
const A = [10, 2, 5, 1, 8, 20];
let ret = solution(A);
document.write(ret + '<br>');
const B = [10, 50, 5, 1];
let re = solution(B);
document.write(re + '<br>');
</script>
The output is:1
0
If the number of elements in the list is less than 3, then no triangle can be formed. And so the function should return zero.
Note that after the sorting, the for-loop scans from i=0 to i<N-2, since the next two consecutive elements are checked.
Note that the programmer has not defined his/her own sorting function.
At app.codility.com/programmers the scoring and detected time complexity for this smart solution() function is:
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N*log(N))
app.codility.com/programmers must have either ignored the O(n) time of the for-loop or has used a sorting function that is faster than O(n.log2n), to have an overall time of O(n.log2n) instead of O(n.log2n + n).
Thanks for reading.