Solution For Peak Index In A Mountain Array

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.

Step by Step Implementation For Peak Index In A Mountain Array

class Solution {
    public int peakIndexInMountainArray(int[] A) {
        // this is a simple binary search problem
        // we can find the peak element by comparing the
        // values at the middle index with its neighbors
        // if the middle element is greater than both of its
        // neighbors, then we have found the peak
        
        int left = 0;
        int right = A.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (A[mid] > A[mid - 1] && A[mid] > A[mid + 1]) {
                return mid;
            } else if (A[mid] > A[mid - 1]) {
                // the peak is to the right of the middle element
                left = mid + 1;
            } else {
                // the peak is to the left of the middle element
                right = mid - 1;
            }
        }
        
        // we can only get here if the array is not a valid mountain
        throw new IllegalArgumentException();
    }
}

class Solution:
    def peakIndexInMountainArray(self, A: List[int]) -> int:
        
        # We can solve this problem using binary search. 
        # First, we find the middle element of the array. 
        # If the middle element is greater than both of its neighbors, 
        # then we know that we have found the peak. 
        # If the middle element is less than its left neighbor, 
        # then we know that the peak must be somewhere to the left of the middle element. 
        # If the middle element is less than its right neighbor, 
        # then we know that the peak must be somewhere to the right of the middle element. 
        # We can then repeat this process on the appropriate half of the array 
        # until we find the peak.
        
        left = 0
        right = len(A)-1
        
        while left < right:
            mid = (left+right)//2
            if A[mid] < A[mid+1]:
                left = mid+1
            else:
                right = mid
        return left

var peakIndexInMountainArray = function(A) {
    // iterate through the array
    // keep track of the highest number seen so far
    // when the current number is less than the highest number seen so far, return the index of the highest number
    
    let highest = A[0];
    let index = 0;
    
    for (let i = 1; i < A.length; i++) {
        if (A[i] > highest) {
            highest = A[i];
            index = i;
        } else {
            return index;
        }
    }
};

class Solution {
public:
    int peakIndexInMountainArray(vector& A) {
        int N = A.size();
        int lo = 0, hi = N-1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (A[mid] < A[mid+1])
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo;
    }
};

public int PeakIndexInMountainArray(int[] A) {
        //find the index of the peak element in the mountain array
        int peak = 0;
        for(int i = 0; i < A.Length - 1; i++)
        {
            if(A[i] > A[i+1])
            {
                peak = i;
                break;
            }
        }
        return peak;
    }