algoadvance

Given an array of integers arr that is a mountain array, return the peak index in the mountain array.

A mountain array is defined as an array that:

• 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]

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

Clarifying Questions

1. What should be returned when there are multiple peaks?
   • The problem guarantees a unique peak because of the definition of a mountain array.
2. Are there any constraints on the values of the array elements?
   • The array elements will be integers, but no specific range is given.
3. Can the input array have duplicate values?
   • Based on the definition of a mountain array, there should be no duplicates around the peak.

Strategy

To solve this problem efficiently in O(log(n)) time complexity, we can use a binary search approach. Here’s how:

• Initialize two pointers, left at the start of the array and right at the end of the array.
• While left is less than right:
  • Find the middle index mid.
  • If arr[mid] is less than arr[mid + 1], it means the peak is in the right half, so move left to mid + 1.
  • Otherwise, if arr[mid] is greater than or equal to arr[mid + 1], it means the peak is in the left half, so move right to mid.
• When the loop exits, left will be pointing at the peak index.

Code

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

Time Complexity

• Time Complexity: O(log(n)) because each step of the binary search cuts the search space in half.
• Space Complexity: O(1) because no additional space is used that scales with the input size.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?