Find local minima in an array | Data Structures and Algorithm

Given an array of unique integers whose first two numbers are decreasing and last two numbers are increasing, find a number in the array which is local minima. A number in the array is called local minima if it is smaller than both its left and right numbers.
For example in the array 9,7,2,8,5,6,3,4
2 is a local minima as it is smaller than its left and right number 7 and 8. Similarly 5 is another local minima as it is between 8 and 6, both larger than 5.
You need to find any one of the local minima.
Prove there must be a local minima.

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.

private static int findLocalMinima(int[] arr)
 {
  return findLocalMinima(arr, 0, arr.length);
 }

 private static int findLocalMinima(int[] arr, int start, int end)
 {
  int mid = (start + end) / 2;
  if (mid - 2 < 0 && mid + 1 >= arr.length)
   return -1;
  if (arr[mid - 2] > arr[mid - 1] && arr[mid - 1] < arr[mid])
   return arr[mid - 1];
  if (arr[mid - 1] > arr[mid - 2])
   return findLocalMinima(arr, start, mid);
  else
   return findLocalMinima(arr, mid, end);
 }

Read full article from Find local minima in an array | Data Structures and Algorithm

Largest Rectangular Area in a Histogram | Set 1 | GeeksforGeeks

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit.
We can use Divide and Conquer to solve this in O(nLogn) time. The idea is to find the minimum value in the given array. Once we have index of the minimum value, the max area is maximum of following three values.
a) Maximum area in left side of minimum value (Not including the min value)
b) Maximum area in right side of minimum value (Not including the min value)
c) Number of bars multiplied by minimum value.
The areas in left and right of minimum value bar can be calculated recursively. If we use linear search to find the minimum value, then the worst case time complexity of this algorithm becomes O(n^2). In worst case, we always have (n-1) elements in one side and 0 elements in other side and if the finding minimum takes O(n) time, we get the recurrence similar to worst case of Quick Sort.
How to find the minimum efficiently? Range Minimum Query using Segment Tree can be used for this. We build segment tree of the given histogram heights. Once the segment tree is built, all range minimum queries take O(Logn) time.
O(nLogn) Solution:

int getMaxAreaRec(int *hist, int *st, int n, int l, int r)

{

    // Base cases

    if (l > r)  return INT_MIN;

    if (l == r)  return hist[l];

 

    // Find index of the minimum value in given range

    // This takes O(Logn)time

    int m = RMQ(hist, st, n, l, r);

 

    /* Return maximum of following three possible cases

       a) Maximum area in Left of min value (not including the min)

       a) Maximum area in right of min value (not including the min)

       c) Maximum area including min */

    return max(getMaxAreaRec(hist, st, n, l, m-1),

               getMaxAreaRec(hist, st, n, m+1, r),

               (r-l+1)*(hist[m]) );

}

 

// The main function to find max area

int getMaxArea(int hist[], int n)

{

    // Build segment tree from given array. This takes

    // O(n) time

    int *st = constructST(hist, n);

 

    // Use recursive utility function to find the

    // maximum area

    return getMaxAreaRec(hist, st, n, 0, n-1);

}

Read full article from Largest Rectangular Area in a Histogram | Set 1 | GeeksforGeeks