Find Peak Element

Problem Statement

A peak element is an element that is strictly greater than its neighbors. Given an integer array nums, find a peak element, and return its index. If the array has multiple peaks, return the index to any one of them.

You may imagine that nums[-1] = nums[n] = -infinity.

You must write an algorithm that runs in O(log n) time.

What to notice first

• A peak must be greater than both neighbors (or treat out-of-bounds as negative infinity).
• There is always at least one peak in the array due to the constraints.
• Comparing mid with its right neighbor tells us which direction the peak is.

Examples

Input	Output	Explanation
[1, 2, 3, 1]	2	3 is a peak (3 > 2 and 3 > 1)
[1, 2, 1]	1	2 is a peak (2 > 1 and 2 > 1)
[1]	0	Single element is always a peak
[6, 5, 4, 3, 2, 3, 4]	0	6 is a peak (6 > 5)

Constraints

• 1 <= nums.length <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• nums[i] != nums[i + 1] for all valid i

Real-World Applications

Where this pattern appears

• Stock price analysis — finding local maxima in price history to identify peaks.
• Signal processing — detecting peaks in time-series data (audio, seismic).
• Terrain mapping — finding high points in elevation data.
• Network traffic — identifying peak load times in bandwidth usage.

Complexity Comparison

Approach	Time	Space	Best When
Binary Search	O(log n)	O(1)	Large arrays, O(log n) required by constraints
Linear Scan	O(n)	O(1)	Small arrays, simplicity preferred

Which approach should you learn first?

• Pick Binary Search to meet the O(log n) constraint and understand the pattern.
• Pick Linear Scan to understand how peaks work conceptually.

Required Time

Binary Search

O(log n) time · O(1) space

Simpler Logic

Linear Scan

O(n) time · O(1) space

Approach 1: Binary Search (Recommended)

★ Recommended

Compare nums[mid] with nums[mid + 1]. If mid is less than its right neighbor, the peak must be on the right (since there’s an increasing trend). Otherwise, search left. This guarantees finding a peak.

⏱ Time O(log n) Halve search space each iteration 💾 Space O(1) Only pointers

Step-by-step Example

Input: nums = [1, 2, 3, 1]

Step	left	right	mid	nums[mid]	nums[mid+1]	nums[mid] < nums[mid+1]?	Action
1	0	3	1	2	3	Yes	left = 2
2	2	3	2	3	1	No	right = 2
3	2	2	—	—	—	—	Return 2 ✓

Pseudocode

function findPeakElement(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) / 2
        if nums[mid] < nums[mid + 1]:
            left = mid + 1  // Peak on right
        else:
            right = mid  // Peak on left or at mid
    return left

Solution Code

Python

find_peak_element_binary_search.py

"""
#162 Find Peak Element - Binary Search Approach
Time: O(log n), Space: O(1)

A peak element is an element that is strictly greater than its neighbors.
The array may contain multiple peaks; return index of any one.
"""


class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        """
        Binary search by comparing mid with its right neighbor.
        If nums[mid] < nums[mid+1], peak is on the right.
        Otherwise, peak is on the left or at mid.
        """
        left, right = 0, len(nums) - 1

        while left < right:
            mid = left + (right - left) // 2

            # If mid is less than its right neighbor, peak is on right
            if nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                # Peak is on left or at mid
                right = mid

        return left


# Test cases
if __name__ == "__main__":
    sol = Solution()

    assert sol.findPeakElement([1, 2, 3, 1]) == 2
    assert sol.findPeakElement([1, 2, 1]) == 1
    assert sol.findPeakElement([1]) == 0
    assert sol.findPeakElement([6, 5, 4, 3, 2, 3, 4]) == 0
    assert sol.findPeakElement([1, 2, 3, 4, 5]) == 4

    print("All test cases passed!")

C++

find_peak_element_binary_search.cpp

#include <vector>
using namespace std;

/*
#162 Find Peak Element - Binary Search Approach
Time: O(log n), Space: O(1)

A peak element is an element that is strictly greater than its neighbors.
The array may contain multiple peaks; return index of any one.
*/

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        /*
        Binary search by comparing mid with its right neighbor.
        If nums[mid] < nums[mid+1], peak is on the right.
        Otherwise, peak is on the left or at mid.
        */
        int left = 0, right = nums.size() - 1;

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

            // If mid is less than its right neighbor, peak is on right
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                // Peak is on left or at mid
                right = mid;
            }
        }

        return left;
    }
};

Java

FindPeakElementBinarySearch.java

/*
#162 Find Peak Element - Binary Search Approach
Time: O(log n), Space: O(1)

A peak element is an element that is strictly greater than its neighbors.
The array may contain multiple peaks; return index of any one.
*/

class Solution {
    public int findPeakElement(int[] nums) {
        /*
        Binary search by comparing mid with its right neighbor.
        If nums[mid] < nums[mid+1], peak is on the right.
        Otherwise, peak is on the left or at mid.
        */
        int left = 0, right = nums.length - 1;

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

            // If mid is less than its right neighbor, peak is on right
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                // Peak is on left or at mid
                right = mid;
            }
        }

        return left;
    }
}

JavaScript

find_peak_element_binary_search.js

/**
 * #162 Find Peak Element - Binary Search Approach
 * Time: O(log n), Space: O(1)
 *
 * A peak element is an element that is strictly greater than its neighbors.
 * The array may contain multiple peaks; return index of any one.
 */

class Solution {
    findPeakElement(nums) {
        /**
         * Binary search by comparing mid with its right neighbor.
         * If nums[mid] < nums[mid+1], peak is on the right.
         * Otherwise, peak is on the left or at mid.
         */
        let left = 0, right = nums.length - 1;

        while (left < right) {
            const mid = left + Math.floor((right - left) / 2);

            // If mid is less than its right neighbor, peak is on right
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                // Peak is on left or at mid
                right = mid;
            }
        }

        return left;
    }
}

// Export for CommonJS
module.exports = Solution;

Rust

find_peak_element_binary_search.rs

/*
#162 Find Peak Element - Binary Search Approach
Time: O(log n), Space: O(1)

A peak element is an element that is strictly greater than its neighbors.
The array may contain multiple peaks; return index of any one.
*/

impl Solution {
    pub fn find_peak_element(nums: Vec<i32>) -> i32 {
        /*
        Binary search by comparing mid with its right neighbor.
        If nums[mid] < nums[mid+1], peak is on the right.
        Otherwise, peak is on the left or at mid.
        */
        let mut left = 0i32;
        let mut right = nums.len() as i32 - 1;

        while left < right {
            let mid = left + (right - left) / 2;
            let mid_idx = mid as usize;

            // If mid is less than its right neighbor, peak is on right
            if nums[mid_idx] < nums[mid_idx + 1] {
                left = mid + 1;
            } else {
                // Peak is on left or at mid
                right = mid;
            }
        }

        left
    }
}

Go

find_peak_element_binary_search.go

package main

/*
#162 Find Peak Element - Binary Search Approach
Time: O(log n), Space: O(1)

A peak element is an element that is strictly greater than its neighbors.
The array may contain multiple peaks; return index of any one.
*/

func FindPeakElementBinarySearch(nums []int) int {
  /*
  Binary search by comparing mid with its right neighbor.
  If nums[mid] < nums[mid+1], peak is on the right.
  Otherwise, peak is on the left or at mid.
  */
  left, right := 0, len(nums)-1

  for left < right {
    mid := left + (right-left)/2

    // If mid is less than its right neighbor, peak is on right
    if nums[mid] < nums[mid+1] {
      left = mid + 1
    } else {
      // Peak is on left or at mid
      right = mid
    }
  }

  return left
}

Approach 2: Linear Scan

✓ Simple

Iterate through the array and check if each element is greater than its neighbors. Return the first peak found.

⏱ Time O(n) Full array scan 💾 Space O(1) Only pointers

Step-by-step Example

Input: nums = [1, 2, 3, 1]

i	nums[i]	Left neighbor	Right neighbor	Is peak?	Action
0	1	-∞	2	No (1 < 2)	Continue
1	2	1	3	No (2 < 3)	Continue
2	3	2	1	Yes (3 > 2 && 3 > 1)	Return 2 ✓

Pseudocode

function findPeakElement(nums):
    for i in range(len(nums)):
        isLeft = (i == 0) or (nums[i] > nums[i-1])
        isRight = (i == len(nums)-1) or (nums[i] > nums[i+1])
        if isLeft and isRight:
            return i

Solution Code

Python

find_peak_element_linear_scan.py

"""
#162 Find Peak Element - Linear Scan Approach
Time: O(n), Space: O(1)

Iterate through array and find the first element greater than its neighbors.
"""


class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        """
        Linear scan to find first peak.
        Compare each element with its neighbors.
        """
        for i in range(len(nums)):
            # Check if current element is greater than neighbors
            is_peak = True

            if i > 0 and nums[i] <= nums[i - 1]:
                is_peak = False

            if i < len(nums) - 1 and nums[i] <= nums[i + 1]:
                is_peak = False

            if is_peak:
                return i

        # If no peak found (shouldn't happen given constraints)
        return 0


# Test cases
if __name__ == "__main__":
    sol = Solution()

    assert sol.findPeakElement([1, 2, 3, 1]) == 2
    assert sol.findPeakElement([1, 2, 1]) == 1
    assert sol.findPeakElement([1]) == 0
    assert sol.findPeakElement([6, 5, 4, 3, 2, 3, 4]) == 0
    assert sol.findPeakElement([1, 2, 3, 4, 5]) == 4

    print("All test cases passed!")

C++

find_peak_element_linear_scan.cpp

#include <vector>
using namespace std;

/*
#162 Find Peak Element - Linear Scan Approach
Time: O(n), Space: O(1)

Iterate through array and find the first element greater than its neighbors.
*/

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        /*
        Linear scan to find first peak.
        Compare each element with its neighbors.
        */
        for (int i = 0; i < nums.size(); i++) {
            // Check if current element is greater than neighbors
            bool is_peak = true;

            if (i > 0 && nums[i] <= nums[i - 1]) {
                is_peak = false;
            }

            if (i < nums.size() - 1 && nums[i] <= nums[i + 1]) {
                is_peak = false;
            }

            if (is_peak) {
                return i;
            }
        }

        // If no peak found (shouldn't happen given constraints)
        return 0;
    }
};

Java

FindPeakElementLinearScan.java

/*
#162 Find Peak Element - Linear Scan Approach
Time: O(n), Space: O(1)

Iterate through array and find the first element greater than its neighbors.
*/

class Solution {
    public int findPeakElement(int[] nums) {
        /*
        Linear scan to find first peak.
        Compare each element with its neighbors.
        */
        for (int i = 0; i < nums.length; i++) {
            // Check if current element is greater than neighbors
            boolean isPeak = true;

            if (i > 0 && nums[i] <= nums[i - 1]) {
                isPeak = false;
            }

            if (i < nums.length - 1 && nums[i] <= nums[i + 1]) {
                isPeak = false;
            }

            if (isPeak) {
                return i;
            }
        }

        // If no peak found (shouldn't happen given constraints)
        return 0;
    }
}

JavaScript

find_peak_element_linear_scan.js

/**
 * #162 Find Peak Element - Linear Scan Approach
 * Time: O(n), Space: O(1)
 *
 * Iterate through array and find the first element greater than its neighbors.
 */

class Solution {
    findPeakElement(nums) {
        /**
         * Linear scan to find first peak.
         * Compare each element with its neighbors.
         */
        for (let i = 0; i < nums.length; i++) {
            // Check if current element is greater than neighbors
            let isPeak = true;

            if (i > 0 && nums[i] <= nums[i - 1]) {
                isPeak = false;
            }

            if (i < nums.length - 1 && nums[i] <= nums[i + 1]) {
                isPeak = false;
            }

            if (isPeak) {
                return i;
            }
        }

        // If no peak found (shouldn't happen given constraints)
        return 0;
    }
}

// Export for CommonJS
module.exports = Solution;

Rust

find_peak_element_linear_scan.rs

/*
#162 Find Peak Element - Linear Scan Approach
Time: O(n), Space: O(1)

Iterate through array and find the first element greater than its neighbors.
*/

impl Solution {
    pub fn find_peak_element(nums: Vec<i32>) -> i32 {
        /*
        Linear scan to find first peak.
        Compare each element with its neighbors.
        */
        for i in 0..nums.len() {
            // Check if current element is greater than neighbors
            let mut is_peak = true;

            if i > 0 && nums[i] <= nums[i - 1] {
                is_peak = false;
            }

            if i < nums.len() - 1 && nums[i] <= nums[i + 1] {
                is_peak = false;
            }

            if is_peak {
                return i as i32;
            }
        }

        // If no peak found (shouldn't happen given constraints)
        0
    }
}

Go

find_peak_element_linear_scan.go

package main

/*
#162 Find Peak Element - Linear Scan Approach
Time: O(n), Space: O(1)

Iterate through array and find the first element greater than its neighbors.
*/

func FindPeakElementLinearScan(nums []int) int {
  /*
  Linear scan to find first peak.
  Compare each element with its neighbors.
  */
  for i := 0; i < len(nums); i++ {
    // Check if current element is greater than neighbors
    isPeak := true

    if i > 0 && nums[i] <= nums[i-1] {
      isPeak = false
    }

    if i < len(nums)-1 && nums[i] <= nums[i+1] {
      isPeak = false
    }

    if isPeak {
      return i
    }
  }

  // If no peak found (shouldn't happen given constraints)
  return 0
}

Common mistakes

Watch for these pitfalls

• Forgetting to handle boundary conditions (first and last elements).
• Accessing nums[mid + 1] without checking if it exists in the linear scan.
• Confusing the search direction in binary search (right if increasing, left otherwise).

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

find_peak_element_space_optimized.py

"""
Solution for Find Peak Element
"""

def solve():
    """Implementation for approach 3 of Find Peak Element"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

find_peak_element_space_optimized.cpp

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

// Solution for Find Peak Element
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

FindPeakElementSpaceOptimized.java

/**
 * Solution for Find Peak Element
 * Approach 3
 */
public class FindPeakElementSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

find_peak_element_space_optimized.js

/**
 * Solution for Find Peak Element
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

find_peak_element_space_optimized.rs

/// Solution for Find Peak Element
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

find_peak_element_space_optimized.go

package main

import "fmt"

// Solution for Find Peak Element
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Binary Search ↗ Easy #704
• Search Insert Position ↗ Easy #35
• Search in Rotated Sorted Array ↗ Medium #33
• Find Minimum in Rotated Sorted Array ↗ Medium #153

Interview Tips

Key trade-offs to discuss

• Why binary search required? The problem explicitly asks for O(log n), which tests understanding of the pattern.
• The comparison trick: Comparing mid with mid+1 (instead of mid-1) guarantees moving towards a peak.
• Why it always finds a peak: The strategy ensures we either climb up or stabilize, eventually reaching a peak.
• Edge case insight: Single-element arrays are always peaks due to the -infinity boundary assumption.

← Previous
#161 One Edit Distance Next
#163 Binary Search Tree Iterator →