Peak index in Mountain Array

XXX. Peak Index in a Mountain Array

Binary Search

Problem Statement:

You are given an integer array arr that represents a mountain array. Your task is to find the peak index i, such that:

• arr[i - 1] < arr[i]
• arr[i] > arr[i + 1]

It is guaranteed that a peak index exists in the array.

Algorithm:

1. Initialize two pointers, low and high, representing the bounds of the array.
2. Perform binary search:
   • Calculate the mid-point mid = low + (high - low) / 2 to avoid overflow.
   • Check if mid is the peak:
     • arr[mid] must be greater than its left neighbor arr[mid - 1] (or it's the first element).
     • arr[mid] must also be greater than its right neighbor arr[mid + 1] (or it's the last element).
   • If arr[mid] is less than arr[mid + 1], move the low pointer to mid + 1.
   • Otherwise, move the high pointer to mid - 1.
3. The loop ends when the peak is found.

Complexity:

Time: O(log n) – The binary search reduces the search space by half in each iteration.
Space: O(1) – No additional space is required.

Java Implementation:

public int peakIndexInMountainArray(int[] arr) {
    int low = 0, high = arr.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2; // Calculate mid-point to avoid overflow

        // Check if mid is the peak
        // A peak satisfies: (1) greater than left (or at boundary) and (2) greater than right (or at boundary)
        if ((mid == 0 || arr[mid] > arr[mid - 1]) && (mid == arr.length - 1 || arr[mid] > arr[mid + 1]))
            return mid;

        // If the right neighbor is greater, the peak lies to the right
        if (mid < arr.length - 1 && arr[mid] < arr[mid + 1]) 
            low = mid + 1; // Move the low pointer to the right
        else 
            high = mid - 1; // Otherwise, the peak lies to the left
    }

    // Should not reach here since a peak is guaranteed
    return -1;
}
                

Python Implementation:

def peakIndexInMountainArray(arr):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = low + (high - low) // 2  # Calculate mid-point to avoid overflow

        # Check if mid is the peak
        if (mid == 0 or arr[mid] > arr[mid - 1]) and (mid == len(arr) - 1 or arr[mid] > arr[mid + 1]):
            return mid

        # If the right neighbor is greater, move low to mid + 1
        if mid < len(arr) - 1 and arr[mid] < arr[mid + 1]:
            low = mid + 1
        else:
            high = mid - 1

    # Should not reach here since a peak is guaranteed
    return -1
                

C++ Implementation:

int peakIndexInMountainArray(vector& arr) {
    int low = 0, high = arr.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2; // Calculate mid-point to avoid overflow

        // Check if mid is the peak
        if ((mid == 0 || arr[mid] > arr[mid - 1]) && (mid == arr.size() - 1 || arr[mid] > arr[mid + 1]))
            return mid;

        // If the right neighbor is greater, move low to mid + 1
        if (mid < arr.size() - 1 && arr[mid] < arr[mid + 1]) 
            low = mid + 1;
        else 
            high = mid - 1;
    }

    // Should not reach here since a peak is guaranteed
    return -1;
}