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

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)

Like IDeserve?

Support us by whitelisting IDeserve in your ad-blocker.

Thanks, -Team IDeserve

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

Like IDeserve?

Support us by whitelisting IDeserve in your ad-blocker.