Code Implementation

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

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

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

var peakIndexInMountainArray = function(arr) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] < arr[mid + 1]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
};
      

Problem Description

Given a mountain array arr, find the index of the peak element. A mountain array is defined as an array where:

• There exists some index i (with 0 < i < arr.length - 1) such that:
• Elements strictly increase from the start up to index i (arr[0] < arr[1] < ... < arr[i])
• Elements strictly decrease from index i to the end (arr[i] > arr[i+1] > ... > arr[arr.length - 1])

• There is exactly one valid solution.
• Do not reuse elements; the peak is unique.
• The array length is at least 3.

Thought Process

To solve this problem, let's first consider the brute-force approach: we could scan the array from left to right and look for the position where an element is greater than its neighbors. However, since the array strictly increases then strictly decreases, we know there is only one such peak.
But this brute-force approach checks each element, which is not efficient for large arrays. Since the array has a single peak and is strictly increasing then decreasing, we can use a more efficient approach inspired by binary search. By comparing the middle element to its neighbor, we can decide which side of the array contains the peak, allowing us to discard half of the search space at each step.
This optimization is possible because of the strict mountain property, much like searching for a turning point in a roller coaster ride: if you’re going up, the peak is still ahead; if you’re going down, you’ve passed it.

Solution Approach

We use a binary search algorithm to efficiently find the peak index in the mountain array. Here are the steps:

1. Initialize two pointers, left and right, at the start and end of the array.
2. While left < right:
   • Find the middle index mid as (left + right) // 2.
   • If arr[mid] < arr[mid + 1], it means we are on the increasing slope, so move left to mid + 1 (the peak must be ahead).
   • Otherwise, we are on the decreasing slope or at the peak, so move right to mid (the peak is at mid or before).
3. When left == right, we've found the peak index.

This approach works because at each step, we use the mountain property to eliminate half the array, ensuring logarithmic time.

Example Walkthrough

Example: arr = [0, 2, 4, 7, 6, 3, 1]

• Initialize left = 0, right = 6 (array length - 1).
• First iteration:
  • mid = (0 + 6) // 2 = 3
  • arr[3] = 7, arr[4] = 6
  • Since arr[3] > arr[4], we are on the decreasing slope or at the peak. Set right = 3.
• Second iteration:
  • left = 0, right = 3
  • mid = (0 + 3) // 2 = 1
  • arr[1] = 2, arr[2] = 4
  • Since arr[1] < arr[2], we are on the increasing slope. Set left = 2.
• Third iteration:
  • left = 2, right = 3
  • mid = (2 + 3) // 2 = 2
  • arr[2] = 4, arr[3] = 7
  • Since arr[2] < arr[3], we are on the increasing slope. Set left = 3.
• Now left == right == 3, so the peak index is 3.

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(n) (must check each element to find the peak)
• Space Complexity: O(1) (no extra space required)

• Time Complexity: O(log n) (at each step, we halve the search space)
• Space Complexity: O(1) (no extra space, just pointers and variables)

Summary

In summary, the problem leverages the unique structure of a mountain array to efficiently locate the peak index. While a brute-force linear scan is possible, a binary search approach is far more elegant and efficient, reducing the time complexity from O(n) to O(log n). The key insight is that comparing adjacent elements tells us which direction to search, allowing us to systematically narrow down to the peak in logarithmic time.