DSA problem

Find in Mountain Array

HardBinary SearchPattern: Binary Searchtop300GoogleAmazonMicrosoft

You may recall that an array arr is a mountain array if and only if: arr.length >= 3 and there exists some i with 0 < i < arr.length - 1 such that arr[0] < arr[1] < ... < arr[i - 1] < 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 can only access the array using a MountainArray interface: MountainArr.get(k) returns the element of the array at index k (0-indexed), and MountainArr.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.

Solve this in three binary searches:

Locate the peak with the slope-comparison technique from "Find Peak Element". Compare arr[mid] and arr[mid + 1]; rising means the peak is to the right, falling means it is at or before mid. This finds peak in O(log n) calls.
Run an ascending binary search on [0, peak] for target. If found, return the index immediately (it's the smallest by definition).
Otherwise, run a descending binary search on [peak + 1, n - 1] for target. Same template but the comparison is inverted.

Total calls to get: roughly 3 log n, comfortably within 100 for n <= 10^4. Memoize results in a local map if you want to be extra defensive, though it is not strictly required. The complexity is O(log n) calls, O(1) memory.

Examples

Example 1

Input: array = [1,2,3,4,5,3,1], target = 3

Output: 2

Explanation: The peak is at index 4 (value 5). Ascending search on [0, 4] finds 3 at index 2 — return immediately.

Example 2

Input: array = [0,1,2,4,2,1], target = 3

Output: -1

Explanation: Peak is at index 3 (value 4). 3 is missing from both halves, so the answer is -1.

Example 3

Input: array = [1,5,2], target = 2

Output: 2

Explanation: Peak at index 1; ascending search on [0, 1] does not find 2; descending search on [2, 2] finds it at index 2.

Constraints

3 <= mountain_arr.length() <= 10^4
0 <= target <= 10^9
0 <= mountain_arr.get(index) <= 10^9
Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

binary-searchinteractivemountain-array

Browse all DSA problems