852. Peak Index in a Mountain Array - Detailed Explanation

Problem Statement

A mountain array is defined as an array that satisfies the following properties:

• The array contains at least three elements.

• There exists an index i (with (0 < i < \text{arr.length} - 1)) such that:

  • ( \text{arr}[0] < \text{arr}[1] < \dots < \text{arr}[i] ) (strictly increasing), and
  • ( \text{arr}[i] > \text{arr}[i+1] > \dots > \text{arr}[\text{arr.length} - 1] ) (strictly decreasing).

Task:
Given a mountain array arr, return the index i (the peak index) where the peak (maximum value) is located.

Example 1

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

Example 2

• Input: [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 \leq \text{arr.length} \leq 10^4)

• (0 \leq \text{arr}[i] \leq 10^6)

• The input array is guaranteed to be a mountain array.

Hints to Guide Your Approach

1. Unimodal Property:
   Since the array first strictly increases and then strictly decreases, the peak is the unique maximum value. You can exploit this property to find the peak efficiently.

2. Binary Search Strategy:
   Use binary search to efficiently locate the peak. Compare the middle element with its next neighbor:

   • If ( \text{arr}[mid] < \text{arr}[mid + 1] ), then the peak must lie to the right.
   • Otherwise, the peak lies to the left (or could be the current element).

   This way, you reduce the search space by half in each iteration.

Approaches to Solve the Problem

Approach 1: Linear Scan

Explanation

• Idea:
  Iterate through the array until you find the point where an element is greater than its next element.

• Steps:

  1. Loop from index 0 to the end.
  2. For each index ( i ), if ( \text{arr}[i] > \text{arr}[i+1] ), then ( i ) is the peak index.

• Complexity Analysis:

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

• Pros & Cons:
  It is simple and works well for small arrays, but it does not take full advantage of the mountain array property.

Approach 2: Binary Search (Optimal)

Explanation

• Idea:
  Because the array is strictly increasing and then strictly decreasing, you can use binary search to find the point where the order changes.
• Steps:

  1. Initialize two pointers: low = 0 and high = arr.length - 1.

  2. While low < high:

     • Compute mid = (low + high) // 2.
     • If ( \text{arr}[mid] < \text{arr}[mid + 1] ), then the peak is in the right half, so set low = mid + 1.
     • Otherwise, the peak is in the left half or could be the current mid, so set high = mid.

  3. When low == high, you have found the peak index.

• Complexity Analysis:
  • Time Complexity: O(\log n))
  • Space Complexity: (O(1))
• Why It Works:
  At each iteration, you are making a decision based on the slope of the mountain (whether it is ascending or descending) and narrowing down the region that can contain the peak.

Code Implementations

Python Code

Below is the Python implementation using the binary search approach: