Log inSign up
mediumLeetCodeNot Started

Find Peak Element

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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] = -infinity. 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 · Single Peak in Small Array:

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

Example 2 · Multiple Peaks:

Input: nums = [1, 2, 1, 3, 5, 6, 4]
Output: 5
Explanation: Your function can return either index 1 (value 2) or index 5 (value 6).

Example 3 · Strictly Decreasing Array:

Input: nums = [5, 4, 3, 2, 1]
Output: 0
Explanation: 5 is greater than nums[-1] (-inf) and nums[1] (4), so index 0 is a valid peak.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Binary Search template and pointer mechanics
  • Understanding local vs global extrema
  • Boundary conditions in un-sorted search spaces

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why Binary Search works on unsorted inputs with directional monotonicity.
  • Master the slope test: comparing nums[mid] with nums[mid + 1].
  • Avoid index-out-of-bounds errors on boundary indices.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find local maximum in an unsorted array with O(log N) time constraint.
  • Adjacent elements are never equal (nums[i] != nums[i+1]).
  • Boundary elements are bounded by -infinity.

Algorithmic Decision Tree:

  • If nums[mid] < nums[mid + 1] -> Peak is to the right (low = mid + 1).
  • If nums[mid] > nums[mid + 1] -> Peak is at mid or to the left (high = mid).
  • Loop until low == high; return low.

Connected Patterns:

Peak Index in a Mountain ArraySearch in Rotated Sorted ArrayBinary Search on Answer

1. Linear Scan (Brute Force)

Intuition

Iterate through the array and return the first element that is strictly greater than its successor.

Algorithm

  1. 1. Loop i from 0 to N-2: - If nums[i] > nums[i+1], return i.
  2. 2. If no such index found, return N-1 (the last element is the peak).

Brute Force Linear Scan Gradient Peak Search

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 1, 3, 5, 6, 4]
Current operationSTEP 1 OF 6
Phase 1 — Not a peak Advance i to 1: Step 1: nums[0] < nums[1]
Visual state
Values and pointers at this exact step
array
S
1
2
1
3
5
6
4
0
↑ i=0: val 1
1
2
3
4
5
6
Variables at this step
i
0
nums[0]
1
nums[1]
2
Slope
Rising
Check / comparison
Check nums[0] (1) vs nums[1] (2): 1 < 2. Slope is rising.
Decision / next transition
Not a peak. Advance i to 1.
Why this step matters

Phase 1 — Not a peak Advance i to 1: Step 1: nums[0] < nums[1]. Moving uphill, so index 0 is not a peak. Advance i.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Brute Force Approach: Linear Scan
6int findPeakElement(const vector<int>& nums) {
7 int n = nums.size();
8 for (int i = 0; i < n - 1; i++) {
9 if (nums[i] > nums[i + 1]) {
10 return i;
11 }
12 }
13 return n - 1;
14}
15
16int main() {
17 vector<int> nums = {1, 2, 3, 1};
18 int peakIndex = findPeakElement(nums);
19 cout << "Output: " << peakIndex << " (Value: " << nums[peakIndex] << ")" << endl;
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(N) — Single scan visits at most N elements.
  • Space complexity: O(1) — No extra data structures used.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Recursive Binary Search (Better)

Intuition

Divide search space in half recursively based on slope direction.

Algorithm

  1. 1. Define helper search(low, high).
  2. 2. If low == high, return low.
  3. 3. mid = low + (high - low) / 2.
  4. 4. If nums[mid] > nums[mid + 1]: return search(low, mid).
  5. 5. Else: return search(mid + 1, high).

Recursive Divide & Conquer Gradient Search

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 1, 3, 5, 6, 4]
Current operationSTEP 1 OF 6
Phase 1 — Step 1: Step 1: At mid = 3, nums[3] = 3 < nums[4] = 5
Visual state
Values and pointers at this exact step
array
S
1
2
1
3
5
6
4
0
1
2
3
↑ Range [0..6], mid=3
4
5
6
Variables at this step
Range
[0..6]
mid
3
Recurse
[4..6]
Check / comparison
mid = 3 (val 3). Compare with nums[4] = 5: nums[3] < nums[4].
Decision / next transition
Rising slope to the right. Peak is guaranteed in right half [4..6].
Why this step matters

Phase 1 — Step 1: Step 1: At mid = 3, nums[3] = 3 < nums[4] = 5. The terrain is sloping upwards to the right. A peak is guaranteed to exist in [4..6].

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Better Approach: Recursive Binary Search
6int search(const vector<int>& nums, int low, int high) {
7 if (low == high) return low;
8 int mid = low + (high - low) / 2;
9 if (nums[mid] > nums[mid + 1]) {
10 return search(nums, low, mid);
11 }
12 return search(nums, mid + 1, high);
13}
14
15int findPeakElement(const vector<int>& nums) {
16 return search(nums, 0, nums.size() - 1);
17}
18
19int main() {
20 vector<int> nums = {1, 2, 1, 3, 5, 6, 4};
21 int peakIndex = findPeakElement(nums);
22 cout << "Output: " << peakIndex << " (Value: " << nums[peakIndex] << ")" << endl;
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(log N) — Search space is halved on each recursive call, leading to log2(N) depth.
  • Space complexity: O(log N) — Call stack depth requires O(log N) memory.

3. Iterative Binary Search (Optimal)

Intuition

Perform iterative binary search on slope direction in O(log N) time and O(1) space.

Algorithm

  1. 1. Set low = 0, high = nums.length - 1.
  2. 2. While low < high: - mid = low + (high - low) / 2 - If nums[mid] < nums[mid + 1]: low = mid + 1 - Else: high = mid.
  3. 3. Return low.

Iterative Binary Search on Gradient Slopes

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 1, 3, 5, 6, 4]
Current operationSTEP 1 OF 6
Phase 1 — Step 1: Step 1 (Binary Search Step): nums[3] = 3 < nums[4] = 5
Visual state
Values and pointers at this exact step
array
S
1
2
1
3
5
6
4
0
↑ L=0
1
2
3
↑ mid=3 (val 3)
4
5
6
↑ R=6
Variables at this step
L
0
R
6
mid
3
nums[mid]
3
nums[mid+1]
5
Slope
Rising
Action
L = 4
Check / comparison
L=0, R=6. mid = (0 + 6) / 2 = 3. Compare nums[mid] (3) vs nums[mid+1] (5): 3 < 5.
Decision / next transition
Slope is RISING to the right. Peak is guaranteed in right half! Set L = mid + 1 = 4.
Why this step matters

Phase 1 — Step 1: Step 1 (Binary Search Step): nums[3] = 3 < nums[4] = 5. Since the sequence slopes upwards, continuing uphill must lead to at least one peak! Discard left half: L = mid + 1 = 4.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Optimal Approach: Iterative Binary Search on Slope
6int findPeakElement(const vector<int>& nums) {
7 int low = 0, high = nums.size() - 1;
8 while (low < high) {
9 int mid = low + (high - low) / 2;
10 if (nums[mid] < nums[mid + 1]) {
11 low = mid + 1;
12 } else {
13 high = mid;
14 }
15 }
16 return low;
17}
18
19int main() {
20 vector<int> nums = {1, 2, 1, 3, 5, 6, 4};
21 int peakIndex = findPeakElement(nums);
22 cout << "Output: " << peakIndex << " (Value: " << nums[peakIndex] << ")" << endl;
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(log N) — Halves search interval in each iteration; requires log2(N) steps.
  • Space complexity: O(1) — Only scalar pointers (low, high, mid) are used in O(1) memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute ForceO(N)O(1)Scan linearly and return the first element greater than its next neighbor.Inspects elements one by one.
2.Better — Recursive Binary SearchO(log N)O(log N)Divide and conquer recursively by comparing mid and mid+1.Recursive stack frames.
3.Optimal — Iterative Binary SearchOptimalO(log N)O(1)Binary search using two pointers (low, high) on slope direction.None; industry-standard optimal solution.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Single element array: nums = [1] -> index 0 is trivially a peak.
  • Monotonically increasing: nums = [1, 2, 3, 4] -> peak is at index 3 (last element).
  • Monotonically decreasing: nums = [4, 3, 2, 1] -> peak is at index 0 (first element).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Find Peak Element?

2.Why is the brute force approach suboptimal for large inputs in Find Peak Element?

3.Which data structure or technique enables the optimal solution for Find Peak Element?

Back to DSA Sheet