Find Peak Element

Patrick Leaton
Published: June 30, 2021, 9:38 p.m.
Problem Description

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

 

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

 

Constraints:

  • 1 <= nums.length <= 1000
  • -2^31 <= nums[i] <= 2^31 - 1
  • nums[i] != nums[i + 1] for all valid i.

 

The description was taken from https://leetcode.com/problems/find-peak-element/.

Problem Solution

#O(Log N) Time, O(1) Space
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) -1
        while left < right:
            mid = (left + right)//2
            if nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                right = mid
        return left 

Problem Explanation

The solution that may come right away is to scan the array while comparing two elements at a time until we find an element less than the previous.  That would be linear time complexity.

The optimal approach would be to use a binary search which would take O(Log N) time instead.  The intuition behind this is we have a sorted list in ascending order until the peak, then it is sorted in descending order.  If we're looking for an element in a sorted array, we can consider applying a binary search.

Note:  This is the same solution for Peak Index in a Mountain Array.

We will start by initializing our left and right pointers to the first and last element of the array.

        left, right = 0, len(nums) -1

 

We will then create a loop that will run while the left pointer is less than the right and in each iteration, we initialize a middle pointer that is the mean of the left and right positions.  

        while left < right:
            mid = (left + right)//2

 

The condition we are looking for is when the elements of the array increase until a peak and then decreases.

If the middle pointer is less than the element to its right then that means we are still increasing and haven't found a peak yet.  If that is the case then we will move our left pointer rightward and continue increasing to find our peak.

            if nums[mid] < nums[mid + 1]:
                left = mid + 1

 

If the middle pointer is greater than the element to its right then that means we could be after the peak so we will move the right pointer leftward and begin increasing backward to find our peak.

            else:
                right = mid

 

Once we break out of our loop it means that our left and right pointer have overlapped so we can return either pointer. 

        return left