Find Peak Element

January 14, 2024

Problem #

Given an array nums of integers which is initially increasing and then decreasing, find a peak element. A peak element is an element which is greater than its neighbors. Assume that nums[-1] and nums[n] (elements outside the array) are negative infinity.

Example:

1. Input: nums = [1, 3, 20, 4, 1, 0] Output: 20

Solution Approach #

The solution involves using a modified binary search. Since the array is initially increasing and then decreasing, a peak element can be found where the trend changes from increasing to decreasing.

Algorithm Steps #

1. Implement a binary search.
2. In each step, compare the middle element with its neighbors.
3. If the middle element is greater than both neighbors, it is the peak, return it.
4. If the left neighbor is greater, then the peak lies in the left half.
5. If the right neighbor is greater, then the peak lies in the right half.
6. Repeat until the peak is found.

Code (Python) #

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

# Test the function
print(findPeakElement([1, 3, 20, 4, 1, 0]))  # Output: 20

Time Complexity #

O(log n), where n is the number of elements in nums. The binary search halves the search space in each step.

Space Complexity #

O(1), as the solution uses constant extra space.