Problem Description

You need to find a peak element in an array. A peak element is defined as an element that is strictly greater than both of its neighboring elements.

Given a 0-indexed integer array nums, your task is to find any peak element and return its index. If there are multiple peaks in the array, you can return the index of any one of them.

Important constraints:

• Elements at the boundaries have special conditions: you can imagine that nums[-1] = nums[n] = -∞ (negative infinity), where n is the length of the array
• This means the first element only needs to be greater than the second element to be a peak (since its left neighbor is considered as negative infinity)
• Similarly, the last element only needs to be greater than the second-to-last element to be a peak

Time complexity requirement: Your algorithm must run in O(log n) time, which suggests using a binary search approach rather than a linear scan.

Example scenarios:

• In an array like [1, 2, 3, 1], the element 3 at index 2 is a peak because 3 > 2 and 3 > 1
• In an array like [1, 2, 1, 3, 5, 6, 4], there are two peaks: index 1 (value 2) and index 5 (value 6). You can return either index

The key insight is that due to the boundary conditions and the definition of a peak, at least one peak element is guaranteed to exist in any non-empty array.

Intuition

The key observation is that we need O(log n) time complexity, which immediately suggests binary search. But how can we apply binary search when the array isn't sorted?

Let's think about what happens when we pick any middle element mid and compare it with its neighbor mid + 1:

1. If nums[mid] > nums[mid + 1]: We're on a "downward slope" going from left to right. Since we know nums[-1] = -∞, there must be at least one peak to the left of or at mid. Why? Because we started from negative infinity and reached nums[mid], so somewhere along the way, we must have gone up and then started going down at mid.

2. If nums[mid] < nums[mid + 1]: We're on an "upward slope" going from left to right. Since we know nums[n] = -∞, there must be at least one peak to the right of mid. Why? Because we're currently going up from nums[mid] to nums[mid + 1], but eventually we must reach negative infinity at the end, so there has to be a peak somewhere on the right.

This insight allows us to eliminate half of the search space in each iteration:

• When going downward (case 1), we can safely ignore everything to the right of mid and search in [left, mid]
• When going upward (case 2), we can safely ignore everything to the left of and including mid and search in [mid + 1, right]

The beauty of this approach is that we don't need the entire array to be sorted. We just need to know which "direction" to go based on the local slope at the middle element. The boundary conditions of negative infinity ensure that no matter which direction we choose, we're guaranteed to find a peak.

When left equals right, we've converged to a single element that must be a peak based on our elimination process.

Solution Approach

We implement the solution using binary search with two pointers: left starting at index 0 and right starting at index n-1.

Step-by-step implementation:

1. Initialize boundaries: Set left = 0 and right = len(nums) - 1 to define our search space.

2. Binary search loop: While left < right, we haven't converged to a single element yet:

   a. Calculate middle point: mid = (left + right) >> 1 (using bit shift for division by 2)

   b. Compare with right neighbor: Check if nums[mid] > nums[mid + 1]

   c. Update search space:

   • If nums[mid] > nums[mid + 1]: We're on a downward slope, so a peak exists in the left half (including mid itself). Update right = mid to search in [left, mid].
   • Otherwise (nums[mid] <= nums[mid + 1]): We're on an upward or flat slope, so a peak exists in the right half. Update left = mid + 1 to search in [mid + 1, right].

3. Return result: When the loop exits, left == right, and this index points to a peak element. Return left.

Why this works:

• Each iteration eliminates half of the remaining search space
• We always move toward a guaranteed peak based on the slope direction
• The loop terminates when we've narrowed down to a single element, which must be a peak

Time Complexity: O(log n) - We halve the search space in each iteration Space Complexity: O(1) - We only use a constant amount of extra space for the pointers

The algorithm cleverly exploits the fact that following the "upward slope" direction will always lead us to a peak, given the boundary conditions of negative infinity at both ends of the array.

Example Walkthrough

Let's walk through the algorithm with the array nums = [1, 2, 1, 3, 5, 6, 4].

Initial Setup:

• left = 0, right = 6 (array length - 1)
• We're searching for any peak element

Iteration 1:

• Calculate mid = (0 + 6) >> 1 = 3
• Compare nums[3] with nums[4]: 3 < 5
• Since we're on an upward slope (going from 3 to 5), a peak must exist on the right
• Update: left = mid + 1 = 4, right = 6
• New search space: [5, 6, 4] (indices 4-6)

Iteration 2:

• Calculate mid = (4 + 6) >> 1 = 5
• Compare nums[5] with nums[6]: 6 > 4
• Since we're on a downward slope (going from 6 to 4), a peak exists at or to the left of mid
• Update: left = 4, right = mid = 5
• New search space: [5, 6] (indices 4-5)

Iteration 3:

• Calculate mid = (4 + 5) >> 1 = 4
• Compare nums[4] with nums[5]: 5 < 6
• Since we're on an upward slope (going from 5 to 6), a peak must exist on the right
• Update: left = mid + 1 = 5, right = 5
• Now left == right = 5

Result:

• The loop exits since left == right
• Return index 5, which contains value 6
• Verify: nums[5] = 6 is indeed a peak because 6 > 5 (left neighbor) and 6 > 4 (right neighbor)

Note that the algorithm found index 5 as a peak, but index 1 (value 2) is also a valid peak. The algorithm guarantees finding a peak but not necessarily all peaks.

Solution Implementation

Time and Space Complexity

The time complexity is O(log n), where n is the length of the array nums. This is because the algorithm uses binary search, which divides the search space in half with each iteration. In each iteration, we compare the middle element with its neighbor and decide which half of the array to continue searching. Since we reduce the problem size by half each time, the number of iterations is at most log₂(n), resulting in O(log n) time complexity.

The space complexity is O(1). The algorithm only uses a constant amount of extra space for the variables left, right, and mid, regardless of the input size. No additional data structures or recursive calls are used that would scale with the input size.

Common Pitfalls

1. Incorrect Middle Calculation Leading to Integer Overflow

While the provided solution uses (left + right) >> 1, a common mistake is writing (left + right) // 2 or (left + right) / 2. In languages with fixed integer sizes (like Java or C++), left + right can cause integer overflow when both values are large.

Incorrect approach:

mid = (left + right) // 2  # Can overflow in other languages

Correct approach:

mid = left + (right - left) // 2  # Overflow-safe
# OR
mid = (left + right) >> 1  # Works in Python, but be careful in other languages

2. Wrong Comparison Direction

A frequent mistake is comparing with the wrong neighbor or using the wrong comparison operator, which can lead to infinite loops or incorrect results.

Incorrect approach:

if nums[mid] < nums[mid + 1]:  # Wrong comparison
    right = mid  # This would move in the wrong direction
else:
    left = mid + 1

Correct approach:

if nums[mid] > nums[mid + 1]:  # Compare if going downward
    right = mid  # Peak is in left half (including mid)
else:
    left = mid + 1  # Peak is in right half

3. Not Including mid in the Correct Half

When nums[mid] > nums[mid + 1], mid itself could be the peak. A common error is excluding it from the search space.

Incorrect approach:

if nums[mid] > nums[mid + 1]:
    right = mid - 1  # Wrong! This excludes a potential peak

Correct approach:

if nums[mid] > nums[mid + 1]:
    right = mid  # Keep mid in the search space

4. Handling Single Element Arrays

While the current solution handles this correctly, beginners often add unnecessary special cases for single-element arrays.

Unnecessary approach:

if len(nums) == 1:
    return 0  # Not needed
left, right = 0, len(nums) - 1
# ... rest of the code

Better approach: The main algorithm already handles this case naturally when left == right == 0.

5. Comparing with Both Neighbors

A common misconception is trying to check both neighbors of mid to determine if it's a peak, which complicates the logic and isn't necessary for the binary search approach.

Overly complex approach:

if mid > 0 and mid < len(nums) - 1:
    if nums[mid] > nums[mid - 1] and nums[mid] > nums[mid + 1]:
        return mid  # Found peak
    # More complex logic needed...

Simpler approach: Just compare with one neighbor (mid + 1) to determine which half to search, as shown in the original solution.