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

Definitions:

    \[\mathbf{A} = \{x \in \mathbb{Z}\ |-2,147,483,648\leq x \leq 2,147,483,647\land |A| = N\},\mathbf{A}\, is\, a\, multiset.\]

    \[\{N \in \mathbb{N}\ |\ 0 \leq N \leq 100,000\}\]

A triplet

    \[(P, Q , R)\]

is triangular if

    \[0 \leq\,P < Q < R < N\]

 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, 

    \[0 \leq\,P < Q < R < N\]

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 

    \[0 \leq\,P < Q < R < N\]

. But let’s say that,

    \[A[P] = x_0, A[Q] = x_1,A[R] = x_2\]

and that

    \[(P, Q , R)\]

is triangular, this means that

    \[x_0 + x_1 > x_2\land x_1 + x_2 > x_0\land\,x_2 + x_0 > x_1\]

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

    \[(P, Q, R)\]

and

    \[(x_0, x_1, x_2)\]

, for example for 

    \[A[P] = x_0, A[Q] = x_2,A[R] = x_1\]

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

    \[0 \leq\,P < Q < R < N\]

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 is now sorted. We know that

    \[A[k]\leq\,A[k + 1]\leq\,,A[k + 2]\]

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

    \[A[k + 2] < A[k + 1] + A[k]\]

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

    \[A[k + 2]\]

. And to prove that we only need to test if

    \[A[k + 2] < A[k + 1] + A[k]\]

. Assume that 

    \[A[k] > A[k + 1] + A[k + 2]\]

, this means that

    \[A[k] > A[k + 1] \land\,A[k] > A[k + 2]\]

which can not be true. The same goes for

    \[A[k + 1] > A[k] + A[k + 2]\]

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

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

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

/*Comment here*/