How to know that a triangle triple exists in our array?

Here is an implementation of the algorithm proposed by Vlad. The question now requires to avoid overflows, therefore the casts to long long.

#include <algorithm>
#include <vector>

int solution(vector<int>& A) {

    if (A.size() < 3u) return 0;

    sort(A.begin(), A.end());

    for (size_t i = 2; i < A.size(); i++) {
        const long long sum = (long long) A[i - 2] + (long long) A[i - 1];
        if (sum > A[i]) return 1;
    }

    return 0;

}

First of all, you can sort your sequence. For the sorted sequence it's enough to check that A[i] + A[j] > A[k] for i < j < k, because A[i] + A[k] > A[k] > A[j] etc., so the other 2 inequalities are automatically true.

(From now on, i < j < k.)

Next, it's enough to check that A[i] + A[j] > A[j+1], because other A[k] are even bigger (so if the inequality holds for some k, it holds for k = j + 1 as well).

Next, it's enough to check that A[j-1] + A[j] > A[j+1], because other A[i] are even smaller (so if inequality holds for some i, it holds for i = j - 1 as well).

So, you have just a linear check: you need to check whether for at least one j A[j-1] + A[j] > A[j+1] holds true.

Altogether O(N log N) {sorting} + O(N) {check} = O(N log N).

---

Addressing the comment about negative numbers: indeed, this is what I didn't consider in the original solution. Considering the negative numbers doesn't change the solution much, since no negative number can be a part of triangle triple. Indeed, if A[i], A[j] and A[k] form a triangle triple, then A[i] + A[j] > A[k], A[i] + A[k] > A[j], which implies 2 * A[i] + A[j] + A[k] > A[k] + A[j], hence 2 * A[i] > 0, so A[i] > 0 and by symmetry A[j] > 0, A[k] > 0.

This means that we can safely remove negative numbers and zeroes from the sequence, which is done in O(log n) after sorting.

In Java:

public int triangle2(int[] A) {

    if (null == A)
        return 0;
    if (A.length < 3)
        return 0;

    Arrays.sort(A);

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

    return 0;

}