English flagEnglish  
CLOSE

Suggested:

Problem Statement

Given an array arr of integers. A peak element is defined as an element greater than both of its neighbors. Formally, if arr[i] is the peak element, arr[i-1] < arr[i] and arr[i+1] < arr[i].

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.

Note: For the first element, the previous element should be considered as negative infinity as well as the last element, the next element should be considered as negative infinity.

Examples

Example 1:

Input: arr = [1, 2, 3, 4, 5, 6, 7, 8, 5, 1]
Output: 7

Explanation: In this example, there is only 1 peak
that is at index 7.
Example 2:

Input: arr = [1, 2, 1, 3, 5, 6, 4]
Output: 1

Explanation: In this example, there are 2 peak that is at indices 1 and 5. We can consider any of them.
Example 3:

Input: arr = [-2, -1, 3, 4, 5]
Output: 4

Explanation: The very last element is the peak which is 5.

Different Approaches

1️⃣ Brute Force (Linear Approach)

Intuition:

A simple approach involves iterating through the array and checking the adjacent elements of the current element, if the adjacent elements are smaller than the current element then the current element will be the peak element.

Approach:

  • Edge cases:
    • If n == 1(n is size of the array): If the size of the array is one, then the only element present will the peak element. So, return its index.
    • If the current index is 0: While checking for 0th index, it will have only one adjacent element, so just check for the element at 1st index, as -1 index will be invalid index.
    • If the current index is (n-1): The last index will also have only one adjacent element as the nth index will be invalid(for 0 based indexing). So just check (n-2)th index.
  • Start traversing the array and for every index, check its adjacent index.
  • If an element is greater than its adjacent elements, return the index of that element.
  • If no such element is found, return -1 as an answer.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find the peak element in the array
    int findPeakElement(vector<int> &arr) {
        // Size of array
        int n = arr.size();
        
        /* Iterate through the array
        to find the peak element */
        for (int i = 0; i < n; i++) {
            
            // Check if arr[i] is a peak
            if ((i == 0 || arr[i - 1] < arr[i]) && (i == n - 1 || arr[i] > arr[i + 1])) {
                
                //Return the index of peak element
                return i; 
            }
        }
        /* Return -1 if no peak element
        found (dummy return) */
        return -1; 
    }
};

int main() {
    vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 5, 1};
    
    // Create an instance of the Solution class
    Solution sol;
    
    int ans = sol.findPeakElement(arr);
    
    // Output the result
    cout << "The peak is at index: " << ans << "\n";
    
    return 0;
}
OR very simple:
#include <vector>
#include <iostream>
#include <climits>
using namespace std;

// Function to find the index of a peak element
int peakElement(vector<int>& arr) {
    int n = arr.size();

    // Handle edge case: Array with only one element
    if (n == 1) return 0;

    // Loop through each element in the array
    for (int i = 0; i < n; i++) {
        int currentElm = arr[i]; // Current element
        int previousElm = (i == 0) ? INT_MIN : arr[i - 1]; // Handle boundary for the first element
        int nextElm = (i == n - 1) ? INT_MIN : arr[i + 1]; // Handle boundary for the last element

        // Check if the current element is greater than both neighbors
        if (currentElm > previousElm && currentElm > nextElm) {
            return i; // Return the index of the peak element
        }
    }

    // If no peak element is found (not possible in a valid input), return -1
    return -1;
}

int main() {
    // Example test cases to verify all edge cases
    vector<vector<int>> testCases = {
        {1},              // Single element
        {1, 2, 3, 4, 5},  // Increasing sequence
        {5, 4, 3, 2, 1},  // Decreasing sequence
        {1, 3, 20, 4, 1}, // Peak in the middle
        {10, 20},         // Two elements
        {20, 10}          // Two elements, reversed
    };

    // Run the function for each test case and print results
    for (auto& arr : testCases) {
        int peakIndex = peakElement(arr);
        cout << "Array: ";
        for (int num : arr) cout << num << " ";
        cout << "\nPeak Element Index: " << peakIndex << "\n\n";
    }

    return 0;
}

Complexity Analysis:

  • Time Complexity: O(N), where N is size of the array.
  • Space Complexity: O(1)

2️⃣ Binary Search

Intuition:

Here, the idea is to use binary search algorithm to optimize the brute-force solution where linear search was being used. For each element (mid), we check if it is greater than its previous and next elements. If so, mid is identified as a peak element. Alternatively, if mid is smaller than its previous element, a peak must exist on the left side, so the right half is eliminated. Similarly, if mid is less than the next element, a peak must exist on the right side, so the left half is eliminated. This approach trims down the search space in each iteration, thereby enhancing the time complexity.

Approach:

  • Edge cases:
    • If n == 1(n is size of the array): If the size of the array is one, then the only element present will the peak element. So, return its index.
    • If the current index is 0: While checking for 0th index, it will have only one adjacent element, so just check for the element at 1st index, as -1 index will be invalid index.
    • If the current index is (n-1): The last index will also have only one adjacent element as the nth index will be invalid(for 0 based indexing). So just check (n-2)th index.
  • Initialize two pointers: low to 1 and high to n-2(n is the size of the array), as the 0th and (n-1)th index has already been dealt with in the edge cases. This will describe our search space.
  • Intialize a while loop which will run till low is less than or equal to high. Now, inside a loop, calculate the value of ‘mid’ using the following formula: mid = (low+high) // 2 ( ‘//’ refers to integer division)
  • Check if element at [mid] is the peak element, if yes, return the value of 'mid' as the peak element is found at index 'mid'.
  • If element at [mid] greater than element at [mid-1], this means we are in the left half and eliminate it as the peak element appears on the right.
  • Otherwise, we are in the right half and eliminate it as the peak element appears on the left. This case also handles the case for the index ‘mid’ being a common point of a decreasing and increasing sequence. It will consider the left peak and eliminate the right peak.
  • At last if no peak element is found return -1 as an answer.

Dry Run:

Initialization:
      +---+---+---+---+---+---+---+---+---+---+
arr = | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 5 | 1 |
      +---+---+---+---+---+---+---+---+---+---+
        0   1   2   3   4   5   6   7   8   9
Start Iterating:
We would skip the first and last index, as they
are handled in the edges cases.

left = 1
right = arr.size() - 2 = 8
mid = left + (right - left) / 2
    = 1 + (8 - 1)/2
    = 1 + 7/2
    = 1 + 3
    = 4
      +---+---+---+---+---+---+---+---+---+---+
arr = | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 5 | 1 |
      +---+---+---+---+---+---+---+---+---+---+
        0   1   2   3   4   5   6   7   8   9
            ^           ^               ^
            |           |               |
           left        mid             right

     Do the mid is greater than its neighbors
         False
     
     Check if previous of mid is greater than mid
         False
     Else next of mid is greater than mid
         True
         Based on it we can say that there
         will be a peak element in the right part
         GO GO right
         set left = mid + 1
             left = 4 + 1
                  = 5
left = 5
right = arr.size() - 2 = 8
mid = left + (right - left) / 2
    = 5 + (8 - 5)/2
    = 5 + 3/2
    = 5 + 1
    = 6
      +---+---+---+---+---+---+---+---+---+---+
arr = | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 5 | 1 |
      +---+---+---+---+---+---+---+---+---+---+
        0   1   2   3   4   5   6   7   8   9
                            ^   ^       ^
                            |   |       |
                           left mid    right

     Do the mid is greater than its neighbors
         False
     
     Check if previous of mid is greater than mid
         False
     Else next of mid is greater than mid
         True
         Based on it we can say that there
         will be a peak element in the right part
         GO GO right
         set left = mid + 1
             left = 6 + 1
                  = 7
left = 7
right = arr.size() - 2 = 8
mid = left + (right - left) / 2
    = 7 + (8 - 7)/2
    = 7 + 1/2
    = 7 + 1
    = 7
      +---+---+---+---+---+---+---+---+---+---+
arr = | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 5 | 1 |
      +---+---+---+---+---+---+---+---+---+---+
        0   1   2   3   4   5   6   7   8   9
                                    ^   ^
                                    |   |
                                   left right
                                   mid

     Do the mid is greater than its neighbors
         True
         As 8 is greater than 7 and 5
         
         We have the peak element 8, return
         its index 7.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find the peak element in the array
    int findPeakElement(vector<int> &arr) {
        // Size of array
        int n = arr.size();
        
        // Edge cases:
        if (n == 1) return 0;
        if (arr[0] > arr[1]) return 0;
        if (arr[n - 1] > arr[n - 2]) return n - 1;

        int low = 1, high = n - 2;
        while (low <= high) {
            int mid = (low + high) / 2;

            //If arr[mid] is the peak
            if (arr[mid - 1] < arr[mid] && arr[mid] > arr[mid + 1])
                return mid;

            // If we are in the left
            if (arr[mid] > arr[mid - 1]) low = mid + 1;

            /* If we are in the right
            Or, arr[mid] is a common point*/
            else high = mid - 1;
        }
        /* Return -1 if no peak element
        found (dummy return) */
        return -1; 
    }
};

int main() {
    vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 5, 1};
    
    // Create an instance of the Solution class
    Solution sol;
    
    int ans = sol.findPeakElement(arr);
    
    // Output the result
    cout << "The peak is at index: " << ans << "\n";
    
    return 0;
}
int findPeakElement(vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;

        // Compare mid with mid + 1
        if (nums[mid] > nums[mid + 1]) {
            // Peak is on the left (including mid)
            right = mid;
        } else {
            // Peak is on the right (excluding mid)
            left = mid + 1;
        }
    }
    
    return left; // or return right, as left == right at the peak
}

Complexity Analysis:

  • Time Complexity: O(logN), N is size of the given array. As binary search is being used to find the minimum.
  • Space Complexity: As no additional space is used, so the Space Complexity is O(1).

Your experience on this site will be improved by allowing cookies Cookie Policy