Thursday, February 27, 2014

Find Local Minimum in an unsorted array with unique elements

Problem: Given an array ‘a’ of N distinct integers, design an O(log N) algorithm to find a local minimum: an index i such that a[i-1] > a[i] < a[i+1].

Examples:
a = [1,2,3,4,5] (increasing, increasing) a[0] is an LM
a = [5,4,3,2,1] (decreasing, decreasing) a[n] is an LM
a = [1,2,2,2,1] (increasing, decreasing) a[0] and a[n] are LMs

Solution:

Brute force 
Go through each element 3 tuples, and compare them.
Time complexity - O(n)

Solution 2
Can we do better? The answer is yes, we can do this in O(log n). Lets see how.
mid=(start+end)/2; 
1. If there is just one array element, it's a local minimum.
2. If there are two array elements, check each. One must be a local minimum.
3. Otherwise, look at the middle element of the array. 
   If it's a local minimum, return it. 
   Otherwise, at least one adjacent value must be smaller than this one. 
   Recurse in the half of the array containing that smaller element 
   (but not the middle).

Here is the code in java:
public class LocalMinimum {

 public static int findLocalMinimum(int[] elements, 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 findLocalMinimum(elements, midIndex, highIndex);
  } else {
   return findLocalMinimum(elements, lowIndex, midIndex);
  }
 }
 
 public static void main(String[] args){
  int Arr[] = {8,5,4,3,1,2,6,9};
  int index = findLocalMinimum(Arr, 0, Arr.length-1);
  System.out.println("local mimimum is "+Arr[index]);
 }

}

Time complexity
T(1) ≤ 1
T(2) ≤ 1
T(n) ≤ T(n / 2) + 1
Using the Master Theorem, you can show that this algorithm runs in time O(log n), as required.

[Edit] - Note
  1. We are not enumerating all the local minima in the array, but a single LM, which can be done in O(log n) time.
    The number of local minima can be n/2; you can't enumerate them all in O(log n) time.
  2. It also doesn't guarantee whether we will get global minima or not. Consider the array
    {8,5,4,3,1,2,6,9}, the output will be 1, as it is only LM here, not because it is a global minima.
  3. The method doesn't guarantee any particular local minima. Consider the array : {8,5,4,3,6,4,5,1,2,6,4,5,9}. The LM outputted by the code will be 3, which is one of the LMs in the array. The LMs we had in array were 3,4,1,4. But the code returned 3, which is one of the LMs. 

Reference
http://stackoverflow.com/questions/12238241/find-local-minima-in-an-array

Thanks

2 comments:

  1. The pseudo / java code find only global minima and that too when no other local minima exist. I don't think this problem can be solved in less than O(n)

    ReplyDelete
  2. Hi Himadri, thanks for the comment. But I think the code is intended to give us local minima, and as we are apply binary search logic, it is possible in O(log n). I have added edit note in the blog post as well :


    We are not enumerating all the local minima in the array, but a single LM, which can be done in O(log n) time. The number of local minima can be n/2; you can't enumerate them all in O(log n) time.

    It also doesn't guarantee whether we will get global minima or not. Consider the array {8,5,4,3,1,2,6,9}, the output will be 1, as it is only LM here, not because it is a global minima.

    The method doesn't guarantee any particular local minima. Consider the array : {8,5,4,3,6,4,5,1,2,6,4,5,9}. The LM outputted by the code will be 3, which is one of the LMs in the array. The LMs we had in array were 3,4,1,4. But the code returned 3, which is one of the LMs.

    Please let me know if this makes sense?

    ReplyDelete