Problem Description

This is an interactive problem where you need to find a target value in a mountain array with limited access.

A mountain array is defined as an array that:

• Has at least 3 elements
• Has a peak element at some index i (where 0 < i < arr.length - 1)
• Strictly increases from the start to the peak: arr[0] < arr[1] < ... < arr[i]
• Strictly decreases from the peak to the end: arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

You're given a MountainArray object and a target value. Your task is to find and return the minimum index where mountainArr.get(index) == target. If the target doesn't exist in the array, return -1.

The catch is that you cannot directly access the array. You can only use two methods:

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

There's a constraint: your solution must make no more than 100 calls to MountainArray.get(), otherwise it will be judged as Wrong Answer.

The solution uses a two-phase approach:

1. Find the peak: Uses binary search to locate the peak of the mountain array by comparing adjacent elements. If get(mid) > get(mid + 1), the peak is at or before mid; otherwise, it's after mid.

2. Search for target: Once the peak is found, the array is divided into two parts:

   • The ascending part (from start to peak): Regular binary search
   • The descending part (from peak+1 to end): Binary search with reversed comparison logic

The clever use of the parameter k (1 or -1) in the search function allows the same binary search logic to work for both ascending and descending portions by multiplying the comparison values by k.

Intuition

The key insight is recognizing that a mountain array has special properties we can exploit. Since we have a strict limit on the number of calls (100), we need an efficient approach - this immediately suggests binary search, which runs in O(log n) time.

The mountain array essentially consists of two sorted sequences joined at a peak: one ascending and one descending. If we can find the peak, we can treat each side as a sorted array and apply binary search.

Why find the peak first? Without knowing where the peak is, we can't determine which "side" of the mountain we're on when we find an element. The comparison logic differs between the ascending side (where larger indices mean larger values) and the descending side (where larger indices mean smaller values).

To find the peak efficiently, we observe that at any point in the array:

• If arr[mid] > arr[mid + 1], we're on the descending side or at the peak itself, so the peak must be at position mid or earlier
• If arr[mid] < arr[mid + 1], we're on the ascending side, so the peak must be after position mid

This allows us to binary search for the peak in O(log n) calls.

Once we have the peak, searching for the target becomes straightforward - we perform binary search on the ascending portion first (since we want the minimum index). If not found there, we search the descending portion.

The elegant trick in the code is using a multiplier k (1 for ascending, -1 for descending) to unify the binary search logic. By multiplying both the current element and target by k, we convert the descending search into an ascending one: in the descending portion, smaller values are actually "greater" in terms of their position from the peak, so multiplying by -1 reverses the comparison appropriately.

This approach ensures we use at most 3 * log n calls to get(): one binary search to find the peak, and potentially two more to search both sides, well within the 100-call limit.

Learn more about Binary Search patterns.

Solution Approach

The implementation consists of two main parts: finding the peak and searching for the target.

Step 1: Find the Peak

l, r = 0, n - 1
while l < r:
    mid = (l + r) >> 1
    if mountain_arr.get(mid) > mountain_arr.get(mid + 1):
        r = mid
    else:
        l = mid + 1

We use binary search with pointers l and r starting at the array boundaries. At each iteration:

• Calculate mid = (l + r) >> 1 (bit shift for integer division)
• Compare mountain_arr.get(mid) with mountain_arr.get(mid + 1)
• If get(mid) > get(mid + 1), we're on the descending side or at the peak, so move r = mid
• Otherwise, we're on the ascending side, so move l = mid + 1

When the loop exits, l points to the peak index.

Step 2: Binary Search Helper Function

def search(l: int, r: int, k: int) -> int:
    while l < r:
        mid = (l + r) >> 1
        if k * mountain_arr.get(mid) >= k * target:
            r = mid
        else:
            l = mid + 1
    return -1 if mountain_arr.get(l) != target else l

This helper function performs binary search on a given range [l, r]. The parameter k controls the search direction:

• k = 1 for ascending portion: normal binary search
• k = -1 for descending portion: reverses the comparison logic

The key insight is k * mountain_arr.get(mid) >= k * target:

• For ascending (k = 1): this becomes get(mid) >= target
• For descending (k = -1): this becomes -get(mid) >= -target, which is equivalent to get(mid) <= target

This multiplication trick allows us to use the same binary search logic for both ascending and descending sequences.

Step 3: Search for Target

ans = search(0, l, 1)
return search(l + 1, n - 1, -1) if ans == -1 else ans

First, search the ascending portion [0, l] with k = 1. If found, return immediately (since we want the minimum index). If not found (ans == -1), search the descending portion [l + 1, n - 1] with k = -1.

Time Complexity: O(log n) - We perform at most three binary searches, each taking O(log n) time.

Space Complexity: O(1) - Only using a constant amount of extra space for variables.

API Calls: Maximum 3 * log n calls to mountain_arr.get(), well within the 100-call limit for reasonable array sizes.

Example Walkthrough

Let's walk through the solution with a concrete example:

Mountain Array: [1, 3, 5, 7, 6, 4, 2]
Target: 4
Expected Output: 5 (index where 4 is located)

Step 1: Find the Peak

We start with l = 0, r = 6 (array length - 1).

Iteration 1:

• mid = (0 + 6) >> 1 = 3
• Compare get(3) = 7 with get(4) = 6
• Since 7 > 6, we're on the descending side or at peak
• Update r = 3

Iteration 2:

• l = 0, r = 3
• mid = (0 + 3) >> 1 = 1
• Compare get(1) = 3 with get(2) = 5
• Since 3 < 5, we're on the ascending side
• Update l = 2

Iteration 3:

• l = 2, r = 3
• mid = (2 + 3) >> 1 = 2
• Compare get(2) = 5 with get(3) = 7
• Since 5 < 7, we're on the ascending side
• Update l = 3

Now l = r = 3, so the peak is at index 3 with value 7.

Step 2: Search for Target = 4

Search ascending portion [0, 3] with k = 1:

• l = 0, r = 3
• mid = 1: 1 * get(1) = 3 vs 1 * 4 = 4
  • Since 3 < 4, update l = 2
• l = 2, r = 3
• mid = 2: 1 * get(2) = 5 vs 1 * 4 = 4
  • Since 5 >= 4, update r = 2
• Now l = r = 2, check get(2) = 5 ≠ 4
• Return -1 (not found in ascending portion)

Search descending portion [4, 6] with k = -1:

• l = 4, r = 6
• mid = 5: -1 * get(5) = -4 vs -1 * 4 = -4
  • Since -4 >= -4, update r = 5
• Now l = 4, r = 5
• mid = 4: -1 * get(4) = -6 vs -1 * 4 = -4
  • Since -6 < -4, update l = 5
• Now l = r = 5, check get(5) = 4 = 4 ✓
• Return 5

Final Answer: 5

The solution efficiently found the target using only 10 calls to get(): 3 to find the peak, 3 for the ascending search, and 4 for the descending search.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n)

The algorithm consists of three binary search operations:

1. First binary search to find the peak element: O(log n) where each iteration makes 2 calls to mountain_arr.get()
2. Second binary search on the ascending part (left side): O(log n) where each iteration makes 1 call to mountain_arr.get()
3. Third binary search on the descending part (right side) - only executed if target not found in ascending part: O(log n) where each iteration makes 1 call to mountain_arr.get()

Since these searches are performed sequentially (not nested), the total time complexity is O(log n) + O(log n) + O(log n) = O(log n).

The total number of API calls to mountain_arr.get() is at most O(log n) calls.

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• A few integer variables (l, r, mid, n, ans)
• The search helper function which doesn't use recursion
• The parameter k in the search function

No additional data structures are created that scale with input size, making the space complexity constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error When Finding the Peak

A common mistake is incorrectly handling the boundary when finding the peak element. Developers often write:

# WRONG - May miss the peak or cause index out of bounds
while l <= r:  # Using <= instead of <
    mid = (l + r) // 2
    if mountain_arr.get(mid) > mountain_arr.get(mid + 1):
        r = mid - 1  # Wrong: might skip the peak
    else:
        l = mid + 1

Why it's wrong: Using r = mid - 1 could skip over the peak element entirely. When get(mid) > get(mid + 1), mid could be the peak itself, so we shouldn't exclude it.

Solution: Use while l < r and set r = mid (not mid - 1) to keep the peak in the search range:

# CORRECT
while l < r:
    mid = (l + r) // 2
    if mountain_arr.get(mid) > mountain_arr.get(mid + 1):
        r = mid  # Keep mid as potential peak
    else:
        l = mid + 1

2. Incorrect Binary Search Boundaries for Descending Portion

Another pitfall is using the wrong starting index when searching the descending portion:

# WRONG - Including peak twice
result = binary_search(0, peak_index, 1)  # Search ascending
if result == -1:
    result = binary_search(peak_index, array_length - 1, -1)  # Wrong: peak_index instead of peak_index + 1

Why it's wrong: The peak element is already checked when searching the ascending portion. Including it again in the descending search wastes an API call and could lead to incorrect results if the binary search implementation doesn't handle edge cases properly.

Solution: Start the descending search from peak_index + 1:

# CORRECT
result = binary_search(0, peak_index, 1)
if result == -1:
    result = binary_search(peak_index + 1, array_length - 1, -1)

3. Forgetting to Check Array Length Edge Cases

Not handling arrays with minimum length (3 elements) properly:

# WRONG - May fail for small arrays
def binary_search(left: int, right: int, ascending: int) -> int:
    while left < right:
        # ... binary search logic
    # Forgot to handle case where left > right initially

Why it's wrong: When searching the descending portion of a 3-element array where the peak is at index 2, the descending search range would be [3, 2], making left > right initially.

Solution: Add a check before or during the search:

# CORRECT
def binary_search(left: int, right: int, ascending: int) -> int:
    if left > right:  # Handle empty range
        return -1
    while left < right:
        # ... rest of binary search

4. Misunderstanding the Multiplication Trick for Descending Search

Incorrectly implementing the comparison for descending arrays:

# WRONG - Incorrect comparison logic
if ascending == 1:
    if mountain_arr.get(mid) >= target:
        right = mid
    else:
        left = mid + 1
else:  # ascending == -1
    if mountain_arr.get(mid) <= target:  # Wrong logic
        right = mid
    else:
        left = mid + 1

Why it's wrong: This doesn't correctly handle the binary search for descending arrays. In a descending array, when get(mid) <= target, we should search the left half (larger values), not maintain the same logic as ascending.

Solution: Use the multiplication trick consistently:

# CORRECT
if ascending * mountain_arr.get(mid) >= ascending * target:
    right = mid
else:
    left = mid + 1

This automatically handles both cases:

• Ascending (ascending = 1): get(mid) >= target
• Descending (ascending = -1): -get(mid) >= -target → get(mid) <= target