Find Peak Element LeetCode 162 Guide

LeetCode 162 — Find Peak Element — gives you an integer array nums where you must return the index of any peak element. A peak element is one that is strictly greater than both of its neighbors. The problem guarantees that nums[-1] = nums[n] = -infinity, meaning the boundaries on both sides are treated as negative infinity — so an element at the very start or end only needs to beat one neighbor to qualify as a peak.

For example, given nums = [1, 2, 3, 1], index 2 holds value 3, which is greater than nums[1]=2 and nums[3]=1, so index 2 is a valid peak. For nums = [1, 2, 1, 3, 5, 6, 4], either index 1 (value 2) or index 5 (value 6) are valid peaks — the problem only requires you return any one of them. Adjacent elements are guaranteed to be unequal, so there are no plateaus to worry about.

The naive O(n) linear scan works but the problem explicitly asks for an O(log n) solution. This O(log n) requirement is the strong hint that binary search is the intended approach — and once you understand the key invariant, binary search on this problem is elegant and provably correct.

The key insight is rooted in the boundary condition: nums[-1] = nums[n] = -infinity. This means both ends of the array are guaranteed to be valleys (negative infinity). Because the array must start from -infinity and eventually return to -infinity, it must go up at some point and come back down — which means at least one peak is guaranteed to exist.

Now consider the midpoint mid. If nums[mid] < nums[mid+1], then the right neighbor is larger. The array is currently "going uphill" to the right. Since the right boundary is -infinity, the array must eventually come back down — and wherever it turns from going up to going down is a peak. Therefore, the right half from mid+1 onward is guaranteed to contain at least one peak.

Conversely, if nums[mid] >= nums[mid+1], then mid itself might be a peak or there is a peak somewhere to the left. Either way, the left half (including mid) is guaranteed to contain a peak. This allows us to confidently discard half the search space each iteration, giving O(log n) time with O(1) space.

The implementation is a standard binary search with lo=0 and hi=len(nums)-1. At each step, compute mid = (lo + hi) // 2. Compare nums[mid] with nums[mid+1]. If nums[mid] < nums[mid+1], set lo = mid + 1 (peak is in the right half). Otherwise set hi = mid (peak is at mid or in the left half). When lo == hi, we have converged on a peak — return lo.

Notice that mid is always computed as (lo + hi) // 2, which floors toward lo. When lo < hi, we have at least two elements, so mid < hi, which means mid + 1 is always a valid index. This is why we compare nums[mid] with nums[mid+1] and never nums[mid-1] — it avoids index-out-of-bounds without special-casing.

The loop invariant is: a peak always exists in the range [lo, hi]. Initially this holds for the full array. Each iteration we either move lo up past mid or bring hi down to mid, always preserving the invariant. When lo == hi, the single remaining element must be a peak because the invariant guarantees it.

The problem statement explicitly says "return the index to any of the peak elements." This is a deliberate design choice that enables the binary search approach. At each step, binary search commits to one half of the array and discards the other. If the problem required the global maximum, we could not safely discard the other half — it might contain the single largest element.

Because any peak is acceptable, when we detect "going uphill" (nums[mid] < nums[mid+1]) and move lo to mid+1, we are not claiming there is no peak in the left half — there might be. We are only claiming the right half definitely contains a peak. Returning that peak satisfies the problem's "any peak" requirement just as well.

This distinction matters when reasoning about correctness. The algorithm is not finding THE peak; it is finding A peak. The boundary condition combined with the "any peak" requirement is the precise combination that makes O(log n) possible. Removing either condition would break the approach.

Trace the algorithm on nums = [1, 2, 3, 1]. Initial state: lo=0, hi=3. Step 1: mid = (0+3)//2 = 1. nums[1]=2, nums[2]=3. Since 2 < 3, go right: lo = mid+1 = 2. Now lo=2, hi=3.

Step 2: mid = (2+3)//2 = 2. nums[2]=3, nums[3]=1. Since 3 >= 1, go left: hi = mid = 2. Now lo=2, hi=2. Loop ends (lo == hi). Return lo = 2.

Verification: nums[2] = 3. Left neighbor nums[1] = 2 < 3. Right neighbor nums[3] = 1 < 3. Index 2 is indeed a peak. The algorithm found it in 2 iterations rather than scanning all 4 elements.

Python solution: def findPeakElement(nums): lo, hi = 0, len(nums) - 1; while lo < hi: mid = (lo + hi) // 2; if nums[mid] < nums[mid+1]: lo = mid + 1; else: hi = mid; return lo. Time complexity O(log n), space O(1). The single-element array (len=1) is handled immediately — lo==hi from the start, loop never executes, returns 0 which is trivially a peak against -infinity boundaries.

Java solution: public int findPeakElement(int[] nums) { int lo = 0, hi = nums.length - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] < nums[mid+1]) lo = mid + 1; else hi = mid; } return lo; }. The expression lo + (hi - lo) / 2 avoids integer overflow compared to (lo + hi) / 2 when lo and hi are large — a safe habit in Java. Same O(log n) time and O(1) space.

Both handle the two-element case (lo=0, hi=1) naturally: mid=0, compare nums[0] with nums[1]. If nums[0] < nums[1], lo becomes 1 and we return index 1 (right element is peak). If nums[0] >= nums[1], hi becomes 0 and we return index 0 (left element is peak). No special cases needed.

Find Peak Element belongs to the "binary search on a condition" family — problems where you binary search not on a sorted array but on a monotone boolean property. Find Minimum in Rotated Sorted Array (LeetCode 153) uses a similar invariant: if nums[mid] > nums[hi], the minimum is in the right half; otherwise it is in the left half. Both problems discard half the array based on a comparison that preserves a guaranteed property.

Koko Eating Bananas (LeetCode 875) and Search in Rotated Sorted Array (LeetCode 33) extend the pattern. Koko binary-searches on the answer space — the feasible eating speeds form a monotone condition. LeetCode 33 binary-searches a rotated array by identifying which half is sorted and whether the target lies within it. All share the core idea: find a binary condition that lets you safely discard half the search space.

Mastering Find Peak Element (LeetCode 162) trains the most fundamental form of this skill: reasoning about a directional invariant (uphill implies peak ahead) to justify the binary discard. Once internalized, this reasoning transfers directly to harder problems like LeetCode 4 (Median of Two Sorted Arrays) and LeetCode 410 (Split Array Largest Sum).