Given an array of integers, write a code to find peak element in array. The array may contain multiple peak elements, in that case, return anyone peak element.
Peak Element
Peak element is an element which greater than it’s neighbours. For strictly decreasing array, the first element is the peak element. And for strictly increasing array the last element is the peak element.
For example:
Example 1:
Input: {2, 3, 4, 7, 5} , Output: 7
The element 7 is greater than it’s neighbours (4 and 5).
Example 2:
Input: {8, 7, 6, 5, 4}, Output: 8
In this example, An array is strictly decreasing, so the first element is the peak element.
Example 3:
Input: {2, 3, 4, 5, 6}, Output: 6
An array is strictly increasing, so the last element is the peak element.
Example 4:
Input: {2, 2, 2, 2, 2}, Output: 2
All the array element is the same, So every element in this array is the peak element.
Now, we have discussed the problem statement with multiple examples. Let’s think how we can solve this problem efficiently.
In this tutorial, I am going to discuss multiple approaches and their time and space complexities to solve this problem. Also, we will write it’s java code.
At the end of this tutorial, I have mentioned the video link for finding the peak element in an array.
Find Peak Element in Array using Linear Scan – Java Code
Let’s start with the easiest appraoch. The idea here is to traverse an array and check if current number is greater than the next number (arr[i] > arr[i+1]). If it is greater than the next number then it’s a peak element.
Using this approach we can easily find all the peak points in an array but as per the problem statement we have to return anyone peak element. So, after finding the first peak element simply return the element.
You can simply visualize this approach by seeing this graph. The time complexity of this approach is O(n) and it’s space complexity is O(1).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
/* Java code to find the peak element in an array using a linear scan. */ public class PeakElement { public static int findPeak(int[] arr) { //Traverse an array for(int i = 0; i < arr.length -1; i++) { /* If the current element is greater than the next element. */ if(arr[i] > arr[i+1]) { return arr[i]; } } return arr[arr.length-1]; } public static void main(String[] args) { int[] arr = {2, 3, 4, 7, 5}; //int[] arr = {2, 2, 2, 2, 2}; //int[] arr = {8, 7, 6, 5, 4}; //int[] arr = {1}; int result = findPeak(arr); System.out.println(result); } } |
Find Peak Element in Array using Binary Search – Java Code
In our previous approach, we have discussed how we can find a peak element using linear scan. Let’s optimize our solution to solve this problem in logarithmic time.
In this approach, I am going to discuss how we can find a peak element using binary search.
In case, If you are not familiar with binary search then check my previous tutorial on binary search program in java.
Programming questions on binary search
Here is the algorithm to solve this problem using binary search.
First, we have to compute the mid. After computing the mid compare with its neighbours. If the element present at mid index is greater than both of its neighbours, then return the element, it is a peak.
If the right element (element present at mid+1 index) is greater, then find the peak in the right side of the array. If the left element (element present at mid-1 index) is greater, then find the peak in the left side of the array
The time complexity of this approach is O(logn).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
/* Find peak element using binary search. */ public class PeakElement { public static int findUsingBinarySearch(int[] arr) { int n = arr.length; int start = 0; int end = n - 1; while (start <= end) { int mid = (start + end) / 2; if ((mid == 0 || arr[mid - 1] <= arr[mid]) && (mid == n - 1 || arr[mid] >= arr[mid + 1])) { return arr[mid]; } else if (mid > 0 && arr[mid - 1] > arr[mid]) { end = mid - 1; } else { start = mid + 1; } } return -1; } public static void main(String[] args) { int[] arr = {2, 3, 4, 7, 5}; //int[] arr = {2, 2, 2, 2, 2}; //int[] arr = {8, 7, 6, 5, 4}; int result = findUsingBinarySearch(arr); System.out.println(result); } } |
