162. Find Peak Element - Detailed Explanation

Problem statement

Given an array of integers nums, a peak element is an element that is strictly greater than its neighbors. You need to find a peak element and return its index. If the array contains several peaks, the index of any one of them is acceptable.

Additional details:

• You may assume that nums[-1] and nums[n] are negative infinity, where n is the length of the array. Those positions do not exist, and treating them as negative infinity guarantees that at least one peak exists.
• The input array can hold a single element, which is trivially a peak.

Example inputs, outputs, and explanations

1. Example 1:

   • Input: nums = [1,2,3,1].
   • Output: 2.
   • Explanation: The element at index 2 is 3, which is greater than its neighbors 2 and 1.

2. Example 2:

   • Input: nums = [1,2,1,3,5,6,4].
   • Output: Could be 1 or 5.
   • Explanation:
     • At index 1, the element is 2, with neighbors 1 and 1, so 2 is a peak.
     • At index 5, the element is 6, with neighbors 5 and 4, so 6 is also a peak.

3. Example 3 (edge case):

   • Input: nums = [1].
   • Output: 0.
   • Explanation: With only one element, it is a peak by definition.

Constraints

• The length of nums is at least 1.
• You can assume that nums[i] is not equal to nums[i+1] for all valid indices, which rules out plateaus.
• An optimal solution is expected to run faster than O(n), ideally in O(log n).

This question is an instance of the modified binary search pattern. Classic binary search needs a sorted array, while a modified binary search keeps the halving step and swaps in a different test for deciding which half to keep. Here the test is a single comparison between a neighbor pair. The pattern applies well beyond this one problem, and the summary of the most common LeetCode patterns shows how often it appears.

Hints to approach the solution

1. Directional clues from neighbors:

   • If an element is less than its right neighbor, a peak has to exist on the right side. The values are climbing, and the climb cannot continue past the end of the array.
   • If an element is greater than its right neighbor, a peak has to lie on the left, and it may be the current element itself.

2. Binary search opportunity:

   • Given that observation, you can compare the middle element with its neighbor and decide which half of the array still contains a peak. That decision discards half the candidates per step.

Approach 1: linear scan (brute force)

Explanation

• Method:
  • Traverse the array from left to right and test each element for the peak property.
  • For each index i, verify that nums[i] is greater than both nums[i-1], when i > 0, and nums[i+1], when i < n-1.
• Edge handling:
  • Handle the first and last elements separately, since each has only one neighbor.

Pseudocode

if length(nums) == 1:
    return 0

if nums[0] > nums[1]:
    return 0

if nums[n-1] > nums[n-2]:
    return n-1

for i in range(1, n-1):
    if nums[i] > nums[i-1] and nums[i] > nums[i+1]:
         return i

Downsides:

• This approach runs in O(n) time. That is acceptable for small inputs, but it does not meet the O(log n) target the problem sets.

Approach 2: binary search (optimal)

Explanation

• Method:
  • Use binary search to shrink the search space.
  • At each iteration, compare the middle element with its right neighbor.
    • If nums[mid] > nums[mid+1], a peak exists in the left half, including mid itself.
    • Otherwise, a peak exists in the right half.
  • Continue until the search space narrows to one element, which is a peak.
• Why it works:
  • Peaks are defined by strict inequality, and the boundaries nums[-1] and nums[n] count as negative infinity. Together those two facts mean the half you keep always still contains a peak, so binary search can move toward one safely.

Pseudocode

left = 0, right = n - 1
while left < right:
    mid = (left + right) // 2
    if nums[mid] > nums[mid + 1]:
         right = mid
    else:
         left = mid + 1
return left

Detailed walkthrough (visual example)

Consider the input nums = [1,2,3,1]:

The element at index 2 is 3, which is a peak.

Code implementations

Python code