I was stuck in solving the following interview practice question:
I have to write a function:
int triangle(int[] A);
that given a zero-indexed array A consisting of N integers returns 1 if there exists a triple (P, Q, R) such that 0 < P < Q < R < N.
A[P] + A[Q] > A[R],
A[Q] + A[R] > A[P],
A[R] + A[P] > A[Q].
The function should return 0 if such triple does not exist. Assume that 0 < N < 100,000. Assume that each element of the array is an integer in range [-1,000,000..1,000,000].
For example, given array A such that
A[0]=10, A[1]=2, A[2]=5, A[3]=1, A[4]=8, A[5]=20
the function should return 1, because the triple (0, 2, 4) fulfills all of the required conditions.
For array A such that
A[0]=10, A[1]=50, A[2]=5, A[3]=1
the function should return 0.
If I do a triple loop, this would be very very slow (complexity: O(n^3)). I am thinking maybe to use to store an extra copy of the array and sort it, and use a binary search for a particular number. But I don't know how to break down this problem.
Any ideas?
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.