Main Idea:

The main idea is to use a binary search-like approach to find a peak element in the array. We can observe that if we start from any index mid, there are three possibilities:

  • If nums[mid] is greater than both its neighbors, then mid is a peak.
  • If nums[mid-1] is greater than nums[mid], then there must be a peak on the left side.
  • If nums[mid+1] is greater than nums[mid], then there must be a peak on the right side. By comparing the elements at indices mid-1 and mid+1, we can decide which side of the array to explore, narrowing down the search space. This approach ensures that we move towards a peak element.
from typing import List

def find_peak_element(nums: List[int]) -> int:
    # Binary search-like approach
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        
        # Check if mid is a peak
        if nums[mid] > nums[mid+1]:
            # Move to the left side
            right = mid
        else:
            # Move to the right side (mid+1 must be greater)
            left = mid + 1
    
    # At the end of the loop, left and right will be equal, and the peak is found
    return left

# Example usage:
result1 = find_peak_element([1, 2, 3, 1])
print(result1)
assert result1 == 2
# Explanation: The peak element is 3, and its index is 2.

result2 = find_peak_element([1, 2, 1, 3, 5, 6, 4])
print(result2)
assert result2 in [1, 5]
# Explanation: The peak elements are 2 and 6, and their indices are 1 and 5, respectively.

Time Complexity:

The time complexity of the binary search-like approach is O(log N), where N is the length of the input array nums. In each step, the search space is reduced by half.

Space Complexity:

The space complexity is O(1) since we are using a constant amount of additional space, regardless of the input size. The algorithm does not use any extra data structures that scale with the input.