852. Peak Index in a Mountain Array - Detailed Explanation

Problem Statement

You are given an integer array arr that is guaranteed to be a mountain array. A mountain array has the following properties:

• arr.length >= 3
• There exists some index i (with 0 < i < arr.length - 1) such that:
  • arr[0] < arr[1] < ... < arr[i] (strictly increasing)
  • arr[i] > arr[i+1] > ... > arr[arr.length - 1] (strictly decreasing)

Your task is to return the index i (the peak index) where the maximum element (the peak) is located.

Example 1

• Input:

  arr = [0, 1, 0]
  

• Output:

  1
  

• Explanation:
  The array increases from 0 to 1 and then decreases to 0. The peak (maximum value) is at index 1.

Example 2

• Input:

  arr = [0, 2, 1, 0]
  

• Output:

  1
  

• Explanation:
  The array increases from 0 to 2 and then decreases from 2 to 1 to 0. The peak is at index 1.

Constraints

• 3 <= arr.length <= 10⁴
• 0 <= arr[i] <= 10⁵
• It is guaranteed that arr is a mountain array.

Hints for the Approach

• Hint 1: Think about how you can exploit the fact that the array is first increasing and then decreasing.
• Hint 2: A simple linear scan can find the peak, but you can achieve a better time complexity by using binary search due to the array’s structure.

Approach 1: Linear Scan

Idea

• Traverse the Array:
  Iterate through the array and compare each element with the next one.
• Identify the Peak:
  The first index where arr[i] > arr[i+1] is the peak index.

Pseudocode

for i from 0 to arr.length - 2:
    if arr[i] > arr[i+1]:
        return i

Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

Approach 2: Binary Search (Optimal)

Idea

Since the array is a mountain array, you can use binary search:

• Middle Element Check:
  For a given middle index mid, compare arr[mid] with arr[mid+1].
• Decision Making:
  • If arr[mid] < arr[mid+1], the peak lies to the right (set low = mid + 1).
  • Otherwise, the peak is to the left (or it could be mid), so set high = mid.
• Termination:
  Continue until low equals high; at that point, low is the peak index.

Pseudocode

low = 0, high = arr.length - 1
while low < high:
    mid = low + (high - low) / 2
    if arr[mid] < arr[mid + 1]:
        low = mid + 1
    else:
        high = mid
return low

Complexity

• Time Complexity: O(log n)
• Space Complexity: O(1)

Detailed Step-by-Step Walkthrough (Binary Search)

Consider the array:

arr = [0, 2, 1, 0]

1. Initialize:

   • low = 0, high = 3 (last index)

2. First Iteration:

   • mid = 0 + (3 - 0) / 2 = 1
   • Compare arr[1] (2) with arr[2] (1).
   • Since 2 > 1, set high = mid = 1.

3. Second Iteration:

   • Now low = 0, high = 1.
   • mid = 0 + (1 - 0) / 2 = 0
   • Compare arr[0] (0) with arr[1] (2).
   • Since 0 < 2, set low = mid + 1 = 1.

4. Termination:

   • low = high = 1.
   • Return index 1.

The peak index is 1, which is correct.

Python Implementation