Skip to main content
Talentd

Find Peak Element - Solution & Explanation

MediumArrayBinary Search19 min readAsked at: Amazon, Microsoft, Apple +27
Practice this problem

Problem Statement

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

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

 

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

 

Constraints:

  • 1 <= nums.length <= 1000
  • -231 <= nums[i] <= 231 - 1
  • nums[i] != nums[i + 1] for all valid i.

Approach Overview

Problem Overview: You are given an integer array where a peak element is strictly greater than its neighbors. The task is to return the index of any peak element. The array may contain multiple peaks, and you can return any valid one. The challenge is to do better than scanning the entire array.

The problem sits at the intersection of array traversal and binary search. The key observation: if an element is smaller than its right neighbor, a peak must exist on the right side. If it is smaller than the left neighbor, a peak must exist on the left side. This property allows logarithmic search.

Approach 1: Linear Scan (Simpler but Not Optimal) (Time: O(n), Space: O(1))

The most direct solution iterates through the array and checks each element against its neighbors. For index i, verify whether nums[i] > nums[i-1] and nums[i] > nums[i+1]. Edge elements only need one comparison because the array boundaries are treated as negative infinity.

This approach performs a single pass through the array. The first element greater than its next neighbor or the first descending point guarantees a peak. Although the logic is simple and easy to implement, it requires examining up to all n elements, resulting in O(n) time complexity and O(1) space.

Approach 2: Binary Search Approach (Time: O(log n), Space: O(1))

The optimal solution uses binary search by analyzing the slope between adjacent elements. Pick a midpoint mid and compare nums[mid] with nums[mid + 1]. If the right neighbor is larger, the array is ascending at that point, so a peak must exist in the right half. Otherwise, a peak exists in the left half including mid.

This works because any increasing slope eventually leads to a peak, and any decreasing slope already passed one. Each comparison eliminates half of the search space. The algorithm continues shrinking the range until left == right, which points to a peak index.

This approach never needs extra memory and performs at most log2(n) iterations, giving O(log n) time and O(1) space. It demonstrates how binary search can work on unsorted arrays when a structural property (like slope direction) guarantees a solution.

Recommended for interviews: Interviewers typically expect the binary search solution. The linear scan shows you understand the peak definition, but the O(log n) approach proves you can recognize patterns that allow binary search without a fully sorted array. Explaining the slope insight clearly is usually the key step during interviews.

Approach 1: Binary Search Approach

The binary search approach is used to achieve the O(log n) time complexity. Binary search leverages the idea that if an element is not a peak and is less than its right neighbor, then a peak must exist on the right half of the array. Similarly, if it is less than its left neighbor, a peak must exist on the left half of the array. Thus, we keep narrowing down the search window until we find a peak.

This C code performs a binary search on the array 'nums'. We start from the whole array and keep reducing the search space. If nums[mid] is greater than nums[mid+1], we search in the left half since a peak might be possible on the left. Otherwise, we search in the right half. This continues until 'left' equals 'right' and we find the peak.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n), Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Linear Scan (Simpler but Not Optimal)

Though not adhering to the O(log n) requirement, a linear scan is straightforward. It involves checking each element to see if it is a peak element, which can serve as a quick solution, but not fulfilling the constraints in a theoretical context. Practically, it can be used in scenarios where constraints are more relaxed or strictly linear approaches are preferred.

In this approach, we first handle edge cases for the start and end of the array. Then, we iterate through the array to find the first element greater than its neighbors. While the time complexity is O(n), it provides a straightforward implementation.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Binary Search

We define the left boundary of binary search as left=0 and the right boundary as right=n-1, where n is the length of the array. In each step of binary search, we find the middle element mid of the current interval, and compare the values of mid and its right neighbor mid+1:

  • If the value of mid is greater than the value of mid+1, there exists a peak element on the left side, and we update the right boundary right to mid.
  • Otherwise, there exists a peak element on the right side, and we update the left boundary left to mid+1.
  • Finally, when the left boundary left is equal to the right boundary right, we have found the peak element of the array.

The time complexity is O(log n), where n is the length of the array nums. Each step of binary search can reduce the search interval by half, so the time complexity is O(log n). The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search Approach

Time Complexity: O(log n), Space Complexity: O(1)

Linear Scan (Simpler but Not Optimal)

Time Complexity: O(n), Space Complexity: O(1)

Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear ScanO(n)O(1)When simplicity matters or when introducing the concept before optimizing
Binary SearchO(log n)O(1)Preferred for interviews and large arrays where logarithmic search is expected

Video Solution

BS-9. Find Peak Element • take U forward • 467,984 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Peak Element easy or hard?
Find Peak Element is generally considered a medium-level problem. The brute force idea is straightforward, but recognizing that binary search works on an unsorted array using slope comparison is the key insight.
How to solve Find Peak Element in O(n)?
Use a linear scan through the array and compare each element with its neighbors. If nums[i] is greater than both adjacent elements, it is a peak. This requires checking each element once, leading to O(n) time and O(1) space.
Find Peak Element Python or Java solution?
Both Python and Java implementations typically use the binary search pattern with two pointers (left and right). Each iteration checks nums[mid] against nums[mid+1] to decide which half to search next, achieving O(log n) time.
What is the best approach for Find Peak Element?
Binary search is the best approach because it reduces the search space by half each step. By comparing nums[mid] with nums[mid+1], you determine which side must contain a peak. This results in O(log n) time complexity and O(1) extra space.
What data structure is used in Find Peak Element?
The problem primarily uses arrays. The optimal algorithm applies binary search logic directly on the array indices without additional data structures, keeping space complexity at O(1).
What is the time complexity of Find Peak Element?
The optimal binary search solution runs in O(log n) time and O(1) space. A simpler linear scan approach runs in O(n) time with constant space. Most interviewers expect the logarithmic solution.
Is Find Peak Element asked at Google, Amazon, or Meta?
Find Peak Element is a common binary search interview problem and has appeared in interviews at companies like Google, Amazon, and Meta. It tests the ability to apply binary search to problems that are not strictly sorted.

Ready to solve this problem?

Practice Find Peak Element with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Hills and Valleys in an Array

Next

Find a Peak Element II