(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) <= 109The key challenge in #1095 Find in Mountain Array is that the array is a mountain array (strictly increasing then strictly decreasing) and can only be accessed through an MountainArray API. A direct linear scan would exceed the allowed number of API calls, so an efficient binary search strategy is required.
First, locate the peak index of the mountain using binary search. Compare get(mid) and get(mid + 1) to determine whether you are in the ascending or descending region, and narrow the search until the peak is found.
Once the peak is known, perform two separate binary searches: one on the ascending portion (from index 0 to peak) and another on the descending portion (from peak + 1 to n - 1). The second search must account for the reversed ordering. This approach minimizes API calls and maintains logarithmic efficiency.
Time Complexity: O(log n) due to multiple binary searches. Space Complexity: O(1).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Find Peak + Binary Search on Both Sides | O(log n) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Based on whether A[i-1] < A[i] < A[i+1], A[i-1] < A[i] > A[i+1], or A[i-1] > A[i] > A[i+1], we are either at the left side, peak, or right side of the mountain. We can binary search to find the peak. After finding the peak, we can binary search two more times to find whether the value occurs on either side of the peak.
In this approach, the task is broken into three main steps:
arr[i] > arr[i+1] and arr[i] > arr[i-1].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.
1class MountainArray {
2 get(index) {
3 // Returns the element of the array at index 'index'.
4 }
5
6 length(
The JavaScript solution employs a binary search strategy first to find the peak of the mountain array, then to conduct two additional binary searches on both sections. This ensures that the target is found efficiently with a minimal index. The approach is efficient due to the logarithmic complexity of the binary search.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variants of mountain array and peak element problems frequently appear in FAANG-style interviews. They test understanding of binary search patterns, array properties, and optimization under restricted access conditions.
The optimal approach uses binary search in three stages. First find the peak element of the mountain array, then run binary search on the increasing side and another modified binary search on the decreasing side. This keeps the number of API calls low and achieves O(log n) time complexity.
The peak divides the array into two sorted segments: one ascending and one descending. Once the peak is known, standard binary search can be applied on both halves with slight adjustments. This structure makes the search efficient without scanning the entire array.
The main technique used is binary search on arrays with different ordering. The solution also relies on the MountainArray interface for controlled access to elements, making it an interactive problem focused on minimizing API calls.
The Python brute-force method iterates across each element of the array sequentially, which could come at a significant performance cost. It outputs the index at which the target is present via linear inspection. If not found after iterating through all elements, -1 is returned due to inefficiencies in this simple, non-optimized approach.