Leetcode 852. Peak Index in a Mountain Array

Problem

You are given an integer array that follows a specific pattern: the values strictly increase up to a certain point (the peak), and then strictly decrease after that point. This is known as a "mountain array" or "bitonic array."

Your task is to find and return the index of the peak element (the maximum value in the array).

You must solve this problem in O(log n) time complexity by using a binary search approach.

Requirements

1. Return the index (not the value) of the peak element
2. The solution must run in O(log n) time complexity
3. The array will always have at least 3 elements
4. The peak will never be at the first or last index (there's always an ascending and descending portion)
5. All elements are distinct integers

Constraints

• 3 <= arr.length <= 10^5
• 0 <= arr[i] <= 10^6
• The array is guaranteed to be a valid mountain array (strictly increasing then strictly decreasing)
• Time complexity must be O(log n)
• Space complexity should be O(1)

Examples

Example 1:

Input: arr = [0, 2, 5, 3, 1] Output: 2 Explanation: The peak is at index 2 with value 5. Elements increase from index 0 to 2, then decrease from index 2 to 4.

Example 2:

Input: arr = [1, 3, 2] Output: 1 Explanation: The smallest valid mountain has its peak at the middle element.

Example 3:

Input: arr = [5, 10, 15, 20, 18, 12, 8, 4] Output: 3 Explanation: The array increases until index 3 (value 20), then decreases afterward.

Example 4:

Input: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7] Output: 9 Explanation: The peak element 10 is located at index 9.

Hint 1: Binary Search Intuition Since the array has a special structure (increasing then decreasing), you can use binary search. At any middle point, look at the neighboring elements to determine whether the peak lies to the left or right. If the middle element is less than its right neighbor, you're still in the ascending portion.

Hint 2: Which Direction to Search Compare arr[mid] with arr[mid + 1]:

• If arr[mid] < arr[mid + 1], the peak must be to the right (we're still climbing)
• If arr[mid] > arr[mid + 1], the peak is at mid or to the left (we've started descending)

This property allows you to eliminate half the search space in each iteration.

Hint 3: Termination Condition Continue the binary search until your search space narrows down to a single element. That element will be the peak since we're guaranteed a valid mountain array.

Full Solution ` def findPeakIndex(arr): """ Find the index of the peak element in a mountain array using binary search.

Time Complexity: O(log n) - we halve the search space each iteration
Space Complexity: O(1) - only using a constant amount of extra space
"""
left = 0
right = len(arr) - 1

# Binary search to find the peak
while left < right:
    mid = left + (right - left) // 2
    
    # Compare middle element with its right neighbor
    if arr[mid] < arr[mid + 1]:
        # We're in the ascending portion, peak is to the right
        left = mid + 1
    else:
        # We're in the descending portion or at the peak
        # Peak is at mid or to the left
        right = mid

# When left == right, we've found the peak
return left

`

Explanation:

The solution uses binary search to efficiently locate the peak in O(log n) time:

1. Initialization: We set up two pointers, left at the start and right at the end of the array.

2. Binary Search Loop: While our search space contains more than one element:

   • Calculate the middle index
   • Compare arr[mid] with arr[mid + 1] to determine which half contains the peak
   • If arr[mid] < arr[mid + 1]: we're still ascending, so the peak must be in the right half (update left = mid + 1)
   • If arr[mid] > arr[mid + 1]: we're descending or at the peak, so the peak is at mid or in the left half (update right = mid)

3. Termination: The loop ends when left == right, pointing to the peak element.

Why This Works:

The mountain array's structure guarantees that:

• There's exactly one peak
• By comparing adjacent elements, we can always determine which direction to search
• Each iteration eliminates half the remaining search space
• Eventually, both pointers converge on the peak index

Time Complexity: O(log n) because we perform binary search, halving the search space with each comparison.

Space Complexity: O(1) since we only use a fixed number of variables regardless of input size.