852. Peak Index in a Mountain Array

Approach 1: Return the largest number

class Solution(object):
    def peakIndexInMountainArray(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        return A.index(max(A))

The largest number will always be greater than it's neighbours so if just find the largest number and return it's index we will get the peak index

Time Complexity: O(N), both max and index are linear runtime functions

Space Complexity: O(1)

Approach 2: Binary Search for the Peak Index

class Solution:
    def peakIndexInMountainArray(self, A):
        """
        https://leetcode.com/problems/peak-index-in-a-mountain-array/description/
        :type A: List[int]
        :rtype: int
        """
        low, high = 0, len(A)-1
        peak = 0

        while low <= high:
            mid = low + (high-low)//2
            if A[mid-1] < A[mid] > A[mid+1]:
                peak = mid
                return peak
            elif A[mid-1] < A[mid]:
                low = mid+1
            else:
                high = mid-1

Like any binary search we have the low and high initialized as 0 and the length of the array, and then we try to find not a specific number but a number that satisfies our criteria for peak index

Time Complexity: O(logN)

Space Complexity: O(1)