Wednesday, May 4, 2022

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

When you run the above program, you will get below output.
Local Minima is: 3

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


Don't miss the next article!
Be the first to be notified when a new article or Kubernetes experiment is published.                            

   

Share This


You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS