Find Peak Element Solution

Problem

Given an integer array, find any index where the element is strictly greater than both of its immediate neighbors. Elements outside the array boundaries count as negative infinity, so the first and last elements each only need to beat a single neighbor. Any valid peak index is an acceptable answer.

Example:

Input: nums = [1, 2, 3, 1]
Output: 2
Explanation: nums[2] = 3 is greater than nums[1] = 2 on its left and nums[3] = 1 on its right.

Multiple peaks are allowed:

Input: nums = [1, 2, 1, 3, 5, 6, 4]
Output: 5 (or 1 — both are valid peaks)
Explanation: nums[5] = 6 beats both neighbors; nums[1] = 2 also beats its neighbors.

Intuition

Because the boundaries act as invisible walls of negative infinity, the array must crest somewhere — it cannot rise forever before hitting the right edge. Binary search exploits this: if the right neighbor of mid is larger than mid, the array is still going uphill to the right, so a peak must lie in that half. The same logic applies leftward, and the two cases are exhaustive.

Approach 1 — Linear Scan

Scan from left to right and return the first index where the element beats both neighbors, treating out-of-bounds positions as −∞.

Steps:

For each index i, determine whether the left neighbor is smaller (true if i is 0 or nums[i] > nums[i-1]).
Determine whether the right neighbor is smaller (true if i is the last index or nums[i] > nums[i+1]).
Return i if both conditions hold — that element is a local maximum.
The first such index encountered is always valid; return -1 only as a dead code sentinel since the problem guarantees a peak exists.

1def findPeakElement(nums: list[int]) -> int:
2    n = len(nums)
3    for i in range(n):
4        left_is_smaller = (i == 0) or (nums[i] > nums[i - 1])
5        right_is_smaller = (i == n - 1) or (nums[i] > nums[i + 1])
6        if left_is_smaller and right_is_smaller:
7            return i
8    return -1  # unreachable: problem guarantees a peak exists

Time: O(n) — in the worst case every element is checked before finding a peak at the end.
Space: O(1) — only a handful of boolean variables; no auxiliary data structure.

Approach 2 — Binary Search

Use binary search: compare mid against its right neighbor to decide which half is guaranteed to contain a peak, then narrow until left and right converge.

Steps:

Initialize left = 0, right = n − 1.
Compute mid = (left + right) / 2.
If nums[mid] > nums[mid + 1], a peak exists in [left, mid] — set right = mid (mid itself might be it).
Otherwise nums[mid + 1] > nums[mid], so the array is still rising rightward and a peak exists in [mid + 1, right] — set left = mid + 1.
When left == right the search space has collapsed to a single element that is guaranteed to be a peak — return left.

1def findPeakElement(nums: list[int]) -> int:
2    left, right = 0, len(nums) - 1
3    while left < right:
4        mid = (left + right) // 2
5        if nums[mid] > nums[mid + 1]:
6            right = mid  # peak is in [left, mid]; mid itself is a candidate
7        else:
8            left = mid + 1  # nums[mid+1] > nums[mid], so peak is in [mid+1, right]
9    return left

Time: O(log n) — the search space halves on every iteration.
Space: O(1) — only two pointer variables regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
Linear Scan	O(n)	O(1)	When simplicity matters more than speed, or for verification
Binary Search	O(log n)	O(1)	Standard approach; required when O(log n) is specified in constraints

Common Mistakes

Setting right = mid - 1 when nums[mid] > nums[mid + 1]: This skips mid itself, which may be the peak. The correct update is right = mid so mid stays in the search range.
Using while left <= right with right = mid: When left == right, mid equals both and right = mid never shrinks the window — infinite loop. The left < right condition exits cleanly at convergence.
Returning mid after the loop: After while left < right, mid retains its last-iteration value, not the answer. Return left (which equals right) — that is the converged peak index.
Checking nums[i] > nums[i - 1] at index 0 in Python without a boundary guard: Python's negative indexing makes nums[-1] wrap around to the last element, so nums[0] > nums[-1] compares against a real element rather than −∞. Always guard with i == 0 first.
Comparing mid against both neighbors instead of just mid + 1: The binary search only needs one comparison (nums[mid] vs nums[mid + 1]) to decide which half to eliminate. Adding a left-neighbor check introduces redundancy and complicates the boundary logic.

Find Peak Element — Solution