Codility – Triangle

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.

# 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

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

# 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

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 $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 A 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).