We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Peak Index in a Mountain Array

Number: 882

Difficulty: Medium

Paid? No

Companies: Google, Meta, Bloomberg, Amazon, DE Shaw, Adobe, Apple, Uber, Yahoo, Accenture

Problem Description

Given a mountain array (an array where values first strictly increase to a peak element then strictly decrease), find and return the index of the peak element. The solution must have O(log(n)) time complexity.

Key Insights

  • The array is strictly increasing up to a peak and then strictly decreasing.
  • A binary search technique is applicable because the array exhibits a single transition point (peak) between increasing and decreasing order.
  • By comparing mid and mid+1, we can decide which half of the array to continue the search in.

Space and Time Complexity

Time Complexity: O(log(n)) - The binary search approach reduces the search interval by half at each step. Space Complexity: O(1) - Only constant extra space is used.

Solution

We use a binary search strategy:

  • Initialize two pointers, left and right, at the beginning and end of the array.
  • In each iteration, calculate mid. If arr[mid] is less than arr[mid + 1], then the peak is in the right half; otherwise, it is in the left half.
  • When left equals right, we have found the peak index. This approach leverages the mountain array properties and ensures an O(log(n)) solution.

Code Solutions

def peakIndexInMountainArray(arr):
    # Initialize pointers for the binary search
    left, right = 0, len(arr) - 1
    # Continue while there is more than one element in the search space
    while left < right:
        mid = (left + right) // 2  # Find the mid index
        # If the sequence is still increasing, move the left pointer to mid+1
        if arr[mid] < arr[mid + 1]:
            left = mid + 1
        else:
            # Otherwise, the peak is at mid or to the left of mid
            right = mid
    # When left and right converge, we have the peak index
    return left

# Example usage:
# print(peakIndexInMountainArray([0, 1, 0]))  # Output: 1
← Back to All Questions