852. Peak Index in a Mountain Array


Problem Description

In this problem, we're given an array arr that represents a mountain, which means it has the shape of a peak: the elements first increase and then decrease. The constraints that define a mountain are:

  1. The length of the array should be at least 3.
  2. There exists an index i where 0 < i < arr.length - 1, and the elements of the array increase from arr[0] to arr[i - 1], reach a peak at arr[i], and then decrease from arr[i + 1] to arr[arr.length - 1].

Our goal is to find the peak of the mountain, which is the index i at the top of the mountain. Importantly, we're asked to find this peak index within a logarithmic time complexity, more precisely O(log(arr.length)), which suggests that a straightforward linear scan won't be sufficient as it would take linear time.

Intuition

To find the peak index in an efficient way that meets the time complexity requirement of O(log(arr.length)), we immediately think of the binary search algorithm. Binary search cuts the problem space in half each time it makes a comparison, which results in the logarithmic time complexity.

The intuition behind using binary search for this problem lies in the properties of a mountain array. Since the elements strictly increase up to the peak and then strictly decrease, if we pick a point in the array and look at its immediate neighbor(s), we can decide which half of the array the peak lies in:

  1. If the current element is greater than its right neighbor, we know that the peak is at this element or to its left.
  2. Conversely, if the current element is less than its right neighbor, the peak must be to the right of this element.

We can keep narrowing down our search space using these comparisons until we converge on the peak element.

The provided solution in Python performs this algorithm efficiently using a while loop to iterate through the potential peak indices within the boundaries defined by left and right. We intentionally start left at 1 and right at len(arr) - 2 to ensure we do not consider the endpoints of the array, which cannot be peaks based on the mountain array definition. The use of the bitwise shift operation >> 1 is a common technique to quickly divide mid by 2, which is a part of the binary search approach to find the middle index between left and right.

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Depth first search can be used to find whether two components in a graph are connected.

Solution Approach

The solution to finding the peak index in the mountain array employs the binary search algorithm. Here's a detailed walkthrough of the implementation based on the provided code:

  1. We initialize two pointers, left and right, that define the range within which we'll conduct our search. As the peak cannot be the first or last element (by the definition of a mountain array), we set left to 1 and right to len(arr) - 2.

  2. We enter a while loop that will run as long as left is less than right, ensuring that we consider at least two elements. This is necessary because we compare the element at the midpoint with its immediate right neighbor to determine the direction of the search.

  3. Within the loop, we calculate the midpoint mid using (left + right) >> 1, which is equivalent to (left + right) / 2 but faster computationally as it is a bit-shift operation that divides right and left by 2.

  4. We then perform a comparison between the elements at arr[mid] and arr[mid + 1]. If arr[mid] is greater than arr[mid + 1], this implies we are currently at a descending part of the array, or we may have found the peak. Thus, the peak index must be at mid or to its left. In this case, we move the right pointer to mid to narrow the search range.

  5. If arr[mid] is not greater than arr[mid + 1], it means we're on an ascending part of the array, and the peak lies to the right of mid. Consequently, we move the left pointer to mid + 1 to adjust the search range.

  6. The loop continues until left and right converge, which happens when left equals right. At this point, both pointers are indicating the peak's index, so we return the value of left.

By repeatedly halving the range of possible indices, we ensure the logarithmic time complexity O(log(arr.length)), as required by the problem.

One thing to note about this implementation is that it uses a half-interval search. This means we always move one of our boundaries to the midpoint itself, not past it. This approach guarantees that the search space is reduced after each iteration and that we don't overshoot the peak and miss it in our search.

Lastly, the algorithm doesn't use any auxiliary data structures, it operates directly on the input array, which ensures space complexity of O(1) - only constant extra space is used.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search can be used to find whether two components in a graph are connected.

Example Walkthrough

Let's consider a sample mountain array arr = [1, 3, 5, 4, 2] to illustrate the solution approach:

  1. Initialize two pointers, left = 1 and right = len(arr) - 2 = 3, to avoid checking the first and last elements as they cannot be the peak by definition.

  2. Start the while loop since left < right (1 < 3 is true).

  3. Calculate the midpoint mid using (left + right) >> 1. For our example, it's (1 + 3) >> 1, which equals 2.

  4. Compare arr[mid] to arr[mid + 1]. For mid = 2, arr[mid] is 5 and arr[mid + 1] is 4. Because 5 > 4, we update right to mid. Now left = 1 and right = 2.

  5. The loop continues because left < right is still true.

  6. Recalculate the midpoint with the updated pointers. Now, mid is (1 + 2) >> 1, which equals 1.

  7. Compare arr[mid] to arr[mid + 1] again. For mid = 1, arr[mid] is 3 and arr[mid + 1] is 5. Because 3 < 5, we update left to mid + 1. Now left = 2 and right = 2.

  8. The loop ends because left equals right, indicating convergence at the peak's index, which is 2 in our example array.

  9. Return left, which is the peak index. In our array, arr[2] is indeed the peak with a value of 5.

Through each iteration, the search space is narrowed down until the peak is found, fulfilling the O(log(arr.length)) time complexity for this logarithmic search approach.

Not Sure What to Study? Take the 2-min Quiz:

In a binary min heap, the minimum element can be found in:

Python Solution

1class Solution:
2    def peakIndexInMountainArray(self, arr: List[int]) -> int:
3        # Starting the search from second element to second last element
4        # because the peak can't be the first or last element.
5        left_index, right_index = 1, len(arr) - 2
6      
7        # Use binary search to find the peak element
8        while left_index < right_index:
9            # Calculate the middle index of the current subarray
10            mid_index = (left_index + right_index) // 2  # Use '//' for floor division in Python 3
11          
12            # If the middle element is greater than its next element,
13            # then the peak is in the left side of mid. Update the right_index.
14            if arr[mid_index] > arr[mid_index + 1]:
15                right_index = mid_index
16            else:
17                # If the middle element is less than its next element,
18                # then the peak is in the right side of mid. Update the left_index.
19                left_index = mid_index + 1
20      
21        # When left_index==right_index, we have found the peak index
22        return left_index
23

Java Solution

1class Solution {
2    public int peakIndexInMountainArray(int[] arr) {
3        // Initialize left and right pointers, excluding the first and last elements 
4        // because the peak cannot be at the ends of the array.
5        int left = 1; 
6        int right = arr.length - 2; 
7      
8        // Perform a binary search to find the peak element
9        while (left < right) {
10            // Calculate the middle index
11            int mid = left + (right - left) / 2;
12          
13            // If the middle element is greater than its successor,
14            // the peak is in the left half, including the mid element
15            if (arr[mid] > arr[mid + 1]) {
16                right = mid;
17            } else {
18                // If the middle element is less than or equal to its successor,
19                // the peak is in the right half
20                left = mid + 1;
21            }
22        }
23
24        // When left equals right, we have found the peak index
25        return left;
26    }
27}
28

C++ Solution

1#include <vector>
2
3class Solution {
4public:
5    // Function to find the peak index in a mountain array
6    int peakIndexInMountainArray(vector<int>& arr) {
7        // Initialize the search range within the array
8        int left = 1; // Starting from 1 because the peak cannot be the first element
9        int right = arr.size() - 2; // Ending at size - 2 because the peak cannot be the last element
10
11        // Continue searching as long as the left index is less than the right index
12        while (left < right) {
13            // Calculate the middle index using bitwise right shift (equivalent to dividing by 2)
14            int mid = (left + right) >> 1;
15
16            // If the middle element is greater than its next element,
17            // we are in the descending part of the mountain
18            // therefore, we continue to search on the left side
19            if (arr[mid] > arr[mid + 1]) {
20                right = mid;
21            } else {
22                // Else, we are in the ascending part of the mountain,
23                // we continue to search on the right side
24                left = mid + 1;
25            }
26        }
27
28        // Since 'left' and 'right' converge to the peak index,
29        // we return 'left' as the peak index of the mountain array
30        return left;
31    }
32};
33

Typescript Solution

1function peakIndexInMountainArray(arr: number[]): number {
2    // Initialize the search range within the boundaries of the potential peak.
3    // We avoid the first and last elements as they cannot be the peak.
4    let left = 1;
5    let right = arr.length - 2;
6
7    // Use binary search to find the peak of the mountain array.
8    while (left < right) {
9        // Calculate the mid index by shifting right bitwise by 1 (equivalent to dividing by 2).
10        const mid = left + ((right - left) >> 1);
11
12        // If the mid element is greater than its next element, we continue in the left portion.
13        // This is because the peak must be to the left of mid or at mid.
14        if (arr[mid] > arr[mid + 1]) {
15            right = mid;
16        } else {
17            // Otherwise, the peak lies to the right of mid, so we continue searching in the right portion.
18            left = mid + 1;
19        }
20    }
21    // After the loop, left will be pointing at the peak element's index
22    return left;
23}
24
Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer techniques do you use to check if a string is a palindrome?

Time and Space Complexity

The given Python code performs a binary search to find the peak index in a mountain array. The complexity analysis is:

  • Time Complexity: The while loop keeps halving the search interval until left and right meet. This halving process continues for at most O(log n) iterations, where n is the length of the array. Hence, the time complexity of this code is O(log n).

  • Space Complexity: The space complexity is O(1) because the code uses a fixed amount of additional memory (a few variables for left, right, and mid indices) regardless of the input array size.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫