Peak Index In A Mountain Array - Leetcode Solution

Problem Statement: You have to find out the peak index in a mountain array, which is an array that increases from the start and then decreases towards its end. More formally, this is an array arr, where:

arr.length >= 3 There exists some i (0-indexed) 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]

Example: Input: arr = [0,2,1,0] Output: 1 Explanation: Index 1 is the peak index, because arr[1] = 2 is greater than arr[0] = 0 and arr[2] = 1.

Approach: The problem can be solved using Binary Search. We can search for the mid element in the array, and then determine if that element is in the increasing or decreasing part of the mountain.

If the mid element is in the increasing part, then we search in the right half to find the peak index. If the mid element is in the decreasing part, then we search in the left half to find the peak index.

Solution: The solution code in Python is given below.

class Solution: def peakIndexInMountainArray(self, arr: List[int]) -> int: left, right = 0, len(arr) - 1 while left < right: mid = (left + right) // 2 if arr[mid] < arr[mid+1]: left = mid + 1 else: right = mid return left

Explanation: We initialize left and right pointers to the first and last index of the array respectively, and then perform Binary Search to find the peak index.

In each iteration, we calculate the mid index of the array using the formula (left+right)//2. We then check whether arr[mid] < arr[mid+1] or not. If it is true, it means that we are still in the increasing part of the mountain, so we update the left pointer to (mid+1), to search in the right half. If arr[mid] >= arr[mid+1], it means that we are at the peak, or have reached the decreasing part of the mountain. In this case, we update the right pointer to mid, to search in the left half.

Finally, when left equals right, we return left, as it is the peak index of the mountain array.

1