LeetCode 852. Peak Index in a Mountain Array

Description

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

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 <= 104
• 0 <= arr[i] <= 106
• arr is guaranteed to be a mountain array.

Follow up: Finding the O(n) is straightforward, could you find an O(log(n)) solution?

Explanation

We can use binary search to find peak element where it is greater than its neighbor elements on both left and right side.

Python Solution

class Solution:
    def peakIndexInMountainArray(self, A: List[int]) -> int:
        if not A:
            return -1

        start = 0
        end = len(A) - 1
        
        while start + 1 < end:
            mid = start + (end - start) // 2
            
            if A[mid] > A[mid - 1] and A[mid] > A[mid + 1]:
                return mid
            elif A[mid] < A[mid + 1]:
                start = mid
            else:
                end = mid
                
        if A[end] > A[start]:
            return end
        else:
            return start
            
        
        return -1

• Time complexity: ~log(N)
• Space complexity: ~1