(This problem is an interactive problem.)
You may recall that an array arr is a mountain array if and only if:
arr.length >= 3i 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]Given a mountain array mountainArr, 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.Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.
Example 1:
Input: mountainArr = [1,2,3,4,5,3,1], target = 3 Output: 2 Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.
Example 2:
Input: mountainArr = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 3 does not exist in the array, so we return -1.
Constraints:
3 <= mountainArr.length() <= 1040 <= target <= 1090 <= mountainArr.get(index) <= 109Problem Overview: You are given a mountain array where values strictly increase to a peak and then strictly decrease. The task is to find the index of a target value using only the provided MountainArray.get() API while minimizing calls to the array.
Approach 1: Brute-force Linear Scan (O(n) time, O(1) space)
The simplest strategy is to iterate through the array from index 0 to n - 1 and call get(i) for each position. If the returned value matches the target, return the index immediately. This approach works because every element is checked exactly once. However, the problem is interactive and restricts the number of API calls, so scanning the entire array can exceed the allowed limit for large inputs. Time complexity is O(n) and extra space is O(1). This approach mainly helps verify correctness before optimizing.
Approach 2: Binary Search with Peak Finding (O(log n) time, O(1) space)
A mountain array has two sorted regions: strictly increasing before the peak and strictly decreasing after it. First locate the peak index using binary search. Compare get(mid) with get(mid + 1). If the sequence is rising, move right; otherwise move left. This identifies the maximum element in O(log n) calls.
Once the peak is known, run two separate binary searches. Search the left side [0, peak] as a normal ascending array. If the target is not found, search the right side [peak + 1, n - 1] but reverse the comparison logic because that portion is descending. Each search takes O(log n), keeping the total time complexity O(log n) and space O(1).
This approach leverages the structural guarantee of a mountain array instead of scanning blindly. It also minimizes calls to the MountainArray interface, which is critical for interactive problems. The algorithm mainly relies on concepts from arrays and interactive problems where API usage is constrained.
Recommended for interviews: Binary search with peak finding is the expected solution. Interviewers want to see that you recognize the two monotonic segments and apply binary search correctly on both sides. Showing the brute-force scan first demonstrates baseline reasoning, but the optimized O(log n) approach proves you understand how to exploit problem structure.
In this approach, the task is broken into three main steps:
arr[i] > arr[i+1] and arr[i] > arr[i-1].This C implementation is efficient as it implements a binary search method to find the peak in O(log n) time. After finding the peak, it searches both halves of the mountain array for the target using two separate binary searches. One binary search is for the increasing part (left of the peak) with an increasing order binary search, and another one in the decreasing half (right of the peak) with a decreasing order binary search. As it is a binary search, each takes O(log n) time.
Time Complexity: O(log n) for peak finding and 2 * O(log n) for the two binary searches.
Total: O(log n).
Space Complexity: O(1) because we use a constant amount of space.
This approach involves directly accessing each element linearly until the condition is satisfied (even though this is not allowed by the problem constraints). It is less optimal and efficient compared to the above implementations, requiring traversal of the entire array.
The brute-force approach directly scans through the mountain array from the start to the finish, checking each element against the target. If an element equals the target, it returns the index. Otherwise, it returns -1. This basic method is straightforward but inefficient due to its time complexity.
Time Complexity: O(n) as each element could potentially be checked once.
Space Complexity: O(1) as no extra space is used except for variables.
| Approach | Complexity |
|---|---|
| Binary Search with Peak Finding | Time Complexity: |
| Brute-force Approach | Time Complexity: |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute-force Linear Scan | O(n) | O(1) | Quick baseline solution or when constraints are very small |
| Binary Search with Peak Finding | O(log n) | O(1) | Optimal solution for mountain arrays and interactive API limits |
Find in Mountain Array - Leetcode 1095 - Python • NeetCodeIO • 17,973 views views
Watch 9 more video solutions →Practice Find in Mountain Array with our built-in code editor and test cases.
Practice on FleetCode