Question 23 : Find local minima in array

A local minimum is less than its neighbors

For example:

Input :
 
int [] arr = {10, 5, 2, 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(og n).
Here is a simple algorithm

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

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));
    }
}

Python code 

def find_local_minima(arr):
    n = len(arr)

    if n == 0:
        return -1
    if n == 1:
        return 0

    if arr[0] < arr[1]:
        return 0

    for i in range(1, n - 1):
        if arr[i] < arr[i - 1] and arr[i] < arr[i + 1]:
            return i

    if arr[n - 1] < arr[n - 2]:
        return n - 1

    return -1


print(find_local_minima([9, 6, 3, 14, 5, 7, 4]))

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

Java — Binary Search Local Minima

public class LocalMinimaBinarySearch {

    public static int findLocalMin(int[] arr, int low, int high) {
        int n = arr.length;
        int mid = low + (high - low) / 2;

        // Check if mid is local minima
        boolean leftOk = (mid == 0) || (arr[mid] < arr[mid - 1]);
        boolean rightOk = (mid == n - 1) || (arr[mid] < arr[mid + 1]);

        if (leftOk && rightOk) {
            return mid;
        }

        // If left neighbor is smaller, go left
        if (mid > 0 && arr[mid - 1] < arr[mid]) {
            return findLocalMin(arr, low, mid - 1);
        }

        // Else go right
        return findLocalMin(arr, mid + 1, high);
    }

    public static void main(String[] args) {
        int[] arr = {9, 6, 3, 14, 5, 7, 4};
        int index = findLocalMin(arr, 0, arr.length - 1);
        System.out.println("Local Minima index: " + index);
    }
}

Python — Binary Search Local Minima
def find_local_min(arr, low, high):
    n = len(arr)
    mid = (low + high) // 2

    left_ok = (mid == 0) or (arr[mid] < arr[mid - 1])
    right_ok = (mid == n - 1) or (arr[mid] < arr[mid + 1])

    if left_ok and right_ok:
        return mid

    if mid > 0 and arr[mid - 1] < arr[mid]:
        return find_local_min(arr, low, mid - 1)

    return find_local_min(arr, mid + 1, high)


arr = [9, 6, 3, 14, 5, 7, 4]
print(find_local_min(arr, 0, len(arr) - 1))

Brute Force — Nested Check (O(n²))

Java — Brute Force Nesteda
public class LocalMinimaBruteForce {

    public static int findLocalMin(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n; i++) {
            boolean isMin = true;

            for (int j = 0; j < n; j++) {
                if (i != j && arr[j] < arr[i]) {
                    isMin = false;
                    break;
                }
            }

            if (isMin) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {9, 6, 3, 14, 5, 7, 4};
        System.out.println(findLocalMin(arr));
    }
}
Python — Brute Force Nesteda
def local_min_bruteforce(arr):
    n = len(arr)

    for i in range(n):
        is_min = True
        for j in range(n):
            if i != j and arr[j] < arr[i]:
                is_min = False
                break
        if is_min:
            return i
    return -1


print(local_min_bruteforce([9,6,3,14,5,7,4]))

  
    
    
    
    
  

  

    
Approach
    
Time Complexity
    
Space Complexity
    
Best Use
  

  

    

      One-pass scan for local minima
    
    

      O(n)
    
    

      O(1)
    
    

      ⭐ Best & direct
    
  

  

    

      Divide & conquer binary search
    
    

      O(log n)
    
    

      O(1)
    
    

      ✔ Best when array is large
    
  

  

    

      Brute force (nested check)
    
    

      O(n²)
    
    

      O(1)
    
    

      ❌ Inefficient