How do you solve Peak Index in a Mountain Array on LeetCode?

Peak Index in a Mountain Array (LeetCode #852) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log n) time complexity and O(1) space complexity. Key insight: The peak element is always greater than its neighbors in a mountain array.

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

The optimal solution for Peak Index in a Mountain Array runs in O(log n) time and uses O(1) space. This complexity is achieved because we are halving the search space with each iteration, characteristic of binary search.

What is the brute force solution for Peak Index in a Mountain Array?

The brute force approach for Peak Index in a Mountain Array is Brute Force, with O(n) time complexity and O(1) space complexity. The simplest way to find the peak is to check each element and see if it is greater than its neighbors. If it is, we've found our peak. This method is straightforward but inefficient for larger arrays. The optimal Optimal Solution approach improves this to O(log n).

What algorithm or data structure is used to solve Peak Index in a Mountain Array?

Peak Index in a Mountain Array uses the following concepts: Array, Binary Search. The recommended patterns to study are: Binary Search, Array.

What are the interview tips for Peak Index in a Mountain Array?

Always clarify the constraints and properties of the input array. Discuss your thought process and approach before jumping into coding. Test your solution with edge cases to ensure robustness.

What are common mistakes when solving Peak Index in a Mountain Array?

Not checking the bounds of the array when accessing neighbors. Confusing the conditions for moving left or right in binary search.

#852

Peak Index in a Mountain Array

Medium

ArrayBinary SearchBinary SearchArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n)	O(log n)
Space	O(1)	O(1)

💡

Intuition

Time O(log n)Space O(1)

We can leverage the properties of a mountain array using binary search. Since the array first increases and then decreases, we can eliminate half of the search space based on the relationship between the middle element and its neighbors.

⚙️

Algorithm

5 steps

1Step 1: Initialize two pointers, left = 0 and right = n - 1.
2Step 2: While left < right, calculate mid = (left + right) // 2.
3Step 3: If arr[mid] < arr[mid + 1], it means the peak is on the right side, so set left = mid + 1.
4Step 4: Otherwise, the peak is on the left side or at mid, so set right = mid.
5Step 5: When left equals right, return left (or right) as the peak index.

solution.py11 lines

1# Full working Python code
2
3def peakIndexInMountainArray(arr):
4    left, right = 0, len(arr) - 1
5    while left < right:
6        mid = (left + right) // 2
7        if arr[mid] < arr[mid + 1]:
8            left = mid + 1
9        else:
10            right = mid
11    return left

ℹ

Complexity note: This complexity is achieved because we are halving the search space with each iteration, characteristic of binary search.

1The peak element is always greater than its neighbors in a mountain array.
2Binary search is effective for problems with a sorted or partially sorted structure.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.