Solution to Codility lesson4-exercise2 Triangle problem, link to Codility problem and complete solution at the end of the post.

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

13 14 15 16 |
# 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 |

The test_triangle function checks if the triple is *triangular.
*

20 21 |
def test_triangle(P, Q, R): return (P + Q) > R and (Q + R) > P and (R + P) > Q |

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:**

12345678910111213141516171819202122
# 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)*