Algorithms for Coding Interviews in C++/

...

/

Solution: Peak Element

Solution: Peak Element

This review discusses the solution of the Peak Element Challenge in detail.

We'll cover the following...

Solution #1: Brute Force

One simple way to solve this problem is to start from the beginning, compare each element with its neighbors, and just return the peak element wherever you find it in the array.

Press + to interact
#include<iostream>
using namespace std;
/* Function to find the peak element in the array */
int findPeak(int arr[], int n){
  if(n==1)     // Handling the edge case (if the array is of size 1)
    return -1;
  for(int i = 1; i<n-1; i++){
    if(arr[i] >= arr[i-1] && arr[i] >= arr[i+1])
      return i;
  }
  if(arr[0] >= arr[1])
    return 0;
    
  if(arr[n-1] >= arr[n-2])
    return n-1;
}
/* Driver program to check above functions */
int main() {
  int arr[] = {7,11,22,13,4,0};
  int x = sizeof(arr);
  int y = sizeof(arr[0]);
  int arrSize = x / y;
  cout << "One peak point index is: " << findPeak(arr, arrSize) << endl;
}

There must always be one peak element in an array with distinct elements, but it’s possible that the array is sorted in ascending order like this:

In this case, the peak element is at the end of the array.

Time Complexity

This solution gives us a worst-case time complexity of O(n)O(n). Can we do better?


Solution #2: Efficient

Using divide and conquer, we can speed up the whole process. Have a look at the solution given below:

Press + to interact
#include <iostream>
using namespace std;
// The function below is based on the recursive binary search algorithm
// It returns the index of the peak element in the given array
int findPeakRecursive(int low, int high, int size, int array[]) {
  // Just as in binary search, we will first find the middle element 
  int middle = low + (high - low) / 2;
  // If neighbors of the middle element exist, compare them with the element 
  if ((middle == size - 1 || array[middle + 1] <= array[middle]) &&
  		(middle == 0 || array[middle - 1] <= array[middle]))
  		return middle;
  // If the left neighbor of the middle element is greater
  // The peak element must be in the left subarray
  else if (array[middle - 1] > array[middle] && middle > 0)
  		return findPeakRecursive(low, (middle - 1), size, array);
  // If the right neighbor of the middle element is greater
  // The peak element must be in the right subarray
  else 
    	return findPeakRecursive((middle + 1), high, size, array);
}
// Wrapper to call the recursive findPeakRecursive() 
int findPeak(int arr[], int n) {
  return findPeakRecursive(0, n - 1, n, arr);
}
/* Driver program to check above functions */
int main() {
  int arr[] = {7,11,22,13,4,0};
  int x = sizeof(arr);
  int y = sizeof(arr[0]);
  int arrSize = x / y;
  cout << "One peak point index is: " << findPeak(arr, arrSize) << endl;
}

Start with the middle element of the array (Line 8)

  • Compare the element with its neighbors.
    • If the middle element is not smaller than any of its neighbors, then we return it. (Line 13)
    • If the middle element is smaller than its left neighbor, then there is always a peak in the left half. (Line 18)
    • If the middle element is smaller than its right neighbor, then there is always a
...