Jobs

Interviews

Discussions

Peak Index in a Mountain Array

Medium

Asked by:

10 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.

Return the index of the peak element.

Your task is to solve it in O(log(n)) time complexity.

Example 1:

Input: arr = [0,1,0]

Output: 1

Example 2:

Input: arr = [0,2,1,0]

Output: 1

Example 3:

Input: arr = [0,10,5,2]

Output: 1

Constraints:

3 <= arr.length <= 10⁵
0 <= arr[i] <= 10⁶
arr is guaranteed to be a mountain array.

Peak Index in a Mountain Array

Medium

Asked by:

10 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.

Return the index of the peak element.

Your task is to solve it in O(log(n)) time complexity.

Example 1:

Input: arr = [0,1,0]

Output: 1

Example 2:

Input: arr = [0,2,1,0]

Output: 1

Example 3:

Input: arr = [0,10,5,2]

Output: 1

Constraints:

3 <= arr.length <= 10⁵
0 <= arr[i] <= 10⁶
arr is guaranteed to be a 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:

What is the minimum size of the mountain array, and can it be empty?
What is the range of values within the array, and can it contain negative numbers?
Is the array guaranteed to have only one peak, or could there be scenarios with multiple local peaks?
Can I assume that the input array is always valid, meaning it always strictly increases and then strictly decreases, or do I need to handle potential invalid input?
If the peak element appears multiple times consecutively, which index should I return?

Brute Force Solution

Approach

Imagine you are climbing a mountain and need to find the very top. The brute force way is like checking the height at every single point to find the highest one. It’s like going through every possible spot until you find the peak.

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

Start at the beginning of the mountain.
Check if the current spot is higher than the next spot.
If it is, then you've found the top! You are done.
If the current spot is lower than the next spot, move to the next spot and check again.
Keep doing this, going from one spot to the next, until you find a spot that's higher than the one immediately after it.

Code Implementation

def find_peak_index_brute_force(mountain_array):
    array_length = len(mountain_array)

    for current_index in range(array_length - 1):
        # We check if the current element is greater
        # than the next to identify the peak.
        if mountain_array[current_index] > mountain_array[current_index + 1]:

            return current_index

        #The current element is smaller than the next
        #We check if it's the last element, if so it is the peak
        if current_index == array_length - 2:
            return current_index + 1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the mountain array from the beginning until it finds an element that is greater than the next element. In the worst-case scenario, the peak is located at the very end of the array or close to it, requiring the algorithm to traverse almost all n elements where n is the number of elements in the array. Therefore, the time complexity is directly proportional to the input size n, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The provided algorithm iterates through the input array using a single index. It doesn't create any additional data structures like lists, dictionaries, or sets. The space used is limited to storing a few variables, such as the current index, which requires a constant amount of memory regardless of the input array's size (N). Therefore, the space complexity is O(1).

Optimal Solution

Approach

The optimal strategy is to use a method similar to searching in a phone book. Instead of checking each entry one by one, we repeatedly cut the possible search area in half until we find what we are looking for. This is much faster than looking at every single entry.

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

Look at the middle value to decide if the peak is on the left or right side.
If the value to the left of the middle value is bigger, the peak must be on the left side. Discard the right side.
If the value to the right of the middle value is bigger, the peak must be on the right side. Discard the left side.
Repeat the process on the remaining section (either left or right).
Keep narrowing down the section until you are left with just one value. This value is the peak.

Code Implementation

def peakIndexInMountainArray(arr):
    left_index = 0
    right_index = len(arr) - 1

    while left_index < right_index:
        middle_index = (left_index + right_index) // 2

        # Check if the peak is to the left of the middle index.
        if arr[middle_index - 1] > arr[middle_index]:

            right_index = middle_index

        # Check if the peak is to the right of the middle index.
        elif arr[middle_index + 1] > arr[middle_index]:

            left_index = middle_index + 1

        # Middle is peak if neither left nor right are bigger.
        else:

            return middle_index

    # When left and right meet, it's the peak.
    return left_index

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The algorithm uses a binary search approach to find the peak element in the mountain array. In each iteration, the search space is halved. The number of iterations is therefore proportional to the number of times n can be divided by 2 until it reaches 1. Hence, the time complexity is logarithmic with respect to the input size n, where n is the number of elements in the array. This halving leads to a time complexity of O(log n).

Space Complexity

O(1) – The algorithm repeatedly narrows down the search range using a binary search approach. It only requires storing a few index variables (e.g., for the left, right, and middle positions) to keep track of the current search boundaries. The number of index variables does not depend on the size of the input array, denoted as N. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Throw an IllegalArgumentException or return -1 to indicate invalid input.
Array with only one element	Throw an IllegalArgumentException or return -1 since it doesn't satisfy mountain array properties.
Array with two elements	Throw an IllegalArgumentException or return -1 as it cannot form a mountain.
Array with only increasing elements	Throw an IllegalArgumentException or return -1 because there is no peak.
Array with only decreasing elements	Throw an IllegalArgumentException or return -1 because there is no peak.
Integer overflow during calculation of mid index in binary search	Use mid = low + (high - low) / 2 to prevent potential overflow.
Large array size exceeding available memory	The binary search approach has logarithmic space complexity, so memory should not be a concern for typical input sizes.
Array with numbers at Integer.MAX_VALUE or Integer.MIN_VALUE	Handle carefully during comparison to prevent any integer overflow issues.

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:

What is the minimum size of the mountain array, and can it be empty?
What is the range of values within the array, and can it contain negative numbers?
Is the array guaranteed to have only one peak, or could there be scenarios with multiple local peaks?
Can I assume that the input array is always valid, meaning it always strictly increases and then strictly decreases, or do I need to handle potential invalid input?
If the peak element appears multiple times consecutively, which index should I return?

Brute Force Solution

Approach

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

Start at the beginning of the mountain.
Check if the current spot is higher than the next spot.
If it is, then you've found the top! You are done.
If the current spot is lower than the next spot, move to the next spot and check again.
Keep doing this, going from one spot to the next, until you find a spot that's higher than the one immediately after it.

Code Implementation

def find_peak_index_brute_force(mountain_array):
    array_length = len(mountain_array)

    for current_index in range(array_length - 1):
        # We check if the current element is greater
        # than the next to identify the peak.
        if mountain_array[current_index] > mountain_array[current_index + 1]:

            return current_index

        #The current element is smaller than the next
        #We check if it's the last element, if so it is the peak
        if current_index == array_length - 2:
            return current_index + 1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Look at the middle value to decide if the peak is on the left or right side.
If the value to the left of the middle value is bigger, the peak must be on the left side. Discard the right side.
If the value to the right of the middle value is bigger, the peak must be on the right side. Discard the left side.
Repeat the process on the remaining section (either left or right).
Keep narrowing down the section until you are left with just one value. This value is the peak.

Code Implementation

def peakIndexInMountainArray(arr):
    left_index = 0
    right_index = len(arr) - 1

    while left_index < right_index:
        middle_index = (left_index + right_index) // 2

        # Check if the peak is to the left of the middle index.
        if arr[middle_index - 1] > arr[middle_index]:

            right_index = middle_index

        # Check if the peak is to the right of the middle index.
        elif arr[middle_index + 1] > arr[middle_index]:

            left_index = middle_index + 1

        # Middle is peak if neither left nor right are bigger.
        else:

            return middle_index

    # When left and right meet, it's the peak.
    return left_index

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Throw an IllegalArgumentException or return -1 to indicate invalid input.
Array with only one element	Throw an IllegalArgumentException or return -1 since it doesn't satisfy mountain array properties.
Array with two elements	Throw an IllegalArgumentException or return -1 as it cannot form a mountain.
Array with only increasing elements	Throw an IllegalArgumentException or return -1 because there is no peak.
Array with only decreasing elements	Throw an IllegalArgumentException or return -1 because there is no peak.
Integer overflow during calculation of mid index in binary search	Use mid = low + (high - low) / 2 to prevent potential overflow.
Large array size exceeding available memory	The binary search approach has logarithmic space complexity, so memory should not be a concern for typical input sizes.
Array with numbers at Integer.MAX_VALUE or Integer.MIN_VALUE	Handle carefully during comparison to prevent any integer overflow issues.