Here's the task:
https://app.codility.com/programmers/lessons/6sorting/triangle/
And here's a simple O(n log n) solution for it (what the site expects):
1 2 3 4 5 6 7 8 9 10 11

int solution(std::vector<int>& A) {
if (A.size() <= 2)
return 0;
std::sort(A.begin(), A.end());
for (size_t i = 0; i < A.size()  2; ++i)
if ((long long)A[i] + A[i + 1] > A[i + 2])
return 1;
return 0;
}
 
What I'm a little curious about is to know if there's possibility to create an O(n) solution with a notaverybad space complexity for the task.
Following my experience with previous tasks I tried to find a relationship/pattern between the results for a few tests on this current task. For example, I tried (using pen and paper) to see if the following items can guide me to a way to find the relationship/pattern for a better solution:
 max, min or average element (of the array)
 using bit manipulation like XOR
 number of elements of the array
 or using a side array
I dedicated about five hours to it but up to now I haven't found such a pattern or particular observation using the items/ideas above except for the last one, like:
 using a
std::vector<size_t>
of size
INT_MAX
and add each positive element in the index equal to it into the vector and that way to get it sorted.
 using a 2D
std::vector
of N*N (N: size of array) and insert all various sequences of the elements into it and finally search on it.
Apart from being sure if the above two ways using a side array can lead to a better solution in terms of time complexity or not, they're obviously quite inefficient in terms of space complexity.
What I need?
What I need is merely a hint! (not code)
I like myself to find a better solution (if any). So if possible just give me some hint or indirect idea for that purpose, please. Then I will try to create the code and then you can post your own ones and together compare them. This way I can take advantages of your experience well.
Thanks in advance.