Find Peak Element in Array

Given an array of integers, your task is to find the index of any peak element in the array.

A peak element is defined as an element that is not smaller than its neighbors. For the edge elements (first or last), we only compare with their one existing neighbor.

If there are multiple peaks, return the index of any one of them. If the array is empty, return -1.

Understanding the Problem

A peak element in an array is one that is not smaller than its neighbors. That means at index i, the value arr[i] is a peak if it satisfies one of the following conditions:

• It is the first element and arr[0] ≥ arr[1]
• It is the last element and arr[n-1] ≥ arr[n-2]
• It is in the middle and arr[i] ≥ arr[i-1] and arr[i] ≥ arr[i+1]

The goal is to efficiently find any one peak. Note: multiple peaks may exist, but we only need to find one of them.

Step-by-Step Solution with Example

Step 1: Start with an example

Let’s take the array [1, 3, 20, 4, 1, 0]. Visually, it looks like:

Index:   0   1   2   3   4   5
Value:   1   3  20   4   1   0

Here, 20 at index 2 is clearly greater than both 3 and 4, so it's a peak.

Step 2: Use Binary Search for Efficiency

We don’t need to linearly scan the entire array. A binary search approach gives us O(log n) efficiency:

1. Set low = 0, high = n - 1
2. While low ≤ high:
   • Compute mid = (low + high) / 2
   • Check if arr[mid] is a peak
   • If arr[mid] < arr[mid + 1], search the right half
   • Else if arr[mid] < arr[mid - 1], search the left half
   • Else return mid as the peak

Step 3: Apply Binary Search to Our Example

• Initial range: low = 0, high = 5
• mid = 2 → arr[2] = 20
• Check neighbors: arr[1] = 3 and arr[3] = 4
• 20 ≥ 3 and 20 ≥ 4 → it's a peak!

So, index 2 is returned. No further searching is needed.

Edge Cases

Case 1: Array has only one element

Example: [7] — This is automatically a peak as it has no neighbors.

Case 2: Peak is at the beginning

Example: [10, 5, 2] — Here, 10 ≥ 5, so index 0 is a peak.

Case 3: Peak is at the end

Example: [1, 2, 4] — 4 ≥ 2, so index 2 is a peak.

Case 4: Empty array

If arr.length == 0, there's no element to evaluate. We should return -1 to indicate no peak.

Finally

By understanding the definition of a peak and applying a smart binary search strategy, we can find any one peak efficiently in O(log n) time. Always check edge cases like an empty array, a single-element array, or peaks at the boundaries to make your solution robust.

And remember: we don’t need to find the highest peak — just any one that satisfies the peak condition!

1. Initialize low = 0 and high = n - 1.
2. While low ≤ high, calculate mid = (low + high) / 2.
3. Check if arr[mid] is a peak:
• It is greater than or equal to its neighbors (consider edge conditions).
4. If it is a peak, return mid.
5. If arr[mid] < arr[mid + 1], move to right half: low = mid + 1.
6. Else, move to left half: high = mid - 1.

#include <stdio.h>

int findPeakElement(int arr[], int n) {
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        int leftOK = (mid == 0 || arr[mid] >= arr[mid - 1]);
        int rightOK = (mid == n - 1 || arr[mid] >= arr[mid + 1]);

        if (leftOK && rightOK) return mid;
        else if (mid < n - 1 && arr[mid] < arr[mid + 1]) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main() {
    int arr[] = {1, 3, 20, 4, 1, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    int peakIndex = findPeakElement(arr, n);
    printf("Peak Index: %d, Peak Element: %d\n", peakIndex, arr[peakIndex]);
    return 0;
}

#include <iostream>
using namespace std;

int findPeakElement(int arr[], int n) {
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        bool leftOK = (mid == 0 || arr[mid] >= arr[mid - 1]);
        bool rightOK = (mid == n - 1 || arr[mid] >= arr[mid + 1]);

        if (leftOK && rightOK) return mid;
        else if (mid < n - 1 && arr[mid] < arr[mid + 1]) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main() {
    int arr[] = {1, 3, 20, 4, 1, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    int peakIndex = findPeakElement(arr, n);
    cout << "Peak Index: " << peakIndex << ", Peak Element: " << arr[peakIndex] << endl;
    return 0;
}

def find_peak_element(arr):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = low + (high - low) // 2
        leftOK = (mid == 0 or arr[mid] >= arr[mid - 1])
        rightOK = (mid == len(arr) - 1 or arr[mid] >= arr[mid + 1])

        if leftOK and rightOK:
            return mid
        elif mid < len(arr) - 1 and arr[mid] < arr[mid + 1]:
            low = mid + 1
        else:
            high = mid - 1
    return -1

arr = [1, 3, 20, 4, 1, 0]
peak_index = find_peak_element(arr)
print(f"Peak Index: {peak_index}, Peak Element: {arr[peak_index]}")

public class PeakElementFinder {
  public static int findPeakElement(int[] arr) {
    int low = 0, high = arr.length - 1;

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

      boolean leftOK = (mid == 0 || arr[mid] >= arr[mid - 1]);
      boolean rightOK = (mid == arr.length - 1 || arr[mid] >= arr[mid + 1]);

      if (leftOK && rightOK) return mid;
      else if (mid < arr.length - 1 && arr[mid] < arr[mid + 1]) low = mid + 1;
      else high = mid - 1;
    }
    return -1;
  }

  public static void main(String[] args) {
    int[] arr = {1, 3, 20, 4, 1, 0};
    int peakIndex = findPeakElement(arr);
    System.out.println("Peak Index: " + peakIndex + ", Peak Element: " + arr[peakIndex]);
  }
}

function findPeakElement(arr) {
  let low = 0, high = arr.length - 1;

  while (low <= high) {
    let mid = Math.floor(low + (high - low) / 2);
    let leftOK = (mid === 0 || arr[mid] >= arr[mid - 1]);
    let rightOK = (mid === arr.length - 1 || arr[mid] >= arr[mid + 1]);

    if (leftOK && rightOK) return mid;
    else if (mid < arr.length - 1 && arr[mid] < arr[mid + 1]) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

const arr = [1, 3, 20, 4, 1, 0];
const peakIndex = findPeakElement(arr);
console.log(`Peak Index: ${peakIndex}, Peak Element: ${arr[peakIndex]}`);

package main

import (
  "fmt"
)

func findPeakElement(arr []int) int {
  low, high := 0, len(arr)-1

  for low <= high {
    mid := low + (high-low)/2
    leftOK := mid == 0 || arr[mid] >= arr[mid-1]
    rightOK := mid == len(arr)-1 || arr[mid] >= arr[mid+1]

    if leftOK && rightOK {
      return mid
    } else if mid < len(arr)-1 && arr[mid] < arr[mid+1] {
      low = mid + 1
    } else {
      high = mid - 1
    }
  }
  return -1
}

func main() {
  arr := []int{1, 3, 20, 4, 1, 0}
  peakIndex := findPeakElement(arr)
  fmt.Printf("Peak Index: %d, Peak Element: %d\n", peakIndex, arr[peakIndex])
}

fn find_peak_element(arr: &[i32]) -> usize {
    let (mut low, mut high) = (0, arr.len() - 1);

    while low <= high {
        let mid = low + (high - low) / 2;
        let left_ok = mid == 0 || arr[mid] >= arr[mid - 1];
        let right_ok = mid == arr.len() - 1 || arr[mid] >= arr[mid + 1];

        if left_ok && right_ok {
            return mid;
        } else if mid < arr.len() - 1 && arr[mid] < arr[mid + 1] {
            low = mid + 1;
        } else {
            if mid == 0 { break; }
            high = mid - 1;
        }
    }
    0
}

fn main() {
    let arr = [1, 3, 20, 4, 1, 0];
    let peak_index = find_peak_element(&arr);
    println!("Peak Index: {}, Peak Element: {}", peak_index, arr[peak_index]);
}

fun findPeakElement(arr: IntArray): Int {
    var low = 0
    var high = arr.size - 1

    while (low <= high) {
        val mid = low + (high - low) / 2
        val leftOK = (mid == 0 || arr[mid] >= arr[mid - 1])
        val rightOK = (mid == arr.size - 1 || arr[mid] >= arr[mid + 1])

        if (leftOK && rightOK) return mid
        else if (mid < arr.size - 1 && arr[mid] < arr[mid + 1]) low = mid + 1
        else high = mid - 1
    }
    return -1
}

fun main() {
    val arr = intArrayOf(1, 3, 20, 4, 1, 0)
    val peakIndex = findPeakElement(arr)
    println("Peak Index: $peakIndex, Peak Element: ${arr[peakIndex]}")
}

func findPeakElement(_ arr: [Int]) -> Int {
    var low = 0
    var high = arr.count - 1

    while low <= high {
        let mid = low + (high - low) / 2
        let leftOK = (mid == 0 || arr[mid] >= arr[mid - 1])
        let rightOK = (mid == arr.count - 1 || arr[mid] >= arr[mid + 1])

        if leftOK && rightOK {
            return mid
        } else if mid < arr.count - 1 && arr[mid] < arr[mid + 1] {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return -1
}

let arr = [1, 3, 20, 4, 1, 0]
let peakIndex = findPeakElement(arr)
print("Peak Index: \(peakIndex), Peak Element: \(arr[peakIndex])")

function findPeakElement(arr: number[]): number {
  let low = 0, high = arr.length - 1;

  while (low <= high) {
    const mid = Math.floor(low + (high - low) / 2);
    const leftOK = (mid === 0 || arr[mid] >= arr[mid - 1]);
    const rightOK = (mid === arr.length - 1 || arr[mid] >= arr[mid + 1]);

    if (leftOK && rightOK) return mid;
    else if (mid < arr.length - 1 && arr[mid] < arr[mid + 1]) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

const arr: number[] = [1, 3, 20, 4, 1, 0];
const peakIndex = findPeakElement(arr);
console.log(`Peak Index: ${peakIndex}, Peak Element: ${arr[peakIndex]}`);

Time complexity

Space complexity

O(1)

The algorithm uses constant extra space regardless of input size.