Find triplets in better than linear time such that A[n-1] >= A[n] <= A[n+1]

Question

A sequence of numbers was given in an interview such that A[0] >= A[1] and A[N-1] >= A[N-2]. I was asked to find at-least one triplet such that A[n-1] >= A[n] <= A[n+1].

I tried to solve in iterations. Interviewer expected better than linear time solution. How should I approach this question?

Example: 9 8 5 4 3 2 6 7

Answer: 3 2 6

Answer 1

We can solve this in O(logn) time using divide & conquer aka. binary search. Better than linear time. So we need to find a triplet such that A[n-1] >= A[n] <= A[n+1].

First find the mid of the given array. If mid is smaller than its left and greater than its right. then return, thats your answer. Incidentally this would be a basecase in your recursion. Also if len(arr) < 3 then too return. another basecase.

Now comes the recursion scenarios. When to recurse, we would need to inspect further right. For that, If mid is greater than the element on its left then consider start to left of the array as a subproblem and recurse with this new array. i.e. in tangible terms at this point we would have ...26... with index n being 6. So we move left to see if the element to the left of 2 completes the triplet.

Otherwise if mid is greater than element on its right subarray then consider mid+1 to right of the array as a subproblem and recurse.

---

More Theory: The above should be sufficient to understand the problem but read on. The problem essentially boils down to finding local minima in a given set of elements. A number in the array is called local minima if it is smaller than both its left and right numbers which precisely boils down to A[n-1] >= A[n] <= A[n+1].

A given array such that its first 2 elements are decreasing and last 2 elements are increasing HAS to have a local minima. Why is that? Lets prove this by negation. If first two numbers are decreasing, and there is no local minima, that means 3rd number is less than 2nd number. otherwise 2nd number would have been local minima. Following the same logic 4th number will have to be less than 3rd number and so on and so forth. So the numbers in the array will have to be in decreasing order. Which violates the constraint of last two numbers being in increasing order. This proves by negation that there need to be a local minima.

The above theory suggests a O(n) linear approach but we definitely can do better. But the theory definitely gives us a different perspective about the problem.

---

Code: Here's python code (fyi - was typed in stackoverflow text editor freehand, it might misbheave).

def local_minima(arr, start, end):
    mid = (start+end)/2

    if mid-2 < 0 and mid+1 >= len(arr):
        return -1;

    if arr[mid-2] > arr[mid-1] and arr[mid-1] < arr[mid]: #found it!
        return mid-1;

    if arr[mid-1] > arr[mid-2]:
        return local_minima(arr, start, mid);
    else:
        return local_minima(arr, mid, end);

Note that I just return the index of the n. To print out the triple just do -1 and +1 to the returned index. source