CareerCup

The question could definitely be worded more precisely, anyways here is a very nice explanation.
First we need to understand that if in an array of unique integers first two numbers are decreasing and last two numbers are increasing there ought to be a local minima. Why so? We can prove it in two ways. First we will do it 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.

We can prove this in some other way also. Suppose we represent the array as a 2-D graph where the index of the numbers in the array represents the x-coordinate. and the number represents the y-coordinate. Now for the first two numbers, derivative will be negative, and for last two numbers derivative will be positive. So at some point the derivative line will have to cross the x axis. As the array contains only unique elements there cannot be a derivative point on the x axis. Because that will mean that two consecutive index having same number. So for any intersection of x axis by the derivative line will be a local minima.

We will solve this problem in O(log n) time by divide and conquer method. We will first check the mid index of the array. If it is smaller than its left and right, then it is the answer. If it is bigger than the left number then from start to left we have a subproblem, and as we proved already that starting with decreasing and ending with increasing sequence array will have to have a local minima, we can safely go to the left subarray. Otherwise if mid is bigger than its right, then we go to the right subarray. This way we guarantee a O(log n) algorithm to find any of the local minima present in the array.
(copied from dsalgo dot com (find-local-minima))

The question could be worded better, but the idea I think is that the numbers exclusively decrease until a certain point where they exclusively increase. There is only one such point in the array. We need to find that point, and we need to do it in better than O(n) time.

So lets use binary search. Cut the array into two parts. For the first half, check the last two elements. Is it still decreasing? if so, forget that half. recursively search in the second half.
When you find the increasing part, keep that half and resursively search it.

Eventually you should find the point where it goes from decreasing to increasing, and this will take logn time.

The difficult is that the questions states greater than/equal, and not just greater than. So its possible to have 9, 8, 5, 4, 3, 3, 3, 3, 3 as an input value, and the algorithm proposed above will end without finding the spot where it starts increasing. however, the spot that you found should still be the center point of a valid return triplet.

*O(log n) time complexity*

A = [9, 8, 5, 4, 3, 2, 1, 7]

def findTriplet():
    first = 0
    last = len(A) - 1
    while (True):
        mid = int((first + last) / 2)
        if (A[mid] <= A[mid - 1]) and  (A[mid] <= A[mid + 1]):
            print(str(A[mid-1]) + " " + str(A[mid]) + " " + str(A[mid+1]))
            return
        if A[mid] > A[mid + 1]:
            first = mid + 1
        if A[mid] > A[mid - 1]:
            last = mid - 1
        
findTriplet()

public void printTriplet(int[] array) {
	if(array == null  || array.length == 0) {
		System.err.println("Empty array");
		return ;
	}
	int index = getTriplet(array, 0, array.length -1 );
	if(index == -1) {
		System.out.println("No such triplet found");
		return;
	}
	System.out.println("The required triplet is " + 
					array[index-1] + ", " +
					array[index] + ", " +
					array[index + 1]);
}

public int getTriplet(int[] array, int lower, int upper) {
	if(lower >= upper) return -1;
	int middle = lower + (upper - lower)/2;
	if(array[middle - 1] >= array[middle] && array[middle + 1] >= array[middle])
		return middle;
	int index = getTriplet(array, lower, middle);
	if(index != -1) return index;
	index = getTriplet(array, middle + 1, upper);
	if(index != -1) return index;
	return -1;
}

agree with GeekTycoon.. idea is gud but it does hav O(n) time cplxty since it scans both side

public static void findTriplet(int lower, int array[]){
while(lower<array.length-2){
if(array[lower]>=array[lower+1]&&array[lower+1]<=array[lower+2]){
System.out.println("Triplet is "+array[lower]+" "+array[lower+1]+" "+array[lower+2]);
return;
}
lower+=2;
}
findTriplet(1,array);
}

public static void main(String[] args){
int[]array= {9, 8, 6, 7};
findTriplet(0,array);
}
}

public class findTriplet {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr[]={9, 8, 5, 4, 3, 2, 1, 7};
	    int n=arr.length;
	    	  int i=findTriplet(arr,0,n-1);
	    	  if(i==-1)
	    	  {
	    		  System.out.println("No triplet exists");
	    	  }
	    	  else 
	    	  {
	    	 System.out.println("Triplet exists and it is \n");
	    	 System.out.println(arr[i-1]+" "+arr[i]+" "+arr[i+1]);
	    	  }
	}

	public static int findTriplet(int arr[], int low, int high) {
		while (low <= high) {
			int mid = (low + high) / 2;
			if(mid-1<0||mid+1>high)
			{
				break;
			}
			if (arr[mid-1]>=arr[mid]&&arr[mid]<=arr[mid+1]) {
				return mid;
			} else if (arr[mid-1] < arr[mid]) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}
		return -1;
	}
}

Binary search - just need to decide to which side to recurse, based on values of the neighbors. Returns the index of the "bottom" or -1 if it doesn't exist.

static int findbottom(int[] arr, int s, int e)
        {
            if (s > e) return -1;
            if (s == e) return s;

            int m = (s + e) / 2;
            if (m == s || m == e) return -1;

            int mm1 = arr[m - 1];
            int mp1 = arr[m + 1];
            if (mm1 >= arr[m] && mp1 >= arr[m]) return m;
            if (mm1 > mp1) return findbottom(arr, m, e);
            return findbottom(arr, s, m);
        }

import java.util.Arrays;


public class LocalMinimumInArray {
	public static int getLocalMinimum(int [] arr){
		int n = arr.length;
		if(n<3 || arr[0] < arr[1] || arr[n-1] < arr[n-2] ) throw new IllegalArgumentException("...");
		int p = 1;
		int q = n-2;
		// check p and q
		if(arr[p] <= arr[p+1]) return p;
		if(arr[q] <= arr[q-1]) return q;


		while(p < q){
			int m = (p+q)/2;
			if(arr[m-1] < arr[m]){
				q = m-1;
				if(arr[q] <= arr[q-1]) return q;
				continue;
			} 
			if(arr[m] > arr[m+1]){
				p = m+1;
				if(arr[p] <= arr[p+1]) return p;
				continue;
			} 
			return m;
		}

		return p;

	}


	public static void main(String[] args) {
		int [] arr = { 8,8,5,4,5,5,6,8 };
		test(arr);
		
		
	}


	private static void test(int[] arr) {
		int idx = getLocalMinimum(arr);
		System.out.println("Local minimum in " + Arrays.toString(arr)+ " is at index "  + idx+": "+ arr[idx]);
	}	

}

The triplet can be found out by using binary search in the following way. You can test the below code:

#include <stdio.h>
#include <stdlib.h>

int findTriplet(int arr[],int low,int high)
{
    if(low==high)
        return 0;
    else if(low==high+1)
        return 0;
    else
    {
        int mid=low+(high-low)/2;
        if(arr[mid-1]>=arr[mid]&&arr[mid]<=arr[mid+1])
                return mid;
        findTriplet(arr,low,mid-1);
        findTriplet(arr,mid+1,high);
    }
}
int main()
{
    int arr[]={4,3,4};
    int n=sizeof(arr)/sizeof(arr[0]);
    int i=findTriplet(arr,0,n-1);
    if(i==0)
        printf("No triplet exists");
    else
    {
        printf("Triplet exists and it is \n");
        printf("%d %d %d",arr[i-1],arr[i],arr[i+1]);
    }
}