Find in Mountain Array
Last Updated: March 29, 2026
Understanding the Problem
This problem combines two classic ideas: mountain arrays and binary search. A mountain array rises strictly to a peak, then falls strictly from that peak. We're given a target value and need to find the smallest index where it appears, but there's a twist: we can't just scan the array. We can only access elements through an API, and we're limited to 100 calls total.
Here's the key observation: a mountain array is really two sorted arrays glued together at the peak. The left half is sorted in ascending order and the right half is sorted in descending order. If we can find the peak, we can binary search both halves independently. And since we want the minimum index, we should search the ascending (left) half first.
Key Constraints:
3 <= mountain_arr.length() <= 10^4→ The array can have up to 10,000 elements. A linear scan would use up to 10,000 API calls, far exceeding the 100-call limit. Binary search uses ~14 calls per search, so three binary searches use ~42 calls total.At most 100 calls to MountainArray.get→ This forces us toward O(log n) binary search. No approach that touches every element will work.0 <= mountain_arr.get(index) <= 10^9→ Large values, but no negative numbers. This doesn't affect our algorithm choice.
Approach 1: Linear Scan
Intuition
The most basic approach: just walk through the array from left to right and return the first index where the value equals the target. Since we want the minimum index and we're scanning from left to right, the first match we find is automatically the answer.
This approach completely ignores the mountain structure. It's the brute force baseline, useful for understanding the problem before optimizing.
Algorithm
- Get the array length
nusingmountainArr.length(). - Iterate
ifrom 0 ton - 1. - If
mountainArr.get(i) == target, returni. - If the loop finishes without finding the target, return
-1.
Example Walkthrough
Code
- Time Complexity: O(n). In the worst case, we scan every element in the array. For n up to 10,000, this means 10,000 API calls.
- Space Complexity: O(1). Only uses a loop variable and no extra data structures.
The linear scan works but uses too many API calls for large arrays. Since the mountain array is two sorted halves joined at a peak, we can use binary search to find the peak and then search each half independently.
Approach 2: Find Peak + Two Binary Searches
Intuition
A mountain array is two sorted halves joined at a peak. The left side increases strictly, and the right side decreases strictly. If we can locate the peak, we've reduced the problem to two independent binary searches on sorted subarrays.
The plan: (1) find the peak index using binary search, (2) search the ascending half with standard binary search, (3) if not found, search the descending half with reversed binary search. We search the left half first because it has smaller indices, guaranteeing we find the minimum index.
The mountain array property guarantees that the array strictly increases up to the peak and strictly decreases after it. The ascending half [0, peak] is a standard sorted array where binary search works normally. The descending half [peak, n-1] is a reverse-sorted array where binary search works with flipped comparisons.
By searching the ascending half first, we guarantee we find the minimum index. If the target exists at both index 2 (ascending side) and index 5 (descending side), we return 2 because we check the left half first and return immediately when we find a match.
Algorithm
- Get
n = mountainArr.length(). - Find peak: Set
left = 0,right = n - 1. Whileleft < right, computemid. IfmountainArr.get(mid) < mountainArr.get(mid + 1), setleft = mid + 1. Otherwise, setright = mid. When done,leftis the peak index. - Search ascending half: Set
left = 0,right = peak. Standard binary search: ifmountainArr.get(mid) < target, go right. IfmountainArr.get(mid) > target, go left. If equal, returnmid. - Search descending half: Set
left = peak,right = n - 1. Reversed binary search: ifmountainArr.get(mid) > target, go right. IfmountainArr.get(mid) < target, go left. If equal, returnmid. - If neither search finds the target, return
-1.
Example Walkthrough
Code
- Time Complexity: O(log n). Finding the peak takes O(log n) comparisons. Searching each half also takes O(log n). Total: 3 * O(log n) = O(log n).
- Space Complexity: O(1). Only uses a handful of integer variables. No extra data structures, no recursion.
Approach 2 is already optimal in Big-O, but during peak finding we call mountainArr.get(mid) and mountainArr.get(mid + 1), and some of those values overlap with indices we query in the subsequent binary searches. What if we cached every result to avoid redundant API calls?
Approach 3: Optimized with Caching
Intuition
Approach 2 is already optimal in terms of Big-O, but there's a practical optimization worth knowing. During the peak-finding phase, we call mountainArr.get(mid) and mountainArr.get(mid + 1) at each step. Some of these values get re-fetched during the subsequent binary searches on the ascending and descending halves.
We can use a hash map to cache the results of mountainArr.get() calls. Every time we call get(k), we store the result. Before making a new call, we check if we already have the value cached. This reduces the total number of API calls, which matters because the problem limits us to 100.
Algorithm
- Create a hash map
cacheto storeindex → valuemappings. - Define a helper function
getVal(index)that checks the cache first, and only callsmountainArr.get(index)if the value isn't cached. - Use the same three-phase approach as Approach 2 (find peak, search ascending, search descending), but replace all direct
mountainArr.get()calls withgetVal().
Example Walkthrough
Code
- Time Complexity: O(log n). Same algorithmic complexity as Approach 2. Three binary searches, each O(log n). The cache adds O(1) per lookup.
- Space Complexity: O(log n). The cache stores at most ~3 * log(n) entries (the number of unique indices visited across all three binary searches).