How do you solve Find Peak Element?

Use a binary search with pointers l and r. At each iteration, compute mid. If nums[mid] < nums[mid+1], the peak lies to the right, so move l to mid+1. Otherwise, the peak lies to the left or at mid, so move r to mid. Continue until l == r, which is the peak index.

Find Peak Element

Q: What is the time complexity of Find Peak Element?

O(log n). Each iteration halves the search space by moving either l or r, resulting in logarithmic time complexity.

Q: What pattern does Find Peak Element use?

The Pattern: Modified Binary Search (Slope-Based Search for Peak) The Heuristic: When searching for a peak or boundary in an array where the property depends on neighbors, compare mid with mid+1 to determine the slope direction and discard the half that cannot contain a peak, guaranteeing logarithmic time.

Medium Modified Binary Search

Problem

Given an integer array nums, return the index of a peak element. A peak element is an element that is strictly greater than its neighbors. You may assume nums[-1] = nums[n] = -∞. The array may contain multiple peaks; return the index to any one of the peaks.

1 ≤ nums.length ≤ 10⁴
−2³¹ ≤ nums[i] ≤ 2³¹ - 1
nums[i] != nums[i + 1] for all valid i

Example

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

Output: 2

The array has a peak at index 2 with value 3. The algorithm uses a binary search variant to efficiently locate a peak by comparing mid elements with their neighbors. Starting with l=0 and r=3, it calculates mid=1. Since nums[1] = 2 is less than nums[2] = 3, it moves l to mid+1=2. Now l=r=2, so it returns 2 as the peak index.

Approach

Straightforward Solution

A naive approach scans the array linearly to find any peak, which is O(n) time. This is inefficient for large arrays.

Core Observation

A peak is guaranteed because nums[-1] = nums[n] = -∞. At an index m, compare nums[m] with nums[m+1]. If nums[m] < nums[m+1], then some peak must exist in (m, r] because the sequence is rising at m and cannot keep rising past the right boundary (it must eventually stop rising, which creates a peak). Otherwise nums[m] > nums[m+1], so some peak must exist in [l, m]. This makes it safe to discard half the search range each iteration while keeping at least one peak inside [l, r].

Path to Optimal

Preview

The key recognition signals are 'peak element', 'neighbors', and 'return any peak'. These indicate Modified Binary Search because the problem can be framed as searching for a boundary where the slope changes from ascending to descending…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a binary search with pointers l and r. At each iteration, compute mid…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(log n)

Each iteration halves the search space by moving either l or r, resulting in logarithmic time complexity.

Space

O(1)

Only a fixed number of variables (l, r, m) are used, so the algorithm uses constant auxiliary space.

Pattern Spotlight

Modified Binary Search (Slope-Based Search for Peak)

When searching for a peak or boundary in an array where the property depends on neighbors, compare mid with mid+1 to determine the slope direction and discard the half that cannot contain a peak, guaranteeing logarithmic time.

Solution

Python

1class Solution:
2    def findPeakElement(self, nums: List[int]) -> int:
3        l, r = 0, len(nums) - 1
4
5        while l < r:
6            m = l + (r - l) // 2
7
8            if nums[m] < nums[m + 1]:
9                l = m + 1
10            else:
11                r = m
12
13        return l

Step-by-Step Solution

Initialize Search Boundaries to Cover Entire Array

3	`l, r = 0, len(nums) - 1`

Objective

To set the initial left and right pointers to the start and end of the array, defining the search space.

Key Insight

Starting with l=0 and r=len(nums)-1 covers the entire array. This ensures the binary search explores all possible peak locations. The pointers represent the current candidate range where a peak must exist.

Interview Quick-Check

Core Logic

Setting l and r to the array boundaries initializes the binary search over the full input.

State & Boundaries

The search space is inclusive of both l and r, and the loop continues while l < r to ensure convergence.

Iteratively Narrow Search Space by Comparing Midpoint with Next Element

To use the slope between nums[mid] and nums[mid+1] to decide which half of the array contains a peak.

Return the Peak Index After Convergence

To return the index where the search pointers converge, which is guaranteed to be a peak.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 8 Critical

if nums[m] < nums[m + 1]:

Compare the middle element with its immediate right neighbor to determine slope direction.

This comparison is the critical decision point that enables discarding half the search space safely by identifying the slope direction, ensuring logarithmic time complexity.

Line 13 Critical

return l

Return the index where the pointers converge, representing a peak element.

Returning l at convergence is correct because the binary search invariant ensures this index corresponds to a peak element, fulfilling the problem's requirement.

Full line-by-line criticality + rationale for all 8 lines available on Pro.

Test Your Understanding

Why does comparing nums[mid] with nums[mid+1] allow us to discard half the search space safely?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Find Peak Element from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Find Peak Element drill

or drill a free problem

1	`class Solution:`
2	`def findPeakElement(self, nums: List[int]) -> int:`
3	`l, r = 0, len(nums) - 1`
4
5	`while l < r:`
6	`m = l + (r - l) // 2`
7
8	`if nums[m] < nums[m + 1]:`
9	`l = m + 1`
10	`else:`
11	`r = m`
12
13	`return l`