Scale Engineer

Peak Index in a Mountain Array

Med
#0806Time: O(n), where n is the number of elements in the array. In the worst-case scenario (e.g., `[0, 1, 2, ..., n-2, n-3]`), we might have to traverse almost the entire array to find the peak.Space: O(1), as we only use a few variables to store the index, requiring constant extra space.4 companies
Algorithms
Binary Search
Data structures
Array
Companies
AccentureByteDancetcsDE Shaw

Prompt

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 <= 105
  • 0 <= arr[i] <= 106
  • arr is guaranteed to be a mountain array.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through the array to find the peak element. A peak element is one that is greater than its immediate neighbors. Since the array is guaranteed to be a mountain array (strictly increasing then strictly decreasing), we can find the peak by identifying the first element that is greater than the next one.

Algorithm

  • Iterate through the array arr with an index i from 0 to arr.length - 2. * In each iteration, check if arr[i] > arr[i+1]. * If this condition is true, it means we have just passed the peak. The peak is at index i. Return i.

Walkthrough

We can traverse the array from the beginning. The peak is the highest point, so the elements increase up to the peak and then decrease. This means the peak is the first element arr[i] for which arr[i] > arr[i+1]. We can iterate from the first element up to the second-to-last element and check this condition. The first time this condition is met, we have found our peak index and can return it immediately. Because the problem guarantees a mountain array of at least length 3, a peak is guaranteed to exist and will be found by this method.

class Solution {    public int peakIndexInMountainArray(int[] arr) {        for (int i = 0; i < arr.length - 1; i++) {            if (arr[i] > arr[i+1]) {                return i;            }        }        return -1; // Should not be reached given the problem constraints    }}

Complexity

Time

O(n), where n is the number of elements in the array. In the worst-case scenario (e.g., `[0, 1, 2, ..., n-2, n-3]`), we might have to traverse almost the entire array to find the peak.

Space

O(1), as we only use a few variables to store the index, requiring constant extra space.

Trade-offs

Pros

  • Very simple to understand and implement.

  • Requires no complex logic.

Cons

  • Inefficient for large arrays as it has a linear time complexity.

  • Does not meet the O(log n) time complexity requirement specified in the problem description.

Solutions

class Solution {public  int peakIndexInMountainArray(int[] arr) {    int left = 1, right = arr.length - 2;    while (left < right) {      int mid = (left + right) >> 1;      if (arr[mid] > arr[mid + 1]) {        right = mid;      } else {        left = mid + 1;      }    }    return left;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem