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

Question

I have found a solution on the net for the codility problem below :

A zero-indexed array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:

    A[P] + A[Q] > A[R],
    A[Q] + A[R] > A[P],
    A[R] + A[P] > A[Q].

For example, consider array A such that:

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20

Triplet (0, 2, 4) is triangular.

Write a function:

 int solution(int A[], int N);

that, given a zero-indexed array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.

The solution is like this :

A.Sort
  for (int i = 0; i < A.length - 2 && A[i] > 0; i++)
  {
         if (A[i] + A[i + 1] > A[i + 2])
            return 1;
  }

But when we sort the array, the original index are no more valid and item in i position can move to j position with j>i or j

The solutin suppose that values that verify assertion (Triangle) is automaticly adjacent in sorted array.

In example array, if we change like this :

A[0] = 10 A[1] = 6 (replace 2) A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20 Here we get 2 new traingle 10 6 5 and 6 5 8. (and 10 5 8)

We sort : 1 5 6 8 10 20 --> Here, original solution (10,5,8) values are not adjacent (no traingle) but instead we have (5,6,8) and (6 8 10). Then algorithm return 1. It seem that if triangle exist then at least values of one triangle will be adjacent but I doesn't find any proof.

Answer 1

Here is my solution in Java. Gives me 100% result on Codility.

class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);

        for (int i = 2; i < A.length; i++) {
            long p = A[i - 2]; 
            long q = A[i - 1]; 
            long r = A[i];

            if (p + q <= r) {
                continue;
            } 
            if (r + p <= q) {
                continue;
            } 
            if (q + r <= p) {
                continue;
            } 
            return 1;
        }

        return 0;
    }
}

Answer 2

Following code works perfectly fine for Python:

def solution(A):
    sorted_a = sorted(A, reverse=True)
    list_len = len(sorted_a) - 2
    for i in range(list_len):
        if sorted_a[i] < sorted_a[i+1] + sorted_a[i+2]:
            return 1
    return 0