Problem

An array arr a mountain if the following properties hold:

  • arr.length >= 3
  • There exists some i with 0 < i < arr.length - 1 such that:
    • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
    • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given a mountain array arr, return the index i such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

You must solve it in O(log(arr.length)) time complexity.

Examples

Example 1:

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

Example 2:

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

Example 3:

Input: arr = [2, 4, 6, 8, 10, 3, 1]
Output: 4

Follow up

What if array is not bitonic array, but sorted. For eg.:

Example 4:

# Edge case (No decreasing part)
Input: arr = [10, 20, 30, 40, 50]
Output: 4

Example 5:

# Edge case (No increasing part)
Input: arr = [100, 80, 60, 40, 20, 0]
Output: 0

Solution

Method 1 - Linear Search

Navigate the array and track the element from where array starts decreasing. Time Complexity: O(n)

Method 2 - Binary Search

If you examine the examples, you’ll see that the maximum element is the only one greater than both its adjacent elements.

Here’s the modified Binary Search algorithm to find the maximum element:

  • If the middle element is greater than both its adjacent elements, it’s the maximum, so return it.
  • If the middle element is greater than the next element but smaller than the previous one, the maximum is on the left side of the middle. For example, in [2, 12, 10, 7, 5, 3].
  • If the middle element is greater than the previous element but smaller than the next one, the maximum is on the right side of the middle. For instance, in [2, 4, 6, 8, 10, 3, 1].

Code

Java
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] > arr[mid + 1]) {
                // Peak must be in the left half, including mid
                right = mid;
            } else {
                // Peak must be in the right half, excluding mid
                left = mid + 1;
            }
        }

        // Left (or right) will be the index of the peak element
        return left;
    }
}
Python
class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        left, right = 0, len(arr) - 1

        while left < right:
            mid = (left + right) // 2

            if arr[mid] > arr[mid + 1]:
                # Peak must be in the left half, including mid
                right = mid
            else:
                # Peak must be in the right half, excluding mid
                left = mid + 1

        # Left (or right) will be the index of the peak element
        return left

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(1)