Find the local minima in array

Table of Contents

Problem
Solution
- Naive approach
- Efficient approach

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this post, we will see how to find the local minima in the array.

Problem

An element is local minima if it is less than its neighbors.

int [] arr = {10, 5, 3, 6, 13, 16, 7};
Output: 2

int []arr = {11,12,13,14};
Output: 11

int []arr = {10};
Output: 10

int []arr = {8,6};
Output: 6

Solution

Naive approach

You can use for loop and compare neighbor elements, you will get the local minima.
Worst case time complexity will be o(n).

Efficient approach

You can use binary search to find local minima.

Worst case time complexity will be o(log n).
Here is simple algorithm

Find the mid element
If mid element is less than both the neighbor then return it.
If mid element is greater than its left neighbor, then go left
else go right.


package org.arpit.java2blog;
public class LocalMinima {

    public int findLocalMinima(int [] arr, int start, int end){

        /*find the mid index*/
        int mid = start + (end-start)/2;
        int size = arr.length;

        /*check the local minima 
         *first check if left and right neighbor exists */
        if((mid==0 || arr[mid-1]>arr[mid]) &&
                (mid==size-1 || arr[mid+1]>arr[mid]))
            return arr[mid];
        /* check if left neighbor is less than mid element, if yes go left */
        else if(mid>0 && arr[mid]>arr[mid-1]){
            return findLocalMinima(arr, start, mid);
        }
        else { 
            /*check if right neighbor is greater than mid element, if yes go right */
            return findLocalMinima(arr, mid+1, end);
        }
    }

    public static void main(String[] args) {
        LocalMinima l = new LocalMinima();
        int [] arr = {10, 5, 3, 6, 13, 16, 7};
        System.out.println("Local Minima is: " + l.findLocalMinima(arr,0,arr.length));
    }
}

package org.arpit.java2blog;

public class LocalMinima {

public int findLocalMinima(int [] arr, int start, int end){

/*find the mid index*/

int mid = start + (end-start)/2;

int size = arr.length;

/*check the local minima

*first check if left and right neighbor exists */

if((mid==0 || arr[mid-1]>arr[mid]) &&

(mid==size-1 || arr[mid+1]>arr[mid]))

return arr[mid];

/* check if left neighbor is less than mid element, if yes go left */

else if(mid>0 && arr[mid]>arr[mid-1]){

return findLocalMinima(arr, start, mid);

}

else {

/*check if right neighbor is greater than mid element, if yes go right */

return findLocalMinima(arr, mid+1, end);

}

public static void main(String[] args) {

LocalMinima l = new LocalMinima();

int [] arr = {10, 5, 3, 6, 13, 16, 7};

System.out.println("Local Minima is: " + l.findLocalMinima(arr,0,arr.length));

}

When you run above program, you will get below output.

Local Minima is: 3

That’s all about how to find the local minima in a array

Was this post helpful?

Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.

Find the local minima in array

Problem