LeetCode · #162

Find Peak Element Solution

Find any index i such that nums[i] is strictly greater than its neighbours. Return its index.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #162

🏗️

Pattern

Binary Search — hill climbing

A peak element is strictly greater than its neighbours. Given an integer array nums, find a peak element and return its index. If the array contains multiple peaks, return the index of any peak. You may imagine that nums[-1] = nums[n] = -∞. You must write an O(log n) algorithm.

Example

 Input: nums = [1,2,3,1]
Output: 2 // nums[2] = 3 is a peak (3 > 2 and 3 > 1) 

Constraints

 • 1 ≤ nums.length ≤ 1000 • -2³¹ ≤ nums[i] ≤ 2³¹ - 1 • nums[i] ≠ nums[i + 1] for all valid i (no adjacent equals) 

Section Two · Approach 1

Linear Scan — O(n)

Walk through the array. Return the first index where nums[i] > nums[i+1] — that element is a peak (it's already greater than nums[i-1] because we came from an ascending sequence).

Problem: O(n). Since no two adjacent elements are equal, the array is a series of slopes. Binary search always moves toward a higher neighbour, guaranteeing a peak in O(log n).

Metric	Value
Time	O(n)
Space	O(1)

Section Three · Approach 2

Binary Search — O(log n)

Compare nums[mid] to nums[mid + 1]. If mid is on an ascending slope (nums[mid] < nums[mid+1]), a peak must exist to the right. If mid is descending, a peak must exist to the left (or mid itself). Move toward the higher side.

💡 Mental model: Imagine hiking in fog and you can only see one step ahead. If the terrain is going up to your right, walk right — there must be a summit somewhere (the boundary is -∞). If it's going down, walk left. You're guaranteed to find a peak because the edges are negative infinity — you can't walk off into endlessly ascending terrain.

Algorithm

Step 1: left = 0, right = n - 1.
Step 2: While left < right:
Step 3: If nums[mid] < nums[mid + 1] → ascending → peak is right: left = mid + 1.
Step 4: Else → descending → peak is left or at mid: right = mid.
Step 5: Return left.

🎯 Why is a peak guaranteed?:

Since nums[-1] = nums[n] = -∞, if you follow an ascending slope, it must eventually descend (boundary is -∞).
The transition from ascending to descending is a peak. Binary search finds it by always moving uphill.

Section Four · Trace

Visual Walkthrough

Trace through nums = [1, 2, 1, 3, 5, 6, 4]:

Binary Search — move toward the higher neighbour

Section Five · Implementation

Code — Java & Python

Java — Binary Search

 class Solution {
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1])
                left = mid + 1; // ascending — peak is right else
right = mid; // descending — peak is left or here
}
return left;
    }
}

Python — Binary Search

 class Solution:
def findPeakElement(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1 while left < right:
            mid = (left + right) // 2 if nums[mid] < nums[mid + 1]:
                left = mid + 1 else:
                right = mid
return left

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Linear Scan	O(n)	O(1)	Finds first descent point
Binary Search ← optimal	O(log n)	O(1)	Move uphill — peak guaranteed by -∞ boundaries

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single element	`[1]`	Always a peak (both neighbours are -∞). L==R==0.
Ascending	`[1,2,3,4]`	Peak is at the end (index 3). Binary search goes right every time.
Descending	`[4,3,2,1]`	Peak is at the start (index 0). Binary search goes left every time.
Multiple peaks	`[1,3,1,5,1]`	Return any peak — both index 1 and 3 are valid.

⚠ Common Mistake: Comparing nums[mid] to nums[mid - 1] instead of nums[mid + 1]. When mid = 0, accessing nums[-1] is out of bounds. Comparing to mid + 1 is safe because the loop condition left < right ensures mid < right ≤ n-1, so mid + 1 is always valid.

← Back to Binary Search problems

LearningTree

LC 162 · Find Peak Element — Solution & Explanation | DSA Guide