LeetCode 1095: Find in Mountain Array

Problem Restatement

A mountain array increases to a peak and then decreases. We have access only through a MountainArray.get(index) API.

We need to find the minimum index where mountainArr.get(index) == target. Return -1 if not found.

We may call MountainArray.get() at most 100 times.

The official constraints state that 3 <= mountainArr.length() <= 10^4 and all values are distinct.

Input and Output

Function shape:

def findInMountainArray(target: int, mountain_arr: 'MountainArray') -> int:
    ...

Key Insight

Three binary searches:

1. Find the peak index.
2. Binary search the ascending left side for target.
3. If not found, binary search the descending right side for target.
4. Return the smaller index (prefer the left side result).

Algorithm

Find peak: binary search for the index where get(mid) > get(mid+1).

Search ascending: standard binary search.

Search descending: binary search where the comparison is reversed.

Correctness

The peak divides the array into an ascending and descending half. Binary search on each half correctly finds the target (if present) with O(log n) queries each.

Total queries: 3 * O(log n) ≤ 3 * 14 = 42, well within 100.

Edge Cases

• Check the smallest and largest valid search values; off-by-one errors usually appear at the boundaries.
• Decide whether the predicate is looking for the first true value, the last true value, or an exact match.
• When the target is absent, the loop should still terminate and return the problem-specific failure value.

Complexity

Common Pitfalls

• Do not mix inclusive and half-open bounds inside the same loop.
• Make sure each branch strictly reduces the search interval.

Implementation

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

        lo, hi = 0, n - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                lo = mid + 1
            else:
                hi = mid
        peak = lo

        lo, hi = 0, peak
        while lo <= hi:
            mid = (lo + hi) // 2
            val = mountain_arr.get(mid)
            if val == target:
                return mid
            elif val < target:
                lo = mid + 1
            else:
                hi = mid - 1

        lo, hi = peak, n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            val = mountain_arr.get(mid)
            if val == target:
                return mid
            elif val > target:
                lo = mid + 1
            else:
                hi = mid - 1

        return -1

Testing

class MountainArray:
    def __init__(self, arr): self.arr = arr
    def get(self, index): return self.arr[index]
    def length(self): return len(self.arr)

def run_tests():
    s = Solution()

    assert s.findInMountainArray(3, MountainArray([1,2,3,4,5,3,1])) == 2
    assert s.findInMountainArray(3, MountainArray([0,1,2,4,2,1])) == -1
    assert s.findInMountainArray(1, MountainArray([1,2,3,4,5,3,1])) == 0

    print("all tests passed")

run_tests()