You are given an array 'arr' of length 'n'. Find the index(0-based) of a peak element in the array. If there are multiple peak numbers, return the index of any peak number.
Peak element is defined as that element that is greater than both of its neighbors. If 'arr[i]' is the peak element, 'arr[i - 1]' < 'arr[i]' and 'arr[i + 1]' < 'arr[i]'.
Assume 'arr[-1]' and 'arr[n]' as negative infinity.
1. There are no 2 adjacent elements having same value (as mentioned in the constraints).
2. Do not print anything, just return the index of the peak element (0 - indexed).
3. 'True'/'False' will be printed depending on whether your answer is correct or not.
Example:
Input: 'arr' = [1, 8, 1, 5, 3]
Output: 3
Explanation: There are two possible answers. Both 8 and 5 are peak elements, so the correct answers are their positions, 1 and 3.
The first line contains an integer ‘n’, the number of elements in 'arr'.
The second line contains ‘n’ space-separated integers , the array 'arr'.
The output contains True/ False depending whether the found number is peak element or not.
5
1 8 1 5 3
1
True
There are two possible answers. Both 8 and 5 are peak elements, so the correct answers are their positions, 1 and 3. Any of these 2 numbers will print 'True'.
3
1 2 1
1
True
The expected time complexity is O(log 'n').
1 <= 'n' <= 10^5
1 <= 'arr[i]' <= 10^5
'arr[i]' != 'arr[i + 1]' for all 'i' in range 0 <= 'i' < 'n' - 1
Check for all elements if they are peak or not.
Keeping the above example in mind, we can write the following solution:
O(‘n’), where ‘n’ is the number of elements in the sequence.
We need to traverse the array once to find the peak element.
Hence the time complexity is O(‘N’).
O(1)
We are using constant space.
Hence the space complexity is O(1).
All tags
Sort by
Interview problems
Easy Java Solution
import java.util.ArrayList;
public class Solution {
public static int findPeakElement(ArrayList<Integer> arr) {
// Write your code here.
if(arr.get(0)>arr.get(1)) return 0;
for(int i=1;i<arr.size()-1;i++){
if(arr.get(i)>arr.get(i-1) && arr.get(i)>arr.get(i+1)) return i;
}
if(arr.get(arr.size()-1)>arr.get(arr.size()-2)) return arr.size()-1;
return 0;
}
};
Interview problems
find Peak element time complexity O(log n)
int findPeakElement(vector<int> &arr) {
int n = arr.size();
if(n == 1) return 0;
if(arr[0] > arr[1]) return 0; // If the peak is first element
if(arr[n - 1] > arr[n - 2]) return n - 1; // If the peak is last element
int st = 1;
long long end = n - 2;
while(st <= end) {
int mid = st+(end-st)/2;
// If the mid element is a peak element
if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
return mid;
}
// If the mid is in left half it means peak is in right half
if(arr[mid] > arr[mid - 1]) {
st = mid + 1;
}
// If the mid is in right half it means peak is in left half
else {
end = mid - 1;
}
}
return -1;
}
Interview problems
Using Binary Search C++
int findPeakElement(vector<int> &arr) {
int n = arr.size();
if(n == 1) return 0;
if(arr[0] > arr[1]) return 0; // If the peak is first element
if(arr[n - 1] > arr[n - 2]) return n - 1; // If the peak is last element
int low = 1;
long long high = n - 2;
while(low <= high) {
int mid = (low + high) / 2;
// If the mid element is a peak element
if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
return mid;
}
// If the mid is in left half it means peak is in right half
if(arr[mid] > arr[mid - 1]) {
low = mid + 1;
}
// If the mid is in right half it means peak is in left half
else {
high = mid - 1;
}
}
return -1;
}
Interview problems
JAVA
import java.util.ArrayList;
public class Solution {
public static int isPeak(ArrayList<Integer> arr,int low,int high){
if (low == high) {
return low;
}
int mid = low + (high - low) / 2;
if (arr.get(mid) > arr.get(mid + 1)) {
return isPeak(arr, low, mid);
} else {
return isPeak(arr, mid + 1, high);
}
}
public static int findPeakElement(ArrayList<Integer> arr) {
// Write your code here.
return isPeak( arr,0, arr.size()-1);
}
};
Interview problems
c++
int findPeakElement(vector<int> &arr) {
// Write your code here
for(int i=1;i<arr.size();i++){
if((arr[i-1]<arr[i]) && (arr[i+1]<arr[i])){
return i;
}
}
}
Interview problems
easy solution c++ Peak element
#include <bits/stdc++.h>
int findPeakElement(vector<int> &arr) {
int n = arr.size();
for(int i =0 ; i<n; i++){
if(arr[i]>arr[i-1]&& arr[i]>arr[i+1]){
return i;
}
if( i ==0 && arr[i]> arr[i+1]){
return i;
}
if(i ==(n-1) && arr[i]> arr[i-1]){
return i;
}
}
}
Interview problems
Easiest Binary Search Approach
int findPeakElement(vector<int> &arr) {
int n = arr.size();
if(n == 1) return 0;
if(arr[0] > arr[1]) return 0; // If the peak is first element
if(arr[n - 1] > arr[n - 2]) return n - 1; // If the peak is last element
int low = 1;
long long high = n - 2;
while(low <= high) {
int mid = (low + high) / 2;
// If the mid element is a peak element
if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
return mid;
}
// If the mid is in left half it means peak is in right half
if(arr[mid] < arr[mid + 1]) {
low = mid + 1;
}
// If the mid is in right half it means peak is in left half
else {
high = mid - 1;
}
}
return -1;
}
Interview problems
Java Solution
import java.util.ArrayList;
public class Solution {
public static int findPeakElement(ArrayList<Integer> arr) {
// Write your code here.
int n=arr.size();
if(arr.size()==1){
return 0;
}
if(arr.get(0)>arr.get(1)){
return 0;
}
if(arr.get(n-1)>arr.get(n-2)){
return n-1;
}
int start=1;
int end=n-2;
while(end>=start){
int mid=start+(end-start)/2;
if(arr.get(mid)>arr.get(mid-1) && arr.get(mid)>arr.get(mid+1)){
return mid;
}
else if(arr.get(mid)>arr.get(mid+1) && arr.get(mid)<arr.get(mid-1)){
end=mid-1;
}
else{
start=mid+1;
}
}
return -1;
}
};
Interview problems
python solution
def findPeakElement(arr: [int]) -> int:
# Write your code here
for i in range(1,len(arr)-1,1):
if arr[i-1] < arr[i] > arr[i+1]:
return i
if arr[0] > arr[1]:
return 0
if arr[-1] > arr[-2]:
return len(arr) - 1
pass
Interview problems
Find Peak Element
The time complexity of the findPeakElement function is O(logn)O(\log n)O(logn).
Explanation:Binary Search Approach:
Logarithmic Time:
For an array like [1, 2, 3, 1], the algorithm will find 3 as a peak element, as it satisfies the condition of being greater than its neighbors.
Summary:This makes the algorithm both time and space efficient for finding a peak element in an array.
