162. Find Peak Element

Quick Identifier

• Topic: binary-search
• Pattern: Binary Search (Slope / neighbor compare)
• Difficulty: Medium
• Companies: Google, Amazon, Meta, Apple, Bloomberg
• Frequency: High
• LeetCode: 162

Quick Sights

• Time Complexity: O(log n) from the optimal approach.
• Space Complexity: O(1) from the optimal approach.
• Core Mechanism: Given an array where nums[-1] and nums[n] are treated as negative infinity, return any index that is a strict local peak (nums[index] > neighbors). Guarantee a peak exists.

Concept Explanation

Given an array where nums[-1] and nums[n] are treated as negative infinity, return any index that is a strict local peak (nums[index] > neighbors). Guarantee a peak exists.

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

• “Peak” with boundaries at negative infinity
• O(log n) expected
• Compare mid to mid+1 to see uphill vs downhill

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Brute force — O(n) — scan for nums[index] > nums[index+1] and nums[index] > nums[index-1].
• Better — not needed.
• Optimal — O(log n) time / O(1) space — if nums[mid] < nums[mid+1], a peak exists to the right; else to the left (inclusive mid).

Optimal Solution

Go

func findPeakElement(nums []int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := left + (right-left)/2
		if nums[mid] < nums[mid+1] {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left
}

JavaScript

function findPeakElement(nums) {
	let left = 0;
	let right = nums.length - 1;
	while (left < right) {
		const mid = left + Math.floor((right - left) / 2);
		if (nums[mid] < nums[mid + 1]) {
			left = mid + 1;
		} else {
			right = mid;
		}
	}
	return left;
}

Walkthrough

nums = [1,2,3,1]

Return index 2. Invariant: a peak always remains in [left, right].

Edge Cases

• Single element — peak index 0.
• Strictly increasing — peak at last index.
• Strictly decreasing — peak at index 0.

Pitfalls

• Off-by-one comparing mid to mid-1 only — need consistent uphill rule with mid+1.
• Assuming unique peak — any peak is acceptable.

Similar Problems

• 153. Find Minimum in Rotated Sorted Array — also compares halves via endpoints.
• 704. Binary Search — baseline shrinking interval.
• 875. Koko Eating Bananas — binary search driven by a local monotone signal.

Variants

• 2D peak — compare to four neighbors; move toward larger neighbor.
• Bitonic array peak — known structure; similar slope logic.

Mind-Map Tags

#binary-search #peak #slope #neighbor-compare