• 0

Suppose we are given an array A[1 .. n] with the special property that A[1] ≥ A[2] and
A[n − 1] ≤ A[n]. We say that an element A[x] is a local minimum if it is less than or equal
to both its neighbors, or more formally, if A[x − 1] ≥ A[x] and A[x] ≤ A[x + 1]. For example,
there are ﬁve local minima in the following array:
9 7 7 2 1 3 7 5 4 7 3 3 4 8 6 9
We can obviously ﬁnd a local minimum in O(n) time by scanning through the array. Describe
and analyze an algorithm that ﬁnds a local minimum in O(log n) time.

Comment hidden because of low score. Click to expand.
3
of 3 vote

The question just asks for one local minimum.
mid=(start+end)/2;
1. if(A[mid-1]>=A[mid] && A[mid+1]>=A[mid]) then A[mid] is a local minimum.
2. else if(A[mid-1]<=A[mid] && A[mid]<=A[mid+1]) end=mid, do recursive search.
3. else if(A[mid-1]>=A[mid] && A[mid]>=A[mid+1]) start=mid, do recursive search
it is O(logn)

Comment hidden because of low score. Click to expand.
0

wont work.
e.g. 1,2,3,4,10,8,11
mid is 4 and as per your logic the search will reduce to 1st half. but the local minimum is 8.

Comment hidden because of low score. Click to expand.
0

Dont know about the above logic , but Tulleys array is wrong. Read problem : a1> a2.

Comment hidden because of low score. Click to expand.
0

You are right, Tulley gave a wrong example. Let's change the example to 2,1,3,4,10,8,11. Based on the logic, mid is 4, 3<4<10, then search the local minimum from the first half, 2,1,3,4. It will find 1 as the local minimum.
In this example there are 2 local minimum 1 and 8. The logic finds 1.

Comment hidden because of low score. Click to expand.
0

apparently your approach is wrong. What if first half of the array is sorted in decreasing order, for example(in above example) 3,2,1,0,-1,8,11. Your code moves to left half [3,2,1,0] where there is no local minima. But the right half contains 1 minima [0,-1,8].

My basic understanding is that NO algorithm exists that can give O(log n) solution for this problem in O(log n). As the array is not sorted, no ordering of elements can be deduced from one comparision, unlike binary search in sorted array.

Comment hidden because of low score. Click to expand.
0

LOL, in your example, 1>0>-1, it will move to the right half, not left half.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This solution is correct and will work for all test cases.

Comment hidden because of low score. Click to expand.
0

the most important thing there is if we can think the first element is the answer in the problem, like the sequence is 0 1, and 0 <= 1, but there is no element before 0, could we think 0 is the answer. If yes, then the algo given by the author is right, else it's wrong.

Comment hidden because of low score. Click to expand.
0

What if 6 3 5 4 8.

This program does not count if it is the local maximum. It do not fall
under any of the conditions.

Comment hidden because of low score. Click to expand.
0
of 0 vote

In this array: {9 7 7 2 1 3 7 5 4 7 3 3 4 8 6 9} I can count six local minimals.

value => position
7 => 1
1 => 4
4 => 8
3 => 10
3 => 11
6 => 14

Am I right ?

Comment hidden because of low score. Click to expand.
0

yes ... you are right. The minimum of array will be one of the local minima and we have to return any of them. Can we find Min of an array in log(n) time??

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

we can do it O(logn) time

Comment hidden because of low score. Click to expand.
0

Do you mind to share?

Comment hidden because of low score. Click to expand.
0

Seems WgpShashank DOES NOT know the answer himself :D

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void findLocalMinima (int* pGivenArray, int* localMinArray, int* minimaCount, int start, int end)
{
int mid;
if (end-start >= 2)
{
mid = (end+start)/2;
if ((pGivenArray [mid-1] >= pGivenArray [mid]) &&
(pGivenArray [mid] <= pGivenArray [mid+1]))
{
localMinArray [++(*minimaCount)] = pGivenArray [mid];
}
findLocalMinima (pGivenArray, localMinArray, minimaCount, start, mid);
findLocalMinima (pGivenArray, localMinArray, minimaCount, mid, end);
}
}

int main ()
{
int givenArray [] = {9,1,11,12,16,13,14,15,16,17,18,19,20,25,2,22};
int minimaArray [10] = {0};
int minimaCount = -1, i;
findLocalMinima (givenArray,minimaArray,&minimaCount,0,15);
while(minimaCount >= 0)
{
printf ("[%d]", minimaArray[minimaCount--]);
}
printf ("\n");
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

This recursion solution is doing better than scanning the array. You will still need to check every elements in the array. Still O(n), not O(lgn)

Maybe I'm stupid, but I don't think there is any possible way you can find local min in O(lgn) without an auxilary data structure and a preprocessing on the input array.

Comment hidden because of low score. Click to expand.
0

@Anonymous: u r correct. Its not O(logn). i also realized the same after writing this solution.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I did not understand the question. They say that A[1]>=A[2] and A[n-1]<=A[n]. In this array first condition is satisfied but not the second one.
9 7 7 2 1 3 7 5 4 7 3 3 4 8 6 9
When they say A[n-1]<=A[n] shouldn't it be in increasing order except the first element?

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this question is either wrong, or having missing conditions. the following array does not have a local minimum. yet, it satisfies the conditions given in the question:

9, 10, 11, 12, 13, 12, 11, 9

Comment hidden because of low score. Click to expand.
0

what happened to A[n-1] <= A[n]?

Comment hidden because of low score. Click to expand.
0
of 0 vote

findLocalMin(start, end, array)
if start > end return None
mid = array[(start+end)/2]; st = array[start]; en = array[end];
if mid > both st and en: findLocalMin(start, mid-1, array) or findLocalMin(mid+1, end, array) # we have at least two local minima
if start > mid > end findLocalMin(mid+1, end, array) #
if end > mind > start findLocalMin(start,mid-1, array)
if mid < both:
if mid < array[mid+1] and array[mid-1] return mid
if array[mid-1] > mid > array[mid+1] findLocalMin(mid+1,end,array)
if array[mid+1] > mid > array[mid-1] findLocalMin(start,mid-1,array)

Comment hidden because of low score. Click to expand.
0

the above logic was kinda buggy, but the idea is the same. Here is working Python code for the O(lgn) solution:

``````def findLocalMin(start, end, array):
if start > end:
return None

m = (start+end) / 2
mid = array[m]
st = array[start]
en = array[end]

print "array:" , array[start:end + 1] # to trace what's happening

after = array[m+1]
before = array[m-1]

if mid <= before and mid <= after: # found local minimum
return mid

if before >= mid and mid >= after: # V-shape on right
return findLocalMin(m, end, array)

if after >= mid and mid >= before: # V-shape on left
return findLocalMin(start,m,array)

if before <= mid and after <= mid: # at least two local minima, choose one
return findLocalMin(m,end,array)

if __name__ == "__main__":
#a = [9,7,7,2,1,2,7,5,4,7,3,4,4,8,6,9]
a = [2,1,3,4,10,8,11]
print findLocalMin(0, len(a) - 1, a)``````

Comment hidden because of low score. Click to expand.
0

Seems ur logic is wrong, indeed. Check out this example:

3, -5, 1, 0, -3, -2, -1

Your search moves to right as before >= mid and mid >= after. But no minima is there. But, one in right half exist there [3,-5,1]

Comment hidden because of low score. Click to expand.
0

oh... i meant left half with respect to middle element 0.

Comment hidden because of low score. Click to expand.
0

sorry, i did mistake. your approach seems correct to me now. however, i believe we can relax the conditions in your code as below:

``````if mid >= after
return findLocalMin(m+1, end, array)
if mid >= before
return findLocalMin(start,m-1,array)``````

Pls verify if that is correct. Thanks.

Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey77119" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{

public int getOneLocalMinimum(int lowIndex, int highIndex) {
if (lowIndex > highIndex) {
return -1;
}
if (lowIndex == highIndex) {
return lowIndex;
}
if (lowIndex + 1 == highIndex) {
if (elements[lowIndex] < elements[highIndex]) {
return lowIndex;
}
return highIndex;
}
int midIndex = (lowIndex + highIndex) / 2;
if ((elements[midIndex] <= elements[midIndex - 1])
&& (elements[midIndex] <= elements[midIndex + 1])) {
return midIndex;
}
if (elements[midIndex] >= elements[midIndex + 1]) {
return getOneLocalMinimum(midIndex, highIndex);
} else {
return getOneLocalMinimum(lowIndex, midIndex);
}
}
public static void main (String[] args)
{
int arr[] = { 1, 0, -1, 0, 1, -2, 0 };
System.out.println(new LocalMinimum(arr).getOneLocalMinimum(0,
arr.length - 1));
}
}

</pre>

Comment hidden because of low score. Click to expand.
0
of 0 vote

easy question if you know math well~
Similar to the intermediate value theorem in real analysis.
Good question~

Comment hidden because of low score. Click to expand.
0

What is your smart solution for such easy problem, dude?

If you dare to challenge, post your answer (NOT code, the idea only). Otherwise, no need to spend your time typing here.

Comment hidden because of low score. Click to expand.
0

it is similar to binary search, you just need to modify it a little bit.

Comment hidden because of low score. Click to expand.
0
of 0 vote

a[1]>=a[2] && a[n-1]<=a[n];
// it means there is a local minima between a[2] to a[n-1]
if(a[n/2]<=a[n/2+1])
//it means there is a local minima between a[n/2] ans a[2];
else there is a local minima between a[n/2+1] ans a[n]

now recursively solve it O(lg n) solution;

Comment hidden because of low score. Click to expand.
0
of 0 vote

To get results on O(log n), the list must be sorted, else no matter what we write the worst case scenario will be O(n).

Comment hidden because of low score. Click to expand.
0
of 0 vote

mid = sizeof(A)/2
recursive call

if(A[mid]>A[1]){
//becasue the value turn up, there will be a local min
find(A,0,mid) }
else{//
find(A[],mid,sizeof(A)-1)
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int find(int[] arr, int start, int end){

int mid = (start + end)/2;
if(mid==0 || mid == arr.length-1) return -1;

if((arr[mid] <= arr[mid-1] && arr[mid] <= arr[mid + 1]) ||
(arr[mid] <= arr[mid-1] && arr[mid] <= arr[mid + 1]) )
return arr[mid];
//ascending
else if(arr[mid] > arr[mid]-1 && arr[mid] < arr[mid+1]){
return find(arr, start, mid);
}

//descending
else{
return find(arr, mid, end);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

The logic for my code is as follows: Given the condition that A[0] >= A[1] and A[n-1] <= A[1], it is guaranteed that a minima exists. This is because for a minima to not exist, the sequence has to be strictly decreasing but the special property negates it. So a transition from strictly decreasing to increasing/remain same has to happen somewhere. Even if there are multiple minimas, each minima is a transition. The following code just looks for a transition. This can be done in O(log n) time.
Python Code:

``````#!/usr/bin/env python

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

low = 0
high = len(A) - 1
found = False
trans = 0

trans = (high + low)/2
if A[trans - 1] >= A[trans]:
low = trans
if A[trans] <= A[trans+1]:
high = trans
if high == low:
found = True

print 'Local minima', A[trans-1:trans+2]``````

Comment hidden because of low score. Click to expand.
0

Splay trees can be helpful here. Though it does not give guaranteed insertion of O(logn) but the average case is O(logn). Also, if the array definitely has local minimun, then splay tree's insertion time will be definitely less than O(logn). A node of splay tree will contain a hashmap of value and it's count. Thus, for the local minimun, the count of the root of node will become 3 and that will be in O(logn) time.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void findMin(int i,int j,int arr[])
{
if(a[i]<a[j])
min=a[i];
else if(a[i+1]<a[j])
min=a[i+1];
if(j-i >=2)
{
findMin(i,(i+j)/2,arr);
findMin(((i+j)/2)+1,j,arr);
}

}``````

I donno whether this runs in O(log n)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.