You are given an integer mountain array arr of length n where the values increase to a peak element and then decrease.

Return the index of the peak element.

Your task is to solve it in O(log(n)) time complexity.

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

Constraints:

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

Peak Index in a Mountain Array

This problem requires us to find the index of the peak element in a mountain array in O(log(n)) time complexity.

Brute Force Solution

A brute force solution would involve iterating through the array and keeping track of the largest element seen so far. The index of the largest element would be the peak index. However, this approach would have a time complexity of O(n), which doesn't meet the requirement of O(log(n)).

def peak_index_in_mountain_array_brute_force(arr):
    peak_index = 0
    for i in range(1, len(arr)):
        if arr[i] > arr[peak_index]:
            peak_index = i
    return peak_index

Optimal Solution

To achieve O(log(n)) time complexity, we can use binary search. The idea is to compare the middle element with its neighbors. If the middle element is greater than both its neighbors, then it is the peak element. If the middle element is less than its left neighbor, then the peak element is in the left half of the array. If the middle element is less than its right neighbor, then the peak element is in the right half of the array.

def peak_index_in_mountain_array(arr):
    left = 0
    right = len(arr) - 1

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

        if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1]:
            return mid
        elif arr[mid] < arr[mid - 1]:
            right = mid
        else:
            left = mid + 1

    return left

Example

Consider the array arr = [0, 1, 0]. The algorithm would proceed as follows:

1. left = 0, right = 2, mid = 1
2. arr[1] = 1. arr[0] = 0, arr[2] = 0
3. arr[1] > arr[0] and arr[1] > arr[2], so 1 is the peak index.

Big(O) Run-time Analysis

The optimal solution uses binary search, which divides the search space in half at each step. Therefore, the time complexity is O(log(n)), where n is the length of the array.

The brute-force solution iterates through each element of the array once, resulting in a time complexity of O(n).

Big(O) Space Usage Analysis

The optimal solution uses only a few variables to keep track of the left, right, and middle indices. Therefore, the space complexity is O(1).

The brute-force solution also uses only a constant amount of extra space. Therefore, the space complexity is O(1).

Edge Cases

1. Empty array: The problem statement guarantees that the array has at least 3 elements, so we don't need to handle the case of an empty array.
2. Array with only one element: Same as above, this case is not possible.
3. Array with two elements: Same as above, this case is not possible.
4. Array with all elements equal: This is not a mountain array, and the problem guarantees that the input is a mountain array.
5. Array with peak at the beginning or end: The binary search algorithm correctly handles these cases.

Code with edge cases handling

def peak_index_in_mountain_array_robust(arr):
    if not arr:
        return -1  # Handle empty array case

    left = 0
    right = len(arr) - 1

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

        if mid > 0 and mid < len(arr) - 1:
            if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1]:
                return mid
            elif arr[mid] < arr[mid - 1]:
                right = mid
            else:
                left = mid + 1
        elif mid == 0:
            if arr[0] > arr[1]:
                return 0
            else:
                return 1
        else:
            if arr[len(arr)-1] > arr[len(arr)-2]:
                return len(arr)-1
            else:
                return len(arr)-2

    return left