Find a Peak Element in an array

Given an array of size n, find a peak element in the array. Peak element is the element which is greater than or equal to its neighbors.
For example - In Array {1,4,3,6,7,5}, 4 and 7 are peak elements. We need to return any one peak element.


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

Linear approach:
One way to solve this problem is to iterate over the array and find an element that is greater than or equal to its neighbors and return it.
Time Complexity: O(n)
Efficient approach:
1. Initialize start = 0, end = array.length - 1
2. Repeat following steps till peak element is found:
   a). Find mid = (start+end)/2
   b). If array[mid] is peak element, return array[mid]
   c). Else if array[mid-1] > array[mid], find peak in left half of array
       set end = mid - 1
   d). Else find peak in right half of array
       set start = mid + 1
Time Complexity: O(log n)


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.saurabh.questions;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * <br><br>
 * Peak Element</b><br>
 * Given an array of size n, find a peak element. Peak element is the element which is greater or equal to all its neighbors.<br><br>
 * <br><br>
 * Ex. Array [1,4,3,6,7,5]
 * <br>
 * Output: 4
 * <br><br>
 * <a href="https://www.youtube.com/watch?v=zOyOwDEF1Rc">Peak Element - Youtube Link</a> 
 * @author Saurabh
 *
 */
public class PeakElement {

    public static Integer getPeakElement(int[] array) {

        if (array == null || array.length == 0) {
            return null;
        }

        int n = array.length;

        int start = 0;
        int end = n - 1;

        while (start <= end) {
            int mid = (start + end) / 2;

            if ((mid == 0 || array[mid - 1] <= array[mid]) && (mid == n - 1 || array[mid] >= array[mid + 1])) {
                return array[mid]; // array[mid] is peak element
            } else if (mid > 0 && array[mid - 1] > array[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        int[] array = { 15, 20, 25, 35, 45, 50, 60 };
        Integer peak = getPeakElement(array);
        System.out.println(peak != null ? "Peak Element is " + peak : "No peak element!");
    }
}
		

Order of the Algorithm

Time Complexity is O(log n)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

    Saurabh Kumar

    Ninja Programmer