Given an array arr of n elements that is first strictly increasing and then maybe strictly decreasing, find the maximum element in the array.
Note: If the array is increasing then just print the last element will be the maximum value.
Example:
Input: array[]= {5, 10, 20, 15}
Output: 20
Explanation: The element 20 has neighbors 10 and 15, both of them are less than 20.
Input: array[] = {10, 20, 15, 2, 23, 90, 67}
Output: 20 or 90
Explanation: The element 20 has neighbors 10 and 15, both of them are less than 20, similarly 90 has neighbors 23 and 67.
The following corner cases give a better idea about the problem.
- If the input array is sorted in a strictly increasing order, the last element is always a peak element. For example, 50 is peak element in {10, 20, 30, 40, 50}.
- If the input array is sorted in a strictly decreasing order, the first element is always a peak element. 100 is the peak element in {100, 80, 60, 50, 20}.
- If all elements of the input array are the same, every element is a peak element.
It is clear from the above examples that there is always a peak element in the input array.
Naive Approach: Below is the idea to solve the problem
The array can be traversed and the element whose neighbors are less than that element can be returned.
Follow the below steps to Implement the idea:
- If the first element is greater than the second or the last element is greater than the second last, print the respective element and terminate the program.
- Else traverse the array from the second index to the second last index i.e. 1 to N – 1
- If for an element array[i] is greater than both its neighbors, i.e., array[i] > =array[i-1] and array[i] > =array[i+1] , then print that element and terminate.
Below is the implementation of above idea.
C++
#include <bits/stdc++.h>
using namespace std;
int findPeak( int arr[], int n)
{
if (n == 1)
return 0;
if (arr[0] >= arr[1])
return 0;
if (arr[n - 1] >= arr[n - 2])
return n - 1;
for ( int i = 1; i < n - 1; i++) {
if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1])
return i;
}
}
int main()
{
int arr[] = { 1, 3, 20, 4, 1, 0 };
int n = sizeof (arr) / sizeof (arr[0]);
cout << "Index of a peak point is " << findPeak(arr, n);
return 0;
}
|
C
#include <stdio.h>
int findPeak( int arr[], int n)
{
if (n == 1)
return 0;
if (arr[0] >= arr[1])
return 0;
if (arr[n - 1] >= arr[n - 2])
return n - 1;
for ( int i = 1; i < n - 1; i++) {
if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1])
return i;
}
}
int main()
{
int arr[] = { 1, 3, 20, 4, 1, 0 };
int n = sizeof (arr) / sizeof (arr[0]);
printf ( "Index of a peak point is %d" ,findPeak(arr, n));
return 0;
}
|
Java
import java.util.*;
class GFG {
static int findPeak( int arr[], int n)
{
if (n == 1 )
return 0 ;
if (arr[ 0 ] >= arr[ 1 ])
return 0 ;
if (arr[n - 1 ] >= arr[n - 2 ])
return n - 1 ;
for ( int i = 1 ; i < n - 1 ; i++) {
if (arr[i] >= arr[i - 1 ] && arr[i] >= arr[i + 1 ])
return i;
}
return 0 ;
}
public static void main(String[] args)
{
int arr[] = { 1 , 3 , 20 , 4 , 1 , 0 };
int n = arr.length;
System.out.print( "Index of a peak point is " + findPeak(arr, n));
}
}
|
Python3
def findPeak(arr, n) :
if (n = = 1 ) :
return 0
if (arr[ 0 ] > = arr[ 1 ]) :
return 0
if (arr[n - 1 ] > = arr[n - 2 ]) :
return n - 1
for i in range ( 1 , n - 1 ) :
if (arr[i] > = arr[i - 1 ] and arr[i] > = arr[i + 1 ]) :
return i
arr = [ 1 , 3 , 20 , 4 , 1 , 0 ]
n = len (arr)
print ( "Index of a peak point is" , findPeak(arr, n))
|
C#
using System;
public class GFG{
static int findPeak( int []arr, int n)
{
if (n == 1)
return 0;
if (arr[0] >= arr[1])
return 0;
if (arr[n - 1] >= arr[n - 2])
return n - 1;
for ( int i = 1; i < n - 1; i++)
{
if (arr[i] >= arr[i - 1] &&
arr[i] >= arr[i + 1])
return i;
}
return 0;
}
public static void Main(String[] args)
{
int []arr = { 1, 3, 20, 4, 1, 0 };
int n = arr.Length;
Console.Write( "Index of a peak point is " +
findPeak(arr, n));
}
}
|
Javascript
<script>
function findPeak(arr, n)
{
if (n == 1) return 0;
if (arr[0] >= arr[1]) return 0;
if (arr[n - 1] >= arr[n - 2]) return n - 1;
for ( var i = 1; i < n - 1; i++)
{
if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1]) return i;
}
}
var arr = [1, 3, 20, 4, 1, 0];
var n = arr.length;
document.write( "Index of a peak point is " + findPeak(arr, n));
</script>
|
Output
Index of a peak point is 2
Time complexity: O(n), One traversal is needed so the time complexity is O(n)
Auxiliary Space: O(1), No extra space is needed, so space complexity is constant
Find a peak element using recursive Binary Search
Below is the idea to solve the problem.
Using Binary Search, check if the middle element is the peak element or not. If the middle element is not the peak element, then check if the element on the right side is greater than the middle element then there is always a peak element on the right side. If the element on the left side is greater than the middle element then there is always a peak element on the left side.
Follow the steps below to implement the idea:
- Create two variables, l and r, initialize l = 0 and r = n-1
- Recursively perform the below steps till l <= r, i.e. lowerbound is less than the upperbound
- Check if the mid value or index mid = low + (high – low) / 2, is the peak element or not, if yes then print the element and terminate.
- Else if the element on the left side of the middle element is greater then check for peak element on the left side, i.e. update r = mid – 1
- Else if the element on the right side of the middle element is greater then check for peak element on the right side, i.e. update
Below is the implementation of the above approach
C++
#include <bits/stdc++.h>
using namespace std;
int findPeakUtil( int arr[], int low,
int high, int n)
{
int mid = low + (high - low) / 2;
if ((mid == 0 || arr[mid - 1] <= arr[mid]) &&
(mid == n - 1 || arr[mid + 1] <= arr[mid]))
return mid;
else if (mid > 0 && arr[mid - 1] > arr[mid])
return findPeakUtil(arr, low, (mid - 1), n);
else
return findPeakUtil(
arr, (mid + 1), high, n);
}
int findPeak( int arr[], int n)
{
return findPeakUtil(arr, 0, n - 1, n);
}
int main()
{
int arr[] = { 1, 3, 20, 4, 1, 0 };
int n = sizeof (arr) / sizeof (arr[0]);
cout << "Index of a peak point is "
<< findPeak(arr, n);
return 0;
}
|
C
#include <stdio.h>
int findPeakUtil(
int arr[], int low, int high, int n)
{
int mid = low + (high - low) / 2;
if ((mid == 0 || arr[mid - 1] <= arr[mid]) && (mid == n - 1 || arr[mid + 1] <= arr[mid]))
return mid;
else if (mid > 0 && arr[mid - 1] > arr[mid])
return findPeakUtil(arr, low, (mid - 1), n);
else
return findPeakUtil(arr, (mid + 1), high, n);
}
int findPeak( int arr[], int n)
{
return findPeakUtil(arr, 0, n - 1, n);
}
int main()
{
int arr[] = { 1, 3, 20, 4, 1, 0 };
int n = sizeof (arr) / sizeof (arr[0]);
printf (
"Index of a peak point is %d" , findPeak(arr, n));
return 0;
}
|
Java
import java.util.*;
import java.lang.*;
import java.io.*;
class PeakElement {
static int findPeakUtil(
int arr[], int low, int high, int n)
{
int mid = low + (high - low) / 2 ;
if ((mid == 0 || arr[mid - 1 ] <= arr[mid])
&& (mid == n - 1 || arr[mid + 1 ] <= arr[mid]))
return mid;
else if (mid > 0 && arr[mid - 1 ] > arr[mid])
return findPeakUtil(arr, low, (mid - 1 ), n);
else
return findPeakUtil(
arr, (mid + 1 ), high, n);
}
static int findPeak( int arr[], int n)
{
return findPeakUtil(arr, 0 , n - 1 , n);
}
public static void main(String[] args)
{
int arr[] = { 1 , 3 , 20 , 4 , 1 , 0 };
int n = arr.length;
System.out.println(
"Index of a peak point is " + findPeak(arr, n));
}
}
|
Python3
def findPeakUtil(arr, low, high, n):
mid = low + (high - low) / 2
mid = int (mid)
if ((mid = = 0 or arr[mid - 1 ] < = arr[mid]) and
(mid = = n - 1 or arr[mid + 1 ] < = arr[mid])):
return mid
elif (mid > 0 and arr[mid - 1 ] > arr[mid]):
return findPeakUtil(arr, low, (mid - 1 ), n)
else :
return findPeakUtil(arr, (mid + 1 ), high, n)
def findPeak(arr, n):
return findPeakUtil(arr, 0 , n - 1 , n)
arr = [ 1 , 3 , 20 , 4 , 1 , 0 ]
n = len (arr)
print ( "Index of a peak point is" , findPeak(arr, n))
|
C#
using System;
class GFG {
static int findPeakUtil( int [] arr, int low,
int high, int n)
{
int mid = low + (high - low) / 2;
if ((mid == 0 || arr[mid - 1] <= arr[mid]) && (mid == n - 1 || arr[mid + 1] <= arr[mid]))
return mid;
else if (mid > 0 && arr[mid - 1] > arr[mid])
return findPeakUtil(arr, low,
(mid - 1), n);
else
return findPeakUtil(arr, (mid + 1),
high, n);
}
static int findPeak( int [] arr,
int n)
{
return findPeakUtil(arr, 0,
n - 1, n);
}
static public void Main()
{
int [] arr = { 1, 3, 20,
4, 1, 0 };
int n = arr.Length;
Console.WriteLine( "Index of a peak "
+ "point is " + findPeak(arr, n));
}
}
|
Javascript
function findPeakUtil(arr, low, high, n)
{
var mid = low + parseInt((high - low) / 2);
if ((mid == 0 || arr[mid - 1] <= arr[mid]) &&
(mid == n - 1 || arr[mid + 1] <= arr[mid]))
return mid;
else if (mid > 0 && arr[mid - 1] > arr[mid])
return findPeakUtil(arr, low, (mid - 1), n);
else
return findPeakUtil(
arr, (mid + 1), high, n);
}
function findPeak(arr, n)
{
return findPeakUtil(arr, 0, n - 1, n);
}
var arr = [ 1, 3, 20, 4, 1, 0 ];
var n = arr.length;
console.log( "Index of a peak point is "
+ findPeak(arr, n));
|
PHP
<?php
function findPeakUtil( $arr , $low ,
$high , $n )
{
$mid = $low + ( $high - $low ) / 2;
if (( $mid == 0 ||
$arr [ $mid - 1] <= $arr [ $mid ]) &&
( $mid == $n - 1 ||
$arr [ $mid + 1] <= $arr [ $mid ]))
return $mid ;
else if ( $mid > 0 &&
$arr [ $mid - 1] > $arr [ $mid ])
return findPeakUtil( $arr , $low ,
( $mid - 1), $n );
else return (findPeakUtil( $arr , ( $mid + 1),
$high , $n ));
}
function findPeak( $arr , $n )
{
return floor (findPeakUtil( $arr , 0,
$n - 1, $n ));
}
$arr = array (1, 3, 20, 4, 1, 0);
$n = sizeof( $arr );
echo "Index of a peak point is " ,
findPeak( $arr , $n );
?>
|
Output
Index of a peak point is 2
Time Complexity: O(log N), Where N is the number of elements in the input array.
Auxiliary Space: O(log N), As recursive call is there, hence implicit stack is used.
Find a peak element using iterative Binary search
Below is the idea to solve the problem.
Using Binary Search, check if the middle element is the peak element or not. If the middle element the peak element terminate the while loop and print middle element, then check if the element on the right side is greater than the middle element then there is always a peak element on the right side. If the element on the left side is greater than the middle element then there is always a peak element on the left side.
Follow the steps below to implement the idea:
- Create two variables, l and r, initialize l = 0 and r = n-1
- Run a while loop till l <= r, lowerbound is less than the upperbound
- Check if the mid value or index mid = low + (high – low) / 2, is the peak element or not, if yes then print the element and terminate.
- Else if the element on the left side of the middle element is greater then check for peak element on the left side, i.e. update r = mid – 1
- Else if the element on the right side of the middle element is greater then check for peak element on the right side, i.e. update
The below-given code is the iterative version of the above explained and demonstrated recursive based divide and conquer technique.
C++
#include <bits/stdc++.h>
using namespace std;
int findPeak( int arr[], int n)
{
int l = 0;
int r = n-1;
int mid;
while (l <= r) {
mid = (l + r) >> 1;
if ((mid == 0 || arr[mid - 1] <= arr[mid])
and (mid == n - 1 || arr[mid + 1] <= arr[mid]))
break ;
if (mid > 0 and arr[mid - 1] > arr[mid])
r = mid - 1;
else
l = mid + 1;
}
return mid;
}
int main()
{
int arr[] = { 1, 3, 20, 4, 1, 0 };
int N = sizeof (arr) / sizeof (arr[0]);
cout << "Index of a peak point is " << findPeak(arr, N);
return 0;
}
|
C
#include <stdio.h>
int findPeak( int arr[], int n)
{
int l = 0;
int r = n-1;
int mid;
while (l <= r) {
mid = (l + r) >> 1;
if ((mid == 0 || arr[mid - 1] <= arr[mid])
&& (mid == n - 1 || arr[mid + 1] <= arr[mid]))
break ;
if (mid > 0 && arr[mid - 1] > arr[mid])
r = mid - 1;
else
l = mid + 1;
}
return mid;
}
int main()
{
int arr[] = { 1, 3, 20, 4, 1, 0 };
int n = sizeof (arr) / sizeof (arr[0]);
printf ( "Index of a peak point is %d" , findPeak(arr, n));
return 0;
}
|
Java
import java.io.*;
class GFG {
static int findPeak( int arr[], int n)
{
int l = 0 ;
int r = n- 1 ;
int mid = 0 ;
while (l <= r) {
mid = (l + r) >> 1 ;
if ((mid == 0
|| arr[mid - 1 ] <= arr[mid])
&& (mid == n - 1
|| arr[mid + 1 ] <= arr[mid]))
break ;
if (mid > 0 && arr[mid - 1 ] > arr[mid])
r = mid - 1 ;
else
l = mid + 1 ;
}
return mid;
}
public static void main(String args[])
{
int arr[] = { 1 , 3 , 20 , 4 , 1 , 0 };
int n = arr.length;
System.out.println( "Index of a peak point is "
+ findPeak(arr, n));
}
}
|
Python3
def findPeak(arr, n):
l = 0
r = n - 1
while (l < = r):
mid = (l + r) >> 1
if ((mid = = 0 or arr[mid - 1 ] < = arr[mid]) and (mid = = n - 1 or arr[mid + 1 ] < = arr[mid])):
break
if (mid > 0 and arr[mid - 1 ] > arr[mid]):
r = mid - 1
else :
l = mid + 1
return mid
arr = [ 1 , 3 , 20 , 4 , 1 , 0 ]
n = len (arr)
print (f "Index of a peak point is {findPeak(arr, n)}" )
|
C#
using System;
public class GFG {
static int findPeak( int [] arr, int n)
{
int l = 0;
int r = n-1;
int mid = 0;
while (l <= r) {
mid = (l + r) >> 1;
if ((mid == 0
|| arr[mid - 1] <= arr[mid]
&& (mid == n - 1
|| arr[mid + 1] <= arr[mid])))
break ;
if (mid > 0 && arr[mid - 1] > arr[mid])
r = mid - 1;
else
l = mid + 1;
}
return mid;
}
public static void Main(String[] args)
{
int [] arr = { 1, 3, 20, 4, 1, 0 };
int n = arr.Length;
Console.WriteLine( "Index of a peak point is "
+ findPeak(arr, n));
}
}
|
Javascript
<script>
function findPeakUtil(arr, low, high, n)
{
let l = low;
let r = high - 1;
let mid;
while (l <= r)
{
mid = (l + r) >> 1;
if ((mid == 0 || arr[mid - 1] <= arr[mid]) &&
(mid == n - 1 || arr[mid + 1] <= arr[mid]))
break ;
if (mid > 0 && arr[mid - 1] > arr[mid])
r = mid - 1;
else
l = mid + 1;
}
return mid;
}
function findPeak(arr,n)
{
return findPeakUtil(arr, 0, n, n);
}
let arr = [ 1, 3, 20, 4, 1, 0 ];
let n = arr.length;
document.write( "Index of a peak point is " +findPeak(arr, n));
</script>
|
Output
Index of a peak point is 2
Time Complexity: O(log N), Where n is the number of elements in the input array. In each step our search becomes half. So it can be compared to Binary search, So the time complexity is O(log N)
Auxiliary Space: O(1), No extra space is required, so the space complexity is constant.
Exercise:
Consider the following modified definition of peak element. An array element is a peak if it is greater than its neighbors. Note that an array may not contain a peak element with this modified definition.
References:
http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
Related Problem:
Find local minima in an array
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!