#852

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Peak Index in a Mountain Array

Find the peak index in a mountain array using binary search for efficient O(log n) time complexity.

Problem Statement

Given a mountain array arr, where the values first strictly increase and then strictly decrease, you need to identify the index of the peak element. The peak is the element that is greater than its neighbors.

Your solution must be optimized to run in O(log n) time, making binary search the best fit for solving this problem. Implementing this search will allow you to quickly find the peak element by narrowing the search space with each comparison.

Examples

Example 1

Input: arr = [0,1,0]

Output: 1

Example details omitted.

Example 2

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

Output: 1

Example details omitted.

Example 3

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

Output: 1

Example details omitted.

Constraints

3 <= arr.length <= 105
0 <= arr[i] <= 106
arr is guaranteed to be a mountain array.

Solution Approach

Binary Search

The key to solving this problem is binary search, which enables us to efficiently find the peak element in O(log n) time. Start by checking the middle element and compare it with its neighbors. If the middle element is greater than both neighbors, it's the peak; if it's smaller than the right neighbor, the peak must be on the right side, and if smaller than the left, the peak must be on the left.

Search Space Reduction

Each iteration of binary search halves the search space, allowing us to focus only on the portion of the array where the peak could be. This method ensures that we reduce the problem size at every step, making the solution very efficient.

Edge Case Considerations

Since the array is guaranteed to be a mountain array, the first and last elements are not the peak. Ensure that the algorithm avoids unnecessary checks on these boundaries. Additionally, handle small arrays (length 3) where the peak is easily identifiable.

Complexity Analysis

Metric	Value
Time	O(\log n)
Space	O(1)

The time complexity is O(log n) due to the binary search approach, which halves the search space on each step. The space complexity is O(1) because no additional space is needed aside from a few variables for the search process.

What Interviewers Usually Probe

The candidate effectively applies binary search to reduce the problem size at each step.
The solution minimizes time complexity, showing understanding of O(log n) algorithms.
The candidate considers edge cases and correctly narrows the search space.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the search direction: always ensure the search space is narrowed toward the correct half (left or right) based on comparisons.
Forgetting to check both neighbors of the middle element before concluding that it is the peak.
Handling arrays with fewer than 3 elements incorrectly, even though the problem guarantees a valid mountain array.

Follow-up variants

What if the mountain array was allowed to contain equal adjacent elements? Would binary search still work?
Can the solution be adapted for an unsorted array?
How would the approach change if the peak element could be at the ends of the array?

FAQ

How can binary search help in finding the peak index in a mountain array?

Binary search allows you to narrow down the search space at each step, reducing the problem size logarithmically until you find the peak index.

What is the time complexity of solving the Peak Index in a Mountain Array problem?

The time complexity is O(log n), as binary search is used to efficiently find the peak element.

What are the edge cases for this problem?

Edge cases include very small arrays (length 3) and arrays where the peak is not at the boundary but is still correctly identified using binary search.

Can the solution handle arrays with more than one peak?

The problem guarantees a valid mountain array with only one peak, so the solution assumes only one peak element exists.

What other patterns could be applied to the Peak Index in a Mountain Array problem?

Aside from binary search, a linear scan would be another approach, but it would not meet the O(log n) time complexity requirement.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        left, right = 1, len(arr) - 2
        while left < right:
            mid = (left + right) >> 1
            if arr[mid] > arr[mid + 1]:
                right = mid
            else:
                left = mid + 1
        return left

Continue Practicing

#862 shortest subarray with sum at least k #875 koko eating bananas #826 most profit assigning work