Peak Index in a Mountain Array LeetCode Solution

Problem Statement

Peak Index in a Mountain Array LeetCode Solution – 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 a mountain array arr, return the index i such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

You must solve it in O(log(arr.length)) time complexity.

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

Explanation

The mountain increases until it doesn’t. The point at which it stops increasing is the peak.

For this problem, we are trying to find a index where a[mid] > a[mid -1] AND a[mid] > a[mid + 1]. That is what the definition of a peak is.

We can use binary search to do this in O(log n) time, but before we go on we need to set up some ground rules on what values we will land on, and what do they mean.

There are four different scenarios we need to take into consideration

• We land on the peak where a[mid] > a[mid – 1] and a[mid] > a[mid +1]
• We land in a valley where a[mid] < a[mid-1] and a[mid] < a[mid + 1]
• We land on a slope, and need to see which way is facing towards a peak (this point is the last two scenarios)

It’s also very important to point out that index 0 or index a.length – 1 can be a peak as well! So we need some custom logic in here for that.

Code

Java Code for Peak Index in a Mountain Array:

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int start = 0;
        int end = arr.length - 1;

        while (start < end) {
            int mid = start + (end - start) / 2;

            if(arr[mid]>arr[mid+1]){
                end = mid;
            }else if (arr[mid]<arr[mid+1]){
                start = mid+1;
            }

        }
        return start;
    }
}

Python Code for Peak Index in a Mountain Array:

class Solution(object):
    def peakIndexInMountainArray(self, arr):
        start = 0
        end = len(arr)-1

        while start<=end:
            mid = (start+end)//2
            if start==end:
                return mid
            elif arr[mid] > arr[mid+1]:
                end = mid
            else:
                start = mid+1

Complexity Analysis for Peak Index in a Mountain Array LeetCode Solution

Time Complexity

O(logn), where N is the length of the Array as we are doing binary search.

Space Complexity

O(1), as we are not using any extra space.