Find in Mountain Array

HardBinary Search · Peak Finding🧩 Binary Search LeetCode #1095 ↗Updated Oct 30, 2026

Problem

A mountain array strictly increases up to a single peak and then strictly decreases (length ≥ 3, peak not at either end). You cannot see the array directly: it is hidden behind a MountainArray interface offering only get(i) and length(). Return the smallest index whose value equals target, or -1. Solutions making more than 100 get calls are rejected.

Inputarray = [1,2,3,4,5,3,1], target = 3Output2 (3 also at index 5; 2 is smaller)

Inputarray = [0,1,2,4,2,1], target = 3Output-1

Inputarray = [1,5,2], target = 2Output2

3 ≤ length ≤ 10⁴ · 0 ≤ target, values ≤ 10⁹ · at most 100 calls to get

Try it yourself

Java

class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A mountain is two sorted arrays glued at the peak. Find the peak with binary search (compare get(mid) with get(mid+1)), then binary search the ascending side first — any hit there has a smaller index — and only then the descending side with the comparison flipped.

PatternBinary Search

Instinct Sorted data, a rotated array, or find the min/max X that works where a yes/no test flips only once - halve the search space every step.

Memory hack Find the fence - every candidate reads NO NO NO YES YES, and binary search just walks to where the fence stands.

Open the Binary Search guide →

Approaches

Brute ForceLinear Scan Through get()

Time O(n)Space O(1)

Read indices from left to right and return the first one whose value equals target. Scanning in increasing order automatically yields the smallest matching index.

Java

public int findInMountainArray(int target, MountainArray mountainArr) {
    int n = mountainArr.length();
    for (int i = 0; i < n; i++) {
        if (mountainArr.get(i) == target) return i; // first hit = smallest index
    }
    return -1;
}

Correct, but needs up to 10⁴ get calls — far over the 100-call cap.

BetterClimb to the Peak, then Two Binary Searches

Time O(n)Space O(1)

Walk right while the next value is larger; where that stops is the peak. The left part is ascending and the right part descending, so each can be binary searched. Search the left side first, because any match there beats a match on the right.

Java

public int findInMountainArray(int target, MountainArray mountainArr) {
    int n = mountainArr.length();
    int peak = 0;
    while (mountainArr.get(peak) < mountainArr.get(peak + 1)) peak++; // walk uphill
    int idx = search(mountainArr, target, 0, peak, true);
    return idx != -1 ? idx : search(mountainArr, target, peak + 1, n - 1, false);
}
// binary search on [lo, hi], sorted ascending (asc = true) or descending
private int search(MountainArray m, int target, int lo, int hi, boolean asc) {
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int v = m.get(mid);
        if (v == target) return mid;
        if ((v < target) == asc) lo = mid + 1; // target lies to the right
        else hi = mid - 1;
    }
    return -1;
}

The searches are logarithmic, but the climb still costs O(n) calls on a far-right peak.

OptimalThree Binary Searches (Peak, Left, Right)

Time O(log n)Space O(1)

Find the peak by binary search too: if get(mid) < get(mid+1) we are still climbing, so the peak is right of mid; otherwise it is mid or to its left. Then reuse the ascending search on [0, peak] and, only if that misses, the descending search on [peak+1, n-1]. Total calls are about 4·log₂n ≈ 56 for n = 10⁴.

Java

public int findInMountainArray(int target, MountainArray mountainArr) {
    int n = mountainArr.length();
    int lo = 0, hi = n - 1;
    while (lo < hi) { // find the peak index
        int mid = lo + (hi - lo) / 2;
        if (mountainArr.get(mid) < mountainArr.get(mid + 1)) lo = mid + 1; // still uphill
        else hi = mid;                                                     // downhill
    }
    int peak = lo;
    int idx = search(mountainArr, target, 0, peak, true); // smaller indices first
    return idx != -1 ? idx : search(mountainArr, target, peak + 1, n - 1, false);
}
// binary search on [lo, hi], sorted ascending (asc = true) or descending
private int search(MountainArray m, int target, int lo, int hi, boolean asc) {
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int v = m.get(mid);
        if (v == target) return mid;
        if ((v < target) == asc) lo = mid + 1; // target lies to the right
        else hi = mid - 1;
    }
    return -1;
}

Dry runarray = [1,2,3,4,5,3,1], target = 3

lo lowm midhi highp peak changed

peak: lo=0 hi=6
1
lo
2

3

4
m
5

3

1
hi
4 < 5 → lo=4
peak: lo=4 hi=6
1

2

3

4

5
lo
3
m
1
hi
3 > 1 → hi=5
peak: lo=4 hi=5
1

2

3

4

5
lo m
3
hi
1

5 > 3 → peak=4
left: lo=0 hi=4
1
lo
2

3
m
4

5
hi p
3

1

get(2)=3 found ✔

Stays well under the 100-call budget for every allowed size — the intended solution.

Pro tip

Searching the ascending half first is what guarantees the smallest index — the right half is only consulted on a miss.

At a glance

Level	Approach	Time	Space
Brute Force	Linear Scan Through get()	`O(n)`	`O(1)`
Better	Climb to the Peak, then Two Binary Searches	`O(n)`	`O(1)`
Optimal	Three Binary Searches (Peak, Left, Right)	`O(log n)`	`O(1)`

Common pitfalls

Searching the descending half first and returning the larger of two matching indices.
Reusing the ascending comparison on the right half — the direction must flip.
Calling get(mid) repeatedly instead of storing it, wasting the call budget.

Interview tips

Count the calls out loud: about 2·log n for the peak plus log n per side.
Write one search helper with a direction flag instead of two near-copies.
Note that caching values in a map is a cheap safety net if calls are very tight.

Pattern

Binary search on a bitonic array → find the turning point first, then search each monotone half.

My notes saved in this browser