Find Peak Element - Video Solutions

Problem Overview: You receive an integer array nums where a peak element is strictly greater than its neighbors. The task is to return the index of any peak element. The array may contain multiple peaks, and accessing outside the array is treated as negative infinity, which guarantees at least one peak exists.

Approach 1: Linear Scan (O(n) time, O(1) space)

The most direct strategy is to iterate through the array and check whether the current element is greater than its adjacent elements. For index i, verify nums[i] > nums[i-1] and nums[i] > nums[i+1]. Edge cases are handled by treating missing neighbors as negative infinity, so the first or last element can also be a peak. The algorithm simply scans left to right and returns the first peak encountered. This approach uses constant extra memory and is easy to implement, but it requires examining every element in the worst case.

This method is useful when simplicity matters more than performance or when the array size is small. It demonstrates a clear understanding of the peak definition but does not take advantage of the structure of the problem.

Approach 2: Binary Search Approach (O(log n) time, O(1) space)

The optimal solution applies binary search to the array. Instead of looking for a specific value, the search uses the slope between adjacent elements to determine where a peak must exist. At each step, compare nums[mid] with nums[mid + 1]. If nums[mid] > nums[mid + 1], the peak lies on the left side (including mid) because the sequence is descending. Otherwise, the peak must exist on the right side because the sequence is ascending.

This observation works because any ascending slope must eventually lead to a peak, and any descending slope means a peak already exists behind it. Repeatedly narrowing the search interval halves the remaining elements each iteration, giving O(log n) time complexity with constant space.

The approach treats the array like a landscape of slopes and peaks rather than a collection of values. It leverages properties of arrays and the divide‑and‑conquer nature of binary search to locate a valid peak efficiently without scanning the entire input.

Recommended for interviews: Interviewers expect the binary search solution. The linear scan proves you understand the peak definition and boundary cases, but it runs in O(n). The binary search approach reduces the complexity to O(log n) and demonstrates strong algorithmic reasoning. Explaining the slope observation—why moving toward the larger neighbor guarantees a peak—usually separates a solid solution from a great one.