Naive Approach
We can simply iterate through the array and check each element with its neighbouring elements. And return the peak element if found.
Algorithm
-
If the size of the array is 1, then return ‘Arr[0]’ and terminate.
-
Check for the first and last elements
-
If Arr[0] >= Arr[1], return Arr[0] and terminate.
-
If Arr[n-1]>=Arr[n-2] return Arr[n-1] and terminate.
-
Else Iterate through the array from index 1 to n-2
-
If Arr[ i ] >= Arr[ i-1 ] and Arr[ i ] >= Arr[ i+1 ] , return Arr[i]
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
int findPeakElement(vector<int>&nums, int n)
{
. // if there is only one element present.
if(n==1)
{
return nums[0];
}
// checking for first and last element.
if(nums[0]>=nums[1])
{
return nums[0];
}
if(nums[n-1]>=nums[n-2])
{
return nums[n-1];
}
// iterating the whole array, to find the peak.
for(int i=1;i<n-1;i++)
{
if(nums[i-1]<= nums[i] && nums[i+1]<=nums[i])
{
return nums[i];
}
}
return 0;
}
// main function to run the program.
int main()
{
int n;
cin>>n;
vector<int>nums(n);
for(int i=0;i<n;i++)
{
cin>>nums[i];
}
cout<<findPeakElement(nums,n);
return 0;
}
You can also try this code with Online C++ Compiler
Implementation in Java
import java.util.*;
public class Main
{
public static int findPeakElement(int[] nums, int n)
{
// if there is only one element present.
if (n == 1)
{
return nums[0];
}
. // checking for first and last element.
if (nums[0] >= nums[1])
{
return nums[0];
}
if (nums[n - 1] >= nums[n - 2])
{
return nums[n - 1];
}
. // iterating the whole array, to find the peak.
for (int i = 1; i < n - 1; i++)
{
if (nums[i - 1] <= nums[i] && nums[i + 1] <= nums[i])
{
return nums[i];
}
}
return 0;
}
// main function to run the program.
public static void main(String[] args)
{
// taking user input.
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++)
{
nums[i] = sc.nextInt();
}
System.out.println(findPeakElement(nums, n));
}
}
You can also try this code with Online Java Compiler
Implementation in Python
def findPeakElement(nums, n) :
# if only one element is present.
if n == 1:
return nums[0]
# checking for first and last element.
if nums[0] >= nums[1]:
return nums[0]
if nums[n - 1] >= nums[n - 2]:
return nums[n - 1]
# iterating the whole array, to find the peak.
for i in range(1, n - 1):
if nums[i - 1] <= nums[i] and nums[i + 1] <= nums[i]:
return nums[i]
return 0
# to run the program.
n = int(input())
nums = list(map(int, input().split()))
print(findPeakElement(nums, n))
You can also try this code with Online Python Compiler
Input
4
1 5 0 2
Output
5
Time Complexity
O(N), where N is the size of the array. At max, we are iterating the whole array. So the complexity is O(N).
Space Complexity
O(1). Constant space is used so the complexity is O(1)
Binary Search Approach:
Another idea for finding the peak element is by using a binary search. We can assume the given array as ascending and descending sequences of numbers.
We will start by checking the mid number if that is the peak element then we can return that. Otherwise, we will check the mid lies in a descending sequence or ascending sequence.
If the mid element lies in the descending sequence then we will find the mid in the left of the mid, otherwise, we will find the mid in the left of the mid elements.
Algorithm:
-
Start the binary search from start = 0 and end = n-1, when n is the length of the array.
-
Define mid as (start + end)/2
-
Check if mid is greater than its neighbours
.
-
If true then return the mid
-
If the left element is greater than mid
-
Repeat the binary search for the left half, i.e from start to end= mid-1
-
Else
-
Repeat the binary search for the right half, i.e from start=mid+1 to end
We can implement binary search in recursive and iterative ways let's see both the implementation:
Recursive Binary Search
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
int findPeakElement(vector<int>& nums, int start, int end)
{
// Base case.
if (start >= end)
{
return nums[start];
}
// defining mid
int mid = (start + end) / 2;
// if mid is the peak element.
if (( mid == 0 || nums[mid] >= nums[mid-1] ) &&
(mid == n-1 || nums[mid] >= nums[mid+1]))
{
return nums[mid];
}
// if mid is in descending sequence.
else if ( mid > 0 && nums[mid-1] > nums[mid])
{
return findPeakElement(nums, start, mid-1);
}
// if mid is in ascending peak.
else
{
return findPeakElement(nums, mid+1, end);
}
}
// main function to run the program.
int main()
{
int n;
cin>>n;
vector<int>nums(n);
for(int i=0;i<n;i++)
{
cin>>nums[i];
}
cout<<findPeakElement(nums,0,n-1);
return 0;
}
You can also try this code with Online C++ Compiler
Implementation in Java
import java.util.Scanner;
import java.util.Vector;
public class Main
{
public static int findPeakElement(int[] nums, int start, int end)
{
// Base condition.
if (start >= end)
{
return nums.get(start);
}
// Defining the mid.
int mid = (start + end) / 2;
// If mid is the peak.
if ((mid == 0 || nums[mid] >= nums[mid-1] ) &&
(mid == n-1 || nums[mid] >= nums[mid+1]))
{
return nums[mid];
}
else if ( mid > 0 && nums[mid-1] > nums[mid])
{
return findPeakElement(nums, start, mid-1);
}
else
{
return findPeakElement(nums, mid+1, end);
}
}
// main function to run the program.
public static void main(String[] args)
{
// taking user input.
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++)
{
nums[i] = sc.nextInt();
}
System.out.println(findPeakElement(nums, n));
}
}
You can also try this code with Online Java Compiler
Implementation in Python
def findPeakElement(nums, start, end):
. # Base case.
if start >= end:
return nums[start]
# Defining the mid
mid = (start + end) // 2
# If mid is the peak.
if mid == 0 or nums[mid] >= nums[mid-1] and mid == n-1 or nums[mid] >= nums[mid+1]:
return nums[mid]
elif mid > 0 and nums[mid-1] > nums[mid]:
return findPeakElement(nums, start, mid-1)
else:
return findPeakElement(nums, mid+1, end)
n = int(input())
nums = list(map(int, input().split()))
print(findPeakElement(nums, 0, n-1))
You can also try this code with Online Java Compiler
Input
4
1 5 0 2
Output
5
Time Complexity:
Log(N), where N is the number of elements in the array. Here in each iteration, our search space is reduced to half, hence the time complexity is Log2N.
Space Complexity:
Log(N) where N is of elements in the array. Here we are using the recursion so this space complexity accounts for the recursion stack.
Also see, Application of Graph in Data Structure
Iterative Binary search
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
int findPeakElement(vector<int>&nums, int n)
{
int start=0, end=n-1;
int mid;
while(start<=end)
{
mid=(start+end)/2;
// if mid is the peak.
if((mid==0 or nums[mid]>=nums[mid-1]) and
(mid==n-1 or nums[mid]>=nums[mid+1]))
{
break;
}
// if mid is in descending sequence.
if( mid > 0 and nums[mid]<nums[mid-1])
{
end=mid-1;
}
// if mid in ascending sequence.
else
{
start=mid+1;
}
}
return nums[mid];
}
// main function to run the program.
int main()
{
int n;
cin>>n;
vector<int>nums(n);
for(int i=0;i<n;i++)
{
cin>>nums[i];
}
cout<<findPeakElement(nums,n);
return 0;
}
You can also try this code with Online C++ Compiler
Implementation in Java
import java.util.*;
public class Main
{
public static int findPeakElement(int[] nums, int n)
{
int start = 0, end = n - 1;
int mid;
while (start <= end)
{
mid = (start + end) / 2;
// if mid is the peak.
if ((mid == 0 || nums[mid] >= nums[mid-1]) &&
(mid == n-1 || nums[mid] >= nums[mid+1]))
{
break;
}
// if mid is in descending sequence.
if (mid > 0 && nums[mid] < nums[mid-1])
{
end = mid - 1;
}
// if mid in ascending sequence.
else
{
start = mid + 1;
}
}
return nums[mid];
}
// main function to run the program.
public static void main(String[] args)
{
// taking user input.
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++)
{
nums[i] = sc.nextInt();
}
System.out.println(findPeakElement(nums, n));
}
}
You can also try this code with Online Java Compiler
Implementation in Python
def findPeakElement(nums, n):
start = 0
end = n - 1
while start <= end:
mid = (start + end) // 2
# if mid is the peak.
if (mid == 0 or nums[mid] >= nums[mid-1]) and (mid == n-1 or nums[mid] >= nums[mid+1]):
break
# if mid is in descending sequence.
if mid > 0 and nums[mid] < nums[mid-1]:
end = mid - 1
# if mid in ascending sequence.
else:
start = mid + 1
return nums[mid]
if __name__ == '__main__':
n = int(input())
nums = list(map(int, input().split()))
print(findPeakElement(nums, n))
You can also try this code with Online Python Compiler
Input
4
1 2 5 0
Output
5
Time Complexity:
Log(N), where N is the size of the array. Here in each iteration, our search space is reduced to half. Hence its complexity is log2N.
Space Complexity:
O(1), constant space is used.
Frequently Asked Questions
Which is the best algorithm to find the peak element in an array?
The best algorithm to find the peak element in an array is the iterative binary search approach. It has a time complexity of Log(N) and constant space complexity (O(1)).
We can find peak elements by iterating through each element in the array and by recursive binary search too.
Which data structure is used in recursion?
The stack data structure is used in recursion. In recursion, a function is called repeatedly by breaking it into smaller chunks until some condition is achieved. It is important to define a base function in recursion otherwise our program will never terminate.
What is the best case time complexity of binary search?
The best case complexity for binary search is O(1). When the element we are searching for is in the mid of the array. Then the program will exit at the first iteration only. Resulting in the best-case time complexity of O(1).
Conclusion
In this blog, we learned how to find the peak element or the local maximum element in a given unsorted array. We have seen different approaches for finding the peak and also saw how to implement this in different languages.
Head over to our enactment platform Coding Ninjas Studio to learn top problem solutions quickly, attempt mock tests, read interview experiences, and lots more.
Keep Coding!!
1+ registered 
