Given an array arr[] where no two adjacent elements are same, find the index of a peak element. An element is considered to be a peak element if it is strictly greater than its adjacent elements. If there are multiple peak elements, return the index of any one of them.
Note: Consider the element before the first element and the element after the last element to be negative infinity.
Examples:
Input: arr[] = [1, 2, 4, 5, 7, 8, 3]
Output: 5
Explanation: arr[5] = 8 is a peak element because arr[4] < arr[5] > arr[6].
Input: arr[] = [10, 20, 15, 2, 23, 90, 80]
Output: 1
Explanation: Element 20 at index 1 is a peak since 10 < 20 > 15. Index 5 (value 90) is also a peak, but returning any one peak index is valid.
[Naive Approach] Using Linear Search - O(n) Time and O(1) Space
The simplest approach is to iterate through the array and check if an element is greater than its neighbors. If it is, then it's a peak element.
C++ #include <iostream> #include <vector> using namespace std; int peakElement(vector<int> &arr) { int n = arr.size(); for(int i = 0; i < n; i++) { bool left = true; bool right = true; // Check for element to the left if(i > 0 && arr[i] <= arr[i - 1]) left = false; // Check for element to the right if(i < n - 1 && arr[i] <= arr[i + 1]) right = false; // If arr[i] is greater than its left as well as // its right element, return its index if(left && right) { return i; } } return 0; } int main() { vector<int> arr = {1, 2, 4, 5, 7, 8, 3}; cout << peakElement(arr); return 0; } #include <stdio.h> int peakElement(int arr[], int n) { for (int i = 0; i < n; i++) { int left = 1; int right = 1; // Check for element to the left if (i > 0 && arr[i] <= arr[i - 1]) left = 0; // Check for element to the right if (i < n - 1 && arr[i] <= arr[i + 1]) right = 0; // If arr[i] is greater than its left as well as // its right element, return its index if (left && right) { return i; } } return 0; } int main() { int arr[] = {1, 2, 4, 5, 7, 8, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", peakElement(arr, n)); return 0; } class GfG { static int peakElement(int[] arr) { int n = arr.length; for (int i = 0; i < n; i++) { boolean left = true; boolean right = true; // Check for element to the left if (i > 0 && arr[i] <= arr[i - 1]) left = false; // Check for element to the right if (i < n - 1 && arr[i] <= arr[i + 1]) right = false; // If arr[i] is greater than its left as well as // its right element, return its index if (left && right) { return i; } } return 0; } public static void main(String[] args) { int[] arr = {1, 2, 4, 5, 7, 8, 3}; System.out.println(peakElement(arr)); } } def peakElement(arr): n = len(arr) for i in range(n): left = True right = True # Check for element to the left if i > 0 and arr[i] <= arr[i - 1]: left = False # Check for element to the right if i < n - 1 and arr[i] <= arr[i + 1]: right = False # If arr[i] is greater than its left as well as # its right element, return its index if left and right: return i if __name__ == "__main__": arr = [1, 2, 4, 5, 7, 8, 3] print(peakElement(arr))
using System; class GfG { static int peakElement(int[] arr) { int n = arr.Length; for (int i = 0; i < n; i++) { bool left = true; bool right = true; // Check for element to the left if (i > 0 && arr[i] <= arr[i - 1]) left = false; // Check for element to the right if (i < n - 1 && arr[i] <= arr[i + 1]) right = false; // If arr[i] is greater than its left as well as // its right element, return its index if (left && right) { return i; } } return 0; } static void Main() { int[] arr = { 1, 2, 4, 5, 7, 8, 3 }; Console.WriteLine(peakElement(arr)); } } function peakElement(arr) { let n = arr.length; for (let i = 0; i < n; i++) { let left = true; let right = true; // Check for element to the left if (i > 0 && arr[i] <= arr[i - 1]) left = false; // Check for element to the right if (i < n - 1 && arr[i] <= arr[i + 1]) right = false; // If arr[i] is greater than its left as well as // its right element, return its index if (left && right) { return i; } } } // Driver Code let arr = [1, 2, 4, 5, 7, 8, 3]; console.log(peakElement(arr)); [Expected Approach] Using Binary Search - O(log n) Time and O(1) Space
If we observe carefully, we can say that:
If an element is smaller than it's next element then it is guaranteed that at least one peak element will exist on the right side of this element.
Conversely if an element is smaller than it's previous element then it is guaranteed that at least one peak element will exist on the left side of this element.
Therefore, we can use binary search to find the peak element.
Why it is guaranteed that peak element will definitely exist on the right side of an element, if its next element is greater than it?
If we keep moving in the right side of this element, as long as the elements are increasing, we will eventually reach an element that is either:
- The last element of the array, which will be a peak as it is greater than or equal to its previous element.
- An element where the sequence is no longer increasing, i.e., arr[i] > arr[i + 1], which would be a peak element.
For the same reasons, if an element is lesser than its previous element, then it is guaranteed that at least one peak element will exist on the left side of that element.
C++ #include <iostream> #include <vector> using namespace std; int peakElement(vector<int> &arr) { int n = arr.size(); // If there is only one element, then it's a peak if (n == 1) return 0; // Check if the first element is a peak if (arr[0] > arr[1]) return 0; // Check if the last element is a peak if (arr[n - 1] > arr[n - 2]) return n - 1; // Search Space for binary Search int lo = 1, hi = n - 2; while(lo <= hi) { int mid = lo + (hi - lo)/2; // If the element at mid is a // peak element return mid if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) return mid; // If next neighbor is greater, then peak // element will exist in the right subarray if(arr[mid] < arr[mid + 1]) lo = mid + 1; // Otherwise, it will exist in left subarray else hi = mid - 1; } return 0; } int main() { vector<int> arr = {1, 2, 4, 5, 7, 8, 3}; cout << peakElement(arr); return 0; } #include <stdio.h> int peakElement(int arr[], int n) { // If there is only one element, then it's a peak if (n == 1) return 0; // Check if the first element is a peak if (arr[0] > arr[1]) return 0; // Check if the last element is a peak if (arr[n - 1] > arr[n - 2]) return n - 1; // Search Space for binary Search int lo = 1, hi = n - 2; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // If the element at mid is a // peak element return mid if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) return mid; // If next neighbor is greater, then peak // element will exist in the right subarray if (arr[mid] < arr[mid + 1]) lo = mid + 1; // Otherwise, it will exist in left subarray else hi = mid - 1; } return 0; } int main() { int arr[] = {1, 2, 4, 5, 7, 8, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", peakElement(arr, n)); return 0; } class GfG { static int peakElement(int[] arr) { int n = arr.length; // If there is only one element, then it's a peak if (n == 1) return 0; // Check if the first element is a peak if (arr[0] > arr[1]) return 0; // Check if the last element is a peak if (arr[n - 1] > arr[n - 2]) return n - 1; // Search Space for binary Search int lo = 1, hi = n - 2; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // If the element at mid is a // peak element return mid if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) return mid; // If next neighbor is greater, then peak // element will exist in the right subarray if (arr[mid] < arr[mid + 1]) lo = mid + 1; // Otherwise, it will exist in left subarray else hi = mid - 1; } return 0; } public static void main(String[] args) { int[] arr = {1, 2, 4, 5, 7, 8, 3}; System.out.println(peakElement(arr)); } } def peakElement(arr): n = len(arr) # If there is only one element, then it's a peak if n == 1: return 0 # Check if the first element is a peak if arr[0] > arr[1]: return 0 # Check if the last element is a peak if arr[n - 1] > arr[n - 2]: return n - 1 # Search Space for binary Search lo, hi = 1, n - 2 while lo <= hi: mid = lo + (hi - lo) // 2 # If the element at mid is a # peak element return mid if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1]: return mid # If next neighbor is greater, then peak # element will exist in the right subarray if arr[mid] < arr[mid + 1]: lo = mid + 1 # Otherwise, it will exist in left subarray else: hi = mid - 1 if __name__ == "__main__": arr = [1, 2, 4, 5, 7, 8, 3] print(peakElement(arr))
using System; class GfG { static int peakElement(int[] arr) { int n = arr.Length; // If there is only one element, then it's a peak if (n == 1) return 0; // Check if the first element is a peak if (arr[0] > arr[1]) return 0; // Check if the last element is a peak if (arr[n - 1] > arr[n - 2]) return n - 1; // Search Space for binary Search int lo = 1, hi = n - 2; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // If the element at mid is a // peak element return mid if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) return mid; // If next neighbor is greater, then peak // element will exist in the right subarray if (arr[mid] < arr[mid + 1]) lo = mid + 1; // Otherwise, it will exist in left subarray else hi = mid - 1; } return 0; } static void Main() { int[] arr = {1, 2, 4, 5, 7, 8, 3}; Console.WriteLine(peakElement(arr)); } } function peakElement(arr) { let n = arr.length; // If there is only one element, then it's a peak if (n === 1) return 0; // Check if the first element is a peak if (arr[0] > arr[1]) return 0; // Check if the last element is a peak if (arr[n - 1] > arr[n - 2]) return n - 1; // Search Space for binary Search let lo = 1, hi = n - 2; while (lo <= hi) { let mid = lo + Math.floor((hi - lo) / 2); // If the element at mid is a // peak element return mid if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) return mid; // If next neighbor is greater, then peak // element will exist in the right subarray if (arr[mid] < arr[mid + 1]) lo = mid + 1; // Otherwise, it will exist in left subarray else hi = mid - 1; } return 0; } // Driver Code const arr = [ 1, 2, 4, 5, 7, 8, 3 ]; console.log(peakElement(arr)); Related Articles:
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem