Peak Index in a Mountain Array

Problem Statement

Given an integer array arr, it represents a mountain sequence where the numbers in the sequence increase to a maximum peak value and then begin to decrease. The task is to locate and return the index of this peak element. Unlike a traditional search which can operate in O(n) time, the solution for this problem must be optimized to run in O(log(n)) time complexity, akin to a binary search. This stringent time complexity requirement suggests that a direct linear search is insufficient, and a more sophisticated approach, leveraging the properties of the mountain sequence, is necessary.

Examples

Example 1

Input:

arr = [0,1,0]

Output:

1

Example 2

Input:

arr = [0,2,1,0]

Output:

1

Example 3

Input:

arr = [0,10,5,2]

Output:

1

Constraints

• 3 <= arr.length <= 105
• 0 <= arr[i] <= 106
• arr is guaranteed to be a mountain array.

Approach and Intuition

To achieve the O(log(n)) time complexity, the problem closely mirrors the concept used in finding an element in a sorted array with a binary search. However, the twist here is that the array isn't fully sorted; it first rises to a peak and then declines. This unique structure enables the use of a modified binary search:

1. Initialize pointers: Start with two pointers, left at the beginning and right at the end of the array.

2. Binary search application: While left is less than right:

   • Calculate mid as the average of left and right.
   • Check the elements adjacent to arr[mid]. There are three cases:
     • If arr[mid-1] < arr[mid] > arr[mid+1], you've found your peak; return mid.
     • If arr[mid-1] < arr[mid] < arr[mid+1], this implies that the peak is still to the right because the sequence is still ascending. Adjust the left pointer to mid + 1.
     • If arr[mid-1] > arr[mid] > arr[mid+1], this means the peak is to the left, so adjust the right pointer to mid - 1.

3. Conclusion: The loop eventually narrows down to the peak, where left equals right, the index of the peak element.

The rationale behind this approach capitalizes on the guaranteed presense of a single peak and no plateaus (i.e., no two equal maximum elements), as implies by the constraints and the definition of a mountain array. This ensures that the binary search modification effectively converges on the peak element.

Solutions

class Solution {
public:
    int findMountainPeak(vector<int>& array) {
        int left = 0, right = array.size() - 1, middle;
        while (left < right) {
            middle = (left + right) / 2;
            if (array[middle] < array[middle + 1])
                left = middle + 1;
            else
                right = middle;
        }
        return left;
    }
};