Determining possible triangle from lengths of line segments This Codility challenge is to take an array of integers representing lengths of line segments, and determine whether or not it is possible to choose three distinct segments to form a triangle.  (The sum of the lengths of any two sides must exceed the length of the remaining side.)  Assume that A contains at most one million ints.

Complexity requirements:


Expected worst-case time complexity is O(n log(n));
Expected worst-case space complexity is O(n), not counting the input array A itself.


This is my solution:

import java.util.Arrays;
class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 6
        int n = A.length;

        if (n&gt;1000000000) return -1;

        Arrays.sort(A);
        int p=0;
        int q=p+1;
        int r=q+1;
        for (;r&lt;n;p++,q++,r++){
            if(A[p]+A[q]&gt;A[r] &amp;&amp; A[q]+A[r]&gt;A[p] &amp;&amp;  A[r]+A[p]&gt;A[q])
               return 1;
        }
        return 0;
    }
}


I don't how to achieve 100% correctness. I get only 93%.
As has been pointed out, you must do several things to ensure you get the maximum marks.


Ensure that negative numbers are checked for.
Handle the MAX_INT overflow issue which could arise.


  You know 4 + 5 &gt; 7 is same as 5 &gt; (7 - 4). Yes I know you are grinning ;)


This suggested solution is correct for this.


These two individual points should allow you to achieve the maximum score. Now I would just like to quickly go over some theory behind why this solution works. 

Time complexities

It seems people keep asking you to address the "consecutive elements". You have already done this through the use of Arrays.sort(). This Java sort algorithm is referred to as a "tuned Quicksort" ( See http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#sort(int[]) ). 


  The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.
  Quicksort is well known for its O( n log n ) time complexity (excluding extreme cases).


After this you do a single iteration over the array, which is considered O(n). When we add the two time complexities together we are given O( 2n log n) where constants are considered insignificant for Big-O notation. So to clarify this simplifies down to O(n log n) which was the upper bound of the problem.

How sorting solves non-consecutive elements

Once the array is sorted it is true that only consecutive triples need to be considered. 

Consider the following array: {1,2,6,6,8}

Whilst it may be true that (1, 6, 6) is triangular, and is non-consecutive. It can also be proven that if that value is triangular then any number which lies between the initial 1, and 6 will also be triangular. 

From this we can see that in the sort array, for each non-consecutive triangular triples which exists there also exists an consecutive triple.

Simplification from sorting

The sort operation allows you to simplify you checks later, and decrease execution time. When checking for negative number, you only need check the lowest number in the triple, as if this is &gt;= 0 it is given the follow values must be &gt;= that initial value.

This mean you only need check one value for negativity, not three.

This can be extended further into the actual triangular checks. If it is true that the smallest two numbers in the triple are larger than the largest number when summed, then all three statements are true.


  1) A[P] + A[Q] > A[R]
  
  2) A[Q] + A[R] > A[P]
  
  3) A[R] + A[P] > A[Q]


Remembering the algorithm change to this, so these would be evaluated as

A[P] &gt; (A[R] - A[Q])


Because we can guarantee that A[P] &lt; A[Q] &lt; A[R] due to A being sorted, we only need perform the one check above.