Find in Mountain Array
Understanding the Problem
This problem combines mountain arrays and binary search. A mountain array rises strictly to a peak, then falls strictly from that peak. We are given a target value and need to find the smallest index where it appears. The constraint is that we cannot scan the array directly. We can only access elements through an API, and we are limited to 100 calls total.
A mountain array is two sorted arrays joined at the peak. The left half is sorted in ascending order and the right half is sorted in descending order. Once we locate the peak, we can binary search each half independently. Since we want the minimum index, we search the ascending (left) half first.
Key Constraints:
3 <= mountain_arr.length() <= 10^4→ The array holds up to 10,000 elements. A linear scan would use up to 10,000 API calls. With log2(10^4) ≈ 14, each binary search costs about 14 calls, so three of them stay near 42 calls.At most 100 calls to MountainArray.get→ This rules out any approach that touches every element and forces an O(log n) solution.0 <= mountain_arr.get(index) <= 10^9→ Values fit in a 32-bit signed integer, so no overflow concerns and no negative values to special-case.
Approach 1: Linear Scan
Intuition
Walk through the array from left to right and return the first index where the value equals the target. Scanning left to right means the first match is the minimum index by construction.
This ignores the mountain structure entirely. It serves as a baseline before we optimize, and it shows why the call limit matters.
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 uses up to 10,000 API calls, well past the 100-call limit. The next approach uses the mountain structure: find the peak with binary search, then binary search each sorted half.
Approach 2: Find Peak + Two Binary Searches
Intuition
The left side of a mountain array increases strictly and the right side decreases strictly. Locating the peak reduces the problem to two independent binary searches on sorted subarrays.
The plan has three phases: find the peak index with binary search, search the ascending half [0, peak] with standard binary search, and if the target is not found there, search the descending half [peak, n-1] with a reversed binary search.
Peak finding compares arr[mid] with arr[mid + 1]. If arr[mid] < arr[mid + 1], the slope is still rising, so the peak lies strictly to the right and left = mid + 1 is safe. Otherwise the slope is falling (or mid is the peak), so the peak is at mid or to its left and right = mid keeps it in range. The loop ends when left == right, which is the peak.
Searching the ascending half before the descending half gives the minimum index. A value can appear once on each side. The ascending side holds the smaller index, and the search returns as soon as it finds a match there, so the descending half is only searched when the value is absent on the left.
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 optimal in Big-O, but it can repeat API calls. Peak finding queries mountainArr.get(mid) and mountainArr.get(mid + 1), and some of those indices are queried again during the two binary searches. Caching every result removes those duplicate calls, which matters against the 100-call ceiling.
Approach 3: Optimized with Caching
Intuition
A hash map caches the result of each mountainArr.get() call. The first time an index is queried, the value is stored. Later requests for the same index read from the map instead of calling the API again.
The savings are concentrated at the boundaries between phases. The peak index and the indices near it are queried during peak finding and then again at the start of each half-search, so caching turns those repeats into free map lookups.
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).