{x}
blog image

Peak Index in a Mountain Array

You are given an integer mountain array arr of length n where the values increase to a peak element and then decrease.

Return the index of the peak element.

Your task is to solve it in O(log(n)) time complexity.

 

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.

Solution Explanation:

The problem asks to find the peak index in a mountain array. A mountain array is an array that strictly increases until a peak, then strictly decreases. The solution uses binary search to efficiently find the peak index in O(log n) time.

Approach:

The core idea is that we can leverage binary search because of the mountain array's sorted nature (increasing then decreasing). We can eliminate half the search space in each iteration.

  1. Initialization: We start with left = 1 and right = len(arr) - 2. We exclude the first and last elements because the peak cannot be at either end (by definition of a mountain array).

  2. Iteration: The while left < right loop continues until the search space is reduced to a single element.

  3. Midpoint Calculation: mid = (left + right) >> 1 calculates the middle index using bitwise right shift (equivalent to integer division by 2).

  4. Comparison: We compare arr[mid] with arr[mid + 1].

    • If arr[mid] > arr[mid + 1], it means we've passed the peak, so the peak must lie in the left half (right = mid).
    • Otherwise (arr[mid] < arr[mid + 1]), the peak is in the right half (left = mid + 1).

  5. Return Value: After the loop, left (and right) will point to the index of the peak element.

Time Complexity: O(log n) - because we are using binary search. The search space is halved in each iteration.

Space Complexity: O(1) - constant extra space is used, irrespective of the input size.

Code Explanation (Python as Example):

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        left, right = 1, len(arr) - 2
        while left < right:
            mid = (left + right) >> 1
            if arr[mid] > arr[mid + 1]:
                right = mid
            else:
                left = mid + 1
        return left
  • left and right pointers define the search space.
  • The while loop performs the binary search.
  • mid is the middle index.
  • The if condition checks if arr[mid] is greater than its right neighbor. If true, the peak is to the left; otherwise, it's to the right.
  • Finally, left (which equals right after the loop) is the peak index.

The other language solutions follow the same logic, just with syntax differences specific to their respective languages. The core algorithm remains consistent across all implementations.