Definitions:

   

   

A triplet

   

is triangular if

   

 and:

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

Just like in the Max Product of Three problem, 

   

only means that you can’t use the same element of A.

Problem:
Define a function solution with input A, such that solution returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.

• Expected worst-case time complexity is O(N*log(N));
• 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. 

Analysis:

To solve this problem we have to sort the array first, in Python this can be done using A.sort(), the sort method in Python has a time complexity of O(N*log(N)).
With the array sorted now we can solve the problem with O(N)  time complexity, we just have to iterate through A, check if A[k], A[k + 1], A[k + 2] is triangular,  if it is we return 1 and if not we go to next k, until we finish the array.

The test_triangle function checks if the triple is triangular.

So why does this work? First when we sorted the array we modified most of the elements’ indexes. And this may seem to broke this statement 

   

. But let’s say that,

   

and that

   

is triangular, this means that

   

but you can try yourself and see that this holds for every combination of

   

and

   

, for example for 

   

, so it’s only a matter of rearranging the elements to make the statement 

   

true. The second thing to prove is, if A[k], A[k + 1], A[k + 2] is not triangular, why didn’t we tested for A[k], A[k + 2], A[k + 3] and so forth. Well this can be answered by the fact that A is now sorted. We know that

   

, so in our function test_triangle what we are really testing is if

   

, if it’s not there is no need to test the next elements since every other element is greater or equal than

   

. And to prove that we only need to test if

   

. Assume that 

   

, this means that

   

which can not be true. The same goes for

   

.
The total time complexity is O(N) + O(N*log(N)) = O(N*log(N)).
For the space complexity we have O(1).

Complete Solution:

Triangle

Python

# Name: Triangle # Link: https://codility.com/demo/take-sample-test/triangle/ def solution(A): N = len(A) A.sort() # If A length is lesser than 3 A can't be triangular if N < 3: return 0 # Since Array is sorted, only have to look for each element once for k in xrange(N - 1): if test_triangle(A[k], A[k + 1], A[k + 2]): return 1 return 0 def test_triangle(P, Q, R): return (P + Q) > R and (Q + R) > P and (R + P) > Q

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

# Name: Triangle # Link: https://codility.com/demo/take-sample-test/triangle/     def solution(A):     N = len(A)     A.sort()          # If A length is lesser than 3 A can't be triangular     if N < 3:         return 0       # Since Array is sorted, only have to look for each element once     for k in xrange(N - 1):         if test_triangle(A[k], A[k + 1], A[k + 2]):             return 1           return 0   def test_triangle(P, Q, R):     return (P + Q) > R and (Q + R) > P and (R + P) > Q

Time Complexity O(N*log(N))
Space Complexity O(1)

Link to GitHub solution here .
Link to Codility problem here .