Find in Mountain Array
Hard · Binary Search · Array · Binary Search · Interactive
Problem
A mountain array strictly increases to a single peak (not at either end) and then strictly decreases. You cannot read it directly; you only get a MountainArray object with two methods:
- mountainArr.get(k) returns the element at index k (0-indexed);
- mountainArr.length() returns the array's length.
Given an integer target, return the smallest index i with mountainArr.get(i) == target, or -1 if the value does not occur. A value can appear at most twice (once on each slope), and you must return the left occurrence when both exist.
Solutions that call get more than 100 times are rejected, so a linear scan is not allowed. In the examples, mountainArr is shown as the array it hides; your method receives the MountainArray object.
Examples
Input: target = 5, mountainArr = [1,3,5,8,5,2] Output: 2
5 appears at indices 2 and 4; the smaller index is returned.
Input: target = 2, mountainArr = [1,3,5,8,5,2] Output: 5
2 appears only on the descending slope, at index 5.
Input: target = 4, mountainArr = [0,6,1] Output: -1
4 is not in the array.
Constraints
- 3 <= mountainArr.length() <= 10^4
- 0 <= target <= 10^9
- 0 <= mountainArr.get(index) <= 10^9
- At most 100 calls to get
Approaches
- Baseline: ternary search for the peak, then both slopes — time O(log n), space O(1)
Follow-up
Could you save calls by caching the values you have already read? The peak search reads mid and mid + 1, and later slope searches often read the same indices again; a small dictionary of read values cuts the total. See the use cases for an upside-down (valley) array, and for the value closest to a target that may not be present.
Related problems
Start free on Cariara · Coding problems · System design studio
