Codility ‘Triangle’ Solution

Short Problem Definition:

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

Link

Triangle

Complexity:

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

expected worst-case space complexity is O(N)

Execution:

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.

Solution:
def solution(A):
    if len(A) < 3:
        raise Exception("invalid input")

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

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Charly G. Campos

    Hi, in languages in which we have to consider arithmetic overflow i think we should ignore the negatives and as well transform the comparison to A[i] > A[i+2] – A[i+1]. I entered a solution like yours, but for C# and got 93%, i guess being wrong when we pass the half of maxinteger. Regards, Charlio

    • Thanks for pointing that out. I try not to depend on BigInts in Python.

    • João Prudêncio

      In my java solution I need to convert to long values before doing the math calculation.
      I was just thinking if we use dynamic languages like Python it’s much easier to avoid this edge cases. I was thinking about start using one of these languages.
      What is your opinion Martin? And do you recommend just Python? Since I never professionally used this language, I’m afraid I’d loose more time thinking about the syntax instead of thinking in the algorithm.

      • Hmm, interesting question. I solve all these challenges in Python because it is way easier to post. In C++ there are just too many variants, you have to keep in mind too many details and it hides the intention of the algorithm. It has gotten better with c++11, but the language without any additional libraries tends to be a pain. I can’t say if this is the same with Java. It probably is… As for learning Python. Before starting this blog, I had no clue 🙂 I haven’t written a single line of Python, but now I know it pretty well. I would say: Learn the language if you have the choice and the time to do so. Professionally Python is not the language of choice for any serious performance-critical application besides web/django, but especially for stuff like this it makes development faster. My rationale behind Python is that everybody knows it (to a certain degree). Small children can program Raspberry PIs in Python…
        As for the edge cases. Keep them in mind and enjoy the fact that you don’t have to write additional code to handle them 😉

        • João Prudêncio

          Thanks for your great answer Martin.