Taro Logo

Peak Index in a Mountain Array

Medium
Meta logo
Meta
2 views
Topics:
ArraysBinary Search

You are given an integer mountain array arr of length n where the values increase to a peak element and then decrease. Your task is to find the index of the peak element in the array. The peak element is defined as the element which is greater than both of its neighbors.

Constraints:

  • 3 <= arr.length <= 10^5
  • 0 <= arr[i] <= 10^6
  • arr is guaranteed to be a mountain array.

Your solution must have O(log(n)) time complexity.

Examples:

  1. Input: arr = [0,1,0] Output: 1
  2. Input: arr = [0,2,1,0] Output: 1
  3. Input: arr = [0,10,5,2] Output: 1

Can you implement an algorithm to efficiently find the index of the peak element in the mountain array?

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the minimum possible length of the array `arr`? Is it guaranteed to have at least three elements?
  2. What is the range of possible values for the elements within the array `arr`? Are negative numbers allowed?
  3. Is it guaranteed that there is only one peak, meaning that the condition arr[i-1] < arr[i] > arr[i+1] holds for only one index i?
  4. If there are multiple indices that *could* be considered a peak due to floating point imprecision (unlikely, but good to check), which index should be returned?
  5. Can I assume the input array always conforms to the mountain array property, or should my solution handle cases where this property is violated (e.g., a plateau or a decreasing-then-increasing sequence)?

Brute Force Solution

Approach

The brute force strategy for finding the peak in a mountain essentially looks at every single spot to see if it is the highest point. We check each position by comparing it to its neighbors, one at a time, until we find the peak.

Here's how the algorithm would work step-by-step:

  1. Start by examining the very first value.
  2. Compare this value to the value right next to it.
  3. If the first value is bigger, then it's the peak, and you're done!
  4. If not, move to the next value in the list.
  5. Now, compare this value to both of its neighbors: the one before it and the one after it.
  6. If this value is bigger than both its neighbors, then it's the peak!
  7. If not, keep moving to the next value and repeating the comparison.
  8. Continue this process until you find a value that is bigger than both of its neighbors. This is the peak.

Code Implementation

def find_peak_in_mountain_array_brute_force(mountain):
    array_length = len(mountain)

    # Check if the first element is the peak
    if mountain[0] > mountain[1]:
        return 0

    for current_index in range(1, array_length - 1):
        # This condition checks if the current element is greater than its neighbors
        if mountain[current_index] > mountain[current_index - 1] and \
           mountain[current_index] > mountain[current_index + 1]:

            return current_index

        # Check if the last element is the peak
        if mountain[array_length - 1] > mountain[array_length - 2]:
            return array_length - 1

    return -1 #Should not happen if input is a mountain array

Big(O) Analysis

Time Complexity
O(n)The described algorithm iterates through the array, examining each element to determine if it's the peak. In the worst-case scenario, the algorithm needs to traverse almost the entire array to find the peak element because the peak could be at the very end. Since we visit each element at most once, the number of operations grows linearly with the input size n, where n is the number of elements in the array. Therefore, the time complexity is O(n).
Space Complexity
O(1)The algorithm described iterates through the array and compares elements. It does not create any auxiliary data structures like lists, maps, or sets. It only uses a fixed number of variables to store the current index and possibly the peak index. Therefore, the space used is constant and does not depend on the input size N.

Optimal Solution

Approach

We're trying to find the highest point in a sequence of numbers that goes up and then down. Instead of checking every number, we'll use a clever strategy to quickly narrow down our search.

Here's how the algorithm would work step-by-step:

  1. Look at the middle number in the sequence.
  2. Compare this middle number with the numbers right next to it.
  3. If the middle number is bigger than its neighbors, then we've found the highest point!
  4. If the middle number is smaller than the number to its right, this means the highest point is somewhere to the right of the middle number. We can ignore everything to the left and repeat the process on the right half.
  5. If the middle number is smaller than the number to its left, then the highest point is somewhere to the left of the middle number. We can ignore everything to the right and repeat the process on the left half.
  6. Keep repeating this process of looking at the middle and narrowing down the search until you find the highest point.

Code Implementation

def peak_index_in_mountain_array(arr):
    start_index = 0
    end_index = len(arr) - 1

    while start_index < end_index:
        middle_index = (start_index + end_index) // 2

        # Check if middle element is the peak
        if arr[middle_index] > arr[middle_index - 1] and arr[middle_index] > arr[middle_index + 1]:
            return middle_index

        # If middle element is smaller than the next element,
        # peak is in the right half
        if arr[middle_index] < arr[middle_index + 1]:
            start_index = middle_index + 1

        # Otherwise, the peak is in the left half
        else:
            end_index = middle_index

    return start_index

Big(O) Analysis

Time Complexity
O(log n)The algorithm uses a binary search approach to find the peak element. In each step, it divides the search space in half by comparing the middle element with its neighbors. Therefore, the number of iterations is proportional to the logarithm base 2 of the input array size (n). Hence, the time complexity is O(log n).
Space Complexity
O(1)The algorithm iteratively narrows down the search range using two pointers or indices to keep track of the left and right boundaries. The space required for these pointers and any temporary variables used for comparisons does not depend on the size of the input array. Therefore, the space complexity remains constant, regardless of the input size N.

Edge Cases

CaseHow to Handle
Null or empty arrayThrow an IllegalArgumentException or return -1, indicating invalid input.
Array with only one elementThrow an IllegalArgumentException or return -1, as a mountain array requires at least three elements.
Array with only two elementsThrow an IllegalArgumentException or return -1, as a mountain array requires at least three elements.
Array where the peak is the first elementThe binary search should naturally converge to the correct index in this case as left boundary is never the peak.
Array where the peak is the last elementThe binary search should naturally converge to the correct index in this case as right boundary is never the peak.
Array with a very large number of elements (performance considerations)Binary search ensures logarithmic time complexity, scaling well with large inputs.
Array containing negative numbers or zerosThe binary search approach works regardless of whether the numbers are negative or zero, as it relies on the increasing/decreasing property.
Integer overflow when calculating the middle index for very large arraysCalculate the middle index using mid = left + (right - left) / 2 to prevent overflow.