Hard

Find in Mountain Array

LAB

Given a mountain array and target, return the smallest index containing target, or -1.

EXAMPLES

Example 1

Input
{
  "mountainArr": [
    1,
    2,
    3,
    4,
    5,
    3,
    1
  ],
  "target": 3
}

Output
2

FUNCTION SHAPE

mountainArr: intArraytarget: int→int

SOLUTION NOTE

Three binary searches: (1) find peak, (2) search ascending left half, (3) search descending right half. For descending, flip the comparison.

Reveal reference solution +

pythonREFERENCE

def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
    n = mountain_arr.length()

    # Step 1: Find peak using Q162 approach
    left, right = 0, n - 1
    while left < right:
        mid = ceil(left + (right - left) / 2)
        if mountain_arr.get(mid - 1) <= mountain_arr.get(mid):
            left = mid
        else:
            right = mid - 1
    peak = left

    # Step 2: Binary search left side (ascending)
    left, right = 0, peak
    while left < right:
        mid = left + (right - left) // 2
        if mountain_arr.get(mid) >= target:
            right = mid
        else:
            left = mid + 1
    if mountain_arr.get(left) == target:
        return left

    # Step 3: Binary search right side (descending)
    left, right = peak, n - 1
    while left < right:
        mid = left + (right - left) // 2
        if mountain_arr.get(mid) <= target:
            right = mid
        else:
            left = mid + 1
    return left if mountain_arr.get(left) == target else -1

TimeO(log n)

SpaceO(1)

Open on LeetCode ↗