Peak element in Array - Arrays

Problem Statement: Given an array, find a peak element(print anyone, if many are found). A peak element is one such that it is either greater than or equal to its neighbours. For the first and last element, it is enough to look at its only one neighbour.

Examples:

Example 1:
Input:
 arr = {3, 5, 4, 1, 1}

Output: Peak Element is 5
Explanation:
 3 and 4 are lesser than 5, therefore 5 is a peak element (1 is also a peak element).

Example 2:
Input: arr = {2,6,3,7,8,9}
Output: Peak element is 6
Explanation: 2 and 3 are lesser than 6, therefore 6 is a peak element (9 is also a peak element)

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution:

Intuition:

We can just look at each and every element and compare the neighbors.

Approach:

This is a brute force approach. We traverse each element and check whether it is greater than or equal to its neighbours.
If we find one, we return it.
Else we move on.

Code:

C++ Code

#include<iostream>

using namespace std;

int peakEleBruteForce(int arr[], int n) {
  if (arr[0] >= arr[1])
    return arr[0];

  for (int i = 1; i < n - 1; i++)
    if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1])
      return arr[i];

  return arr[n - 1];
}

int main() {

  int arr[] = {3, 5, 4, 1, 1};
  int n = sizeof(arr) / sizeof(arr[0]);

  cout << "Peak Element is " << peakEleBruteForce(arr, n);

  return 0;
}

Output: Peak Element is 5

Time Complexity: O(n), we traverse the whole array once.

Space Complexity: O(1), we are not using any extra space.

Java Code

import java.util.*;

public class Solution {

  public static void main(String[] args) {
    int[] arr = {3, 5, 4, 1, 1};
    int n = arr.length;

    System.out.println("Peak Element is " + peakEleBruteForce(arr, n));
  }

  public static int peakEleBruteForce(int[] arr, int n) {

    if (arr[0] >= arr[1])
      return arr[0];

    for (int i = 1; i < n - 1; i++)
      if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1])
        return arr[i];

    return arr[n - 1];
  }

}

Output: Peak Element is 5

Time Complexity: O(n), we traverse the whole array once.

Space Complexity: O(1), we are not using any extra space.

Solution 2:

Intuition:

Let’s consider 3 numbers as variables A, B, C. At any chance, 3 elements can be the same, or one element will be at least greater than its neighbour(it can be anyone), all 3 elements can’t be smaller than the other one(peak element’s property always holds).
Let’s consider B >= A, if B >= C, B is a peak. Let’s be pessimistic and consider C > B, now if C is a corner element, then C is a peak. If not, the whole intuition comes again.
The point is, we cannot have an array without a peak element. If we follow a greater element, then for sure we will reach a peak element.

Approach:

So we are going to use binary search. As usual we find a middle element and if it is a peak, then we are done.
If not we follow a greater element. That is we shrink the binary search to one half. To be precise, if the left element is a greater one, we then do binary search only on the left half.
Else(the right element must be a greater one), we search on the right half.
Ultimately, we’ll end up with one of the peaks.

Code:

C++ Code

#include<iostream>

using namespace std;

int peakEleOptimal(int arr[], int n) {
  int start = 0, end = n - 1;

  while (start < end) {
    int mid = (start + end) / 2;

    if (mid == 0)
      return arr[0] >= arr[1] ? arr[0] : arr[1];

    if (mid == n - 1)
      return arr[n - 1] >= arr[n - 2] ? arr[n - 1] : arr[n - 2];

    //Cheking whether peak ele is in mid position
    if (arr[mid] >= arr[mid - 1] && arr[mid] >= arr[mid + 1])
      return arr[mid];

    //If left ele is greater then ignore 2nd half of the elements
    if (arr[mid] < arr[mid - 1])
      end = mid - 1;

    //Else ignore first half of the elements
    else
      start = mid + 1;
  }

  return arr[start];
}

int main() {

  int arr[] = {3, 5, 4, 1, 1};
  int n = sizeof(arr) / sizeof(arr[0]);

  cout << "Peak Element is " << peakEleOptimal(arr, n);

  return 0;
}

Output: Peak Element is 5

Time Complexity: O(log(n)), at every time we shrink the search space to half resulting in log(n) time complexity.

Space Complexity: O(1), we are not using any extra space.

Java Code

import java.util.*;

public class Solution {

  public static void main(String[] args) {
    int[] arr = {3, 5, 4, 1, 1};
    int n = arr.length;

    System.out.println("Peak Element is " + peakEleOptimal(arr, n));
  }

  public static int peakEleOptimal(int[] arr, int n) {
    int start = 0, end = n - 1;

    while (start < end) {
      int mid = (start + end) / 2;

      if (mid == 0)
        return arr[0] >= arr[1] ? arr[0] : arr[1];

      if (mid == n - 1)
        return arr[n - 1] >= arr[n - 2] ? arr[n - 1] : arr[n - 2];

      //Cheking whether peak ele is in mid position
      if (arr[mid] >= arr[mid - 1] && arr[mid] >= arr[mid + 1])
        return arr[mid];

      //If left ele is greater then ignore 2nd half of the elements
      if (arr[mid] < arr[mid - 1])
        end = mid - 1;

      //Else ignore first half of the elements
      else
        start = mid + 1;
    }

    return arr[start];

  }

}

Output: Peak Element is 5

Time Complexity: O(log(n)), at every time we shrink the search space to half resulting in log(n) time complexity.

Space Complexity: O(1), we are not using any extra space.

Special thanks to Prathap P for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article