852. Peak Index in a Mountain Array

Problem Description

An array arr is a mountain array if and only if:

• 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].

Examples:

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

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

Input: arr = [0,10,5,2]
Output: 1

Constraints:

• 3 ≤ arr.length ≤ 10⁵
• 0 ≤ arr[i] ≤ 10⁶
• arr is guaranteed to be a mountain array

Python Solution

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

Implementation Notes:

• Uses binary search to find peak
• Time complexity: O(log n)
• Space complexity: O(1)

Java Solution

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 1;
        int right = arr.length - 2;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1]) {
                return mid;
            } else if (arr[mid] > arr[mid-1]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
}

C++ Solution

class Solution {
public:
    int peakIndexInMountainArray(vector& arr) {
        int left = 1;
        int right = arr.size() - 2;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1]) {
                return mid;
            } else if (arr[mid] > arr[mid-1]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
};

JavaScript Solution

/**
 * @param {number[]} arr
 * @return {number}
 */
var peakIndexInMountainArray = function(arr) {
    let left = 1;
    let right = arr.length - 2;
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        
        if (arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1]) {
            return mid;
        } else if (arr[mid] > arr[mid-1]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return left;
};

C# Solution

public class Solution {
    public int PeakIndexInMountainArray(int[] arr) {
        int left = 1;
        int right = arr.Length - 2;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1]) {
                return mid;
            } else if (arr[mid] > arr[mid-1]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }
}

Implementation Notes:

• Uses binary search to find peak efficiently
• Time complexity: O(log n)
• Space complexity: O(1)