Codility 'Triangle' Solution

Martin Kysel · August 7, 2014

Short Problem Definition:

Determine whether a triangle can be built from a given set of edges.



expected worst-case time complexity is O(N\*log(N))

expected worst-case space complexity is O(N)


By sorting the array, we have guaranteed that P+R > Q and Q+R > P (because R is always the biggest). Now what remains, is the proof that P+Q > R, that can be found out by traversing the array. The chance to find such a combination is with three adjacent values as they provide the highest P and Q.


def solution(A):
    if 3 > len(A):
        return 0


    for i in xrange(len(A)-2):
        if A[i] + A[i+1] > A[i+2]:
            return 1

    return 0

Twitter, Facebook