1095. Find in Mountain Array - Explanation

Description

(This problem is an interactive problem.)

An array arr is called a mountain array if and only if:

arr.length >= 3
There exists some index 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 are given a mountain array mountainArr and an integer target, return the minimum index such that mountainArr.get(index) == target. If such an index does not exist, return -1.

You cannot access the mountain array directly. You may only access the array using a MountainArray interface:

MountainArray.get(k) returns the element of the array at index k (0-indexed).
MountainArray.length() returns the length of the array.

You can only make at most 100 calls to the function get(). Submissions making more than 100 calls will be judged as Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

Example 1:

Input: mountainArr = [2,4,5,2,1], target = 2

Output: 0

Example 2:

Input: mountainArr = [1,2,3,4,2,1], target = 6

Output: -1

Constraints:

3 <= mountainArr.length() <= 10,000
0 <= target, mountainArr.get(index) <= 1,000,000,000

1. Brute Force

Intuition

The simplest approach is to scan through the mountain array from left to right. Since we need the minimum index, returning the first occurrence guarantees the correct answer. This works because a linear scan naturally encounters smaller indices first.

Algorithm

Get the length of the mountain array.
Iterate through each index from 0 to n - 1.
For each index, call get(i) and compare with the target.
Return the index immediately upon finding a match.
If no match is found after the full scan, return -1.

# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
#    def get(self, index: int) -> int:
#    def length(self) -> int:

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

        for i in range(n):
            if mountainArr.get(i) == target:
                return i

        return -1

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

2. Binary Search

Intuition

A mountain array has a peak element with strictly increasing values to its left and strictly decreasing values to its right. This structure allows us to use binary search three times: first to find the peak, then to search the ascending left portion, and finally the descending right portion. We search the left side first because we need the minimum index, and values on the left have smaller indices than equivalent values on the right.

Algorithm

Find the peak: Use binary search comparing mid with its neighbors. If values are increasing, search right; if decreasing, search left; otherwise, we found the peak.
Search the ascending portion (indices 0 to peak): Standard binary search where smaller values are on the left.
If found in step 2, return that index (it will be the minimum index).
Search the descending portion (indices peak to n - 1): Modified binary search where smaller values are on the right.
Return the result from step 4, or -1 if not found.

# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
#    def get(self, index: int) -> int:
#    def length(self) -> int:

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

        # Find Peak
        l, r = 1, length - 2
        while l <= r:
            m = (l + r) // 2
            left, mid, right = mountainArr.get(m - 1), mountainArr.get(m), mountainArr.get(m + 1)
            if left < mid < right:
                l = m + 1
            elif left > mid > right:
                r = m - 1
            else:
                break
        peak = m

        # Search left portion
        l, r = 0, peak - 1
        while l <= r:
            m = (l + r) // 2
            val = mountainArr.get(m)
            if val < target:
                l = m + 1
            elif val > target:
                r = m - 1
            else:
                return m

        # Search right portion
        l, r = peak, length - 1
        while l <= r:
            m = (l + r) // 2
            val = mountainArr.get(m)
            if val > target:
                l = m + 1
            elif val < target:
                r = m - 1
            else:
                return m

        return -1

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

3. Binary Search + Caching

Intuition

The MountainArray API may have limited calls or expensive operations. During peak-finding, we query values at mid - 1, mid, and mid + 1, and some of these indices may be queried again in subsequent binary searches. By caching previously retrieved values, we avoid redundant API calls. This is particularly useful when the peak-finding phase overlaps with the search regions.

Algorithm

Create a cache (hash map) to store retrieved values.
Implement a cached get function that checks the cache before calling the API.
Find the peak using binary search with the cached getter.
Implement a generic binary search helper that takes an ascending parameter to handle both increasing and decreasing portions.
Search the ascending left portion first; if found, return immediately.
Search the descending right portion and return the result.

# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
#    def get(self, index: int) -> int:
#    def length(self) -> int:

class Solution:
    def findInMountainArray(self, target: int, mountainArr: 'MountainArray') -> int:
        length = mountainArr.length()
        cache = {}

        def get(i):
            if i not in cache:
                cache[i] = mountainArr.get(i)
            return cache[i]

        # Find Peak
        l, r = 1, length - 2
        while l <= r:
            m = (l + r) >> 1
            left, mid, right = get(m - 1), get(m), get(m + 1)
            if left < mid < right:
                l = m + 1
            elif left > mid > right:
                r = m - 1
            else:
                break
        peak = m

        def binary_search(l, r, ascending):
            while l <= r:
                m = (l + r) >> 1
                val = get(m)
                if val == target:
                    return m
                if ascending == (val < target):
                    l = m + 1
                else:
                    r = m - 1
            return -1

        # Search left portion
        res = binary_search(0, peak, True)
        if res != -1:
            return res

        # Search right portion
        return binary_search(peak, length - 1, False)

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(\log n)$

Common Pitfalls

Searching Right Side Before Left Side

Since the problem requires returning the minimum index when the target appears multiple times, you must search the ascending (left) portion first. If you search the descending (right) portion first or return the first match found without considering index order, you may return a larger index when a smaller one exists.

Incorrect Binary Search Direction for Descending Portion

When searching the descending right portion of the mountain, the binary search logic must be reversed. In an ascending array, smaller values are on the left; in a descending array, smaller values are on the right. Forgetting to flip the comparison logic will cause the search to move in the wrong direction.

Off-by-One Errors in Peak Finding

When finding the peak, the search bounds should be [1, length - 2] to ensure safe access to mid - 1 and mid + 1. Using [0, length - 1] can cause index out of bounds errors. Additionally, ensure the peak is correctly identified as the element greater than both neighbors, not just one.

Exceeding API Call Limits

The problem often restricts the number of get() calls (e.g., 100 calls). Without caching, you may query the same index multiple times during peak finding and subsequent searches. Implementing a cache to store previously retrieved values prevents exceeding the call limit and avoids time limit issues.

Not Handling Target at Peak Position

The target might be at the peak itself. If your left portion search excludes the peak and your right portion search also misses it due to boundary conditions, the target at the peak will never be found. Ensure at least one of your searches includes the peak index in its range.