162. Find Peak Element - Detailed Explanation

Problem Statement

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

Additional Details:

• You may assume that nums[-1] and nums[n] (where n is the length of the array) are negative infinity (i.e., they do not exist), which guarantees that at least one peak exists.
• The input array can have 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 by definition a peak.

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 guarantees no plateaus).
• An optimal solution is expected to have a time complexity better than O(n), ideally O(log n).

Hints to Approach the Solution

1. Directional Clues from Neighbors:

   • Observe that if an element is less than its right neighbor, then there must be a peak on the right side. Conversely, if an element is greater than its right neighbor, then a peak must lie on the left (including possibly the current element).

2. Binary Search Opportunity:

   • Given the above observation, you can leverage a binary search approach by comparing the mid-element with its neighbor to decide which half of the array contains a peak.

Approach 1: Linear Scan (Brute Force)

Explanation

• Method:
  • Traverse the array from left to right and check for each element whether it is a peak.
  • Specifically, for each index i, verify if nums[i] is greater than both nums[i-1] (if i > 0) and nums[i+1] (if i < n-1).
• Edge Handling:
  • Handle the first and last elements separately since they have 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, which is acceptable for smaller inputs but not optimal if the problem requires O(log n).

Approach 2: Binary Search (Optimal)

Explanation

• Method:
  • Use binary search to reduce the search space efficiently.
  • At each iteration, compare the middle element with its right neighbor.
    • If nums[mid] > nums[mid+1], then a peak exists in the left half (including mid).
    • Otherwise, a peak exists in the right half.
  • Continue until the search space is narrowed down to one element, which is a peak.
• Why It Works:
  • Because of the way peaks are defined and the guarantee that nums[-1] and nums[n] are negative infinity, a binary search approach can safely move toward the direction of a peak.

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