Peak Index in a Mountain Array

Patrick Leaton
Published: March 17, 2021, 2:08 a.m.
Problem Description

Let's call an array arr a mountain if the following properties hold:

  • arr.length >= 3
  • There exists some i with 0 < i < arr.length - 1 such that:
    • arr[0] < arr[1] < ... arr[i-1] < arr[i]
    • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

Given an integer array arr that is guaranteed to be a mountain, return any i such that arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

Example 1:

Input: arr = [0,1,0]
Output: 1

Example 2:

Input: arr = [0,2,1,0]
Output: 1

Example 3:

Input: arr = [0,10,5,2]
Output: 1

Example 4:

Input: arr = [3,4,5,1]
Output: 2

Example 5:

Input: arr = [24,69,100,99,79,78,67,36,26,19]
Output: 2

Constraints:

  • 3 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^6
  • arr is guaranteed to be a mountain array.

 

Description taken from https://leetcode.com/problems/peak-index-in-a-mountain-array/.

Problem Solution

#O(Log(N)) Time, O(1) Space
class Solution:
    def peakIndexInMountainArray(self, A: List[int]) -> int:
        left, right = 0, len(A) - 1
        while left < right:
            mid = (left + right) // 2
            if A[mid] < A[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.

However, let's notice that we are being asked to look for a specific solution within a sorted or pseudo-sorted input or output.  When we see requirements like this, a binary search may be a good approach as it will cut down the search space in half within each iteration, costing a fraction of the time.

Here, have a sorted list in ascending order until the peak, then it is sorted in descending order.  The only tweak we need to make from a traditional binary search is the comparison won't be whether the middle element is less than or greater than the target, but whether the middle target is less than or greater than the element to its right.  

Once we make that comparison, we will adjust our pointers accordingly.  If that is the case, the peak will be to the right because we'd be ascending up the mountain, otherwise, we'd be descending down it.

Note:  This is the same solution for Find Peak Element.

Let's start by initializing our left and right pointers to the first and last element of the array.

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

 

While the pointers haven't overlapped, we will continue looking for the peak.

At the beginning of each iteration, we'll initialize a middle pointer that is the mean of the left and right positions.  

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

 

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 A[mid] < A[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 traveling up the mountain's decline 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