Find in Mountain Array

HARD✓ CHIP-TIMEDLC #1095 — FULL STATEMENT ↗

The drill: A mountain array rises then falls; find a target's index while treating every read of the array as a cost to minimize. LeetCode wraps the array in an interactive get/length interface — here it's adapted to a plain array so the answer can be verified directly.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array rises strictly to a single peak and then strictly falls afterward — one climb, one descent, no flat stretches and no second peak — and a target value needs to be located inside it.

This site adapts the classic interactive access pattern to a plain array so the answer can be checked directly, but the drill still rewards treating every read as something to spend carefully rather than something free.

The job is to report the index where the target sits, or −1 if it never appears anywhere along the climb or the descent.

EX 01

target = 9 · mountainArr = [1, 3, 5, 7, 9, 6, 4, 2]

→ 4

TARGET IS THE PEAK

EX 02

target = 5 · mountainArr = [1, 3, 5, 7, 9, 6, 4, 2]

→ 2

TARGET ON THE ASCENDING SIDE

EX 03

target = 6 · mountainArr = [1, 3, 5, 7, 9, 6, 4, 2]

→ 5

TARGET ON THE DESCENDING SIDE

array length runs from a handful of elements up to a few thousand
array strictly increases to one peak, then strictly decreases
the peak is never the first or last element
answer is a single index, or −1 when the target is absent

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A full walk finds the target in O(n) reads, but the shape of a mountain array — one climb, one descent — is exactly the structure binary search exploits twice over. What single index splits the array into those two sorted halves?

HINT 2 THE STRUCTURE

Binary-search for the peak first: compare each midpoint to its neighbor. Still climbing means the peak is further ahead; already falling means it's at or behind the midpoint.

HINT 3 ONE STEP FROM THE ANSWER

With the peak in hand, everything left of it is ascending and everything right of it is descending — binary-search whichever half could hold the target, flipping the comparison direction on the descending side.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE PEAK AND THE SLOPEPATTERN · PEAK, THEN TWO BINARY SEARCHEStarget = 6 · arr = [1, 3, 5, 7, 9, 6, 4, 2]

PEAK SEARCH RESULT

— empty —

STEP 1

Target 6 in a mountain that climbs then falls. First find the peak with a binary search, then search whichever slope can hold 6.

STEP 1 / 14 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/find-in-mountain-array.py — RACE PACE

LANG ▸

PACE ▸

class MountainArray:
    def __init__(self, arr: List[int]):
        self._arr = arr

    def get(self, index: int) -> int:
        return self._arr[index]

    def length(self) -> int:
        return len(self._arr)


class Solution:
    def findInMountainArray(self, target: int, mountainArr: List[int]) -> int:
        arr = MountainArray(mountainArr)
        n = arr.length()

        # 1. find the peak
        lo, hi = 0, n - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if arr.get(mid) < arr.get(mid + 1):
                lo = mid + 1
            else:
                hi = mid
        peak = lo

        # 2. binary-search the ascending half
        lo, hi = 0, peak
        while lo <= hi:
            mid = (lo + hi) // 2
            v = arr.get(mid)
            if v == target:
                return mid
            if v < target:
                lo = mid + 1
            else:
                hi = mid - 1

        # 3. binary-search the descending half
        lo, hi = peak + 1, n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            v = arr.get(mid)
            if v == target:
                return mid
            if v > target:
                lo = mid + 1
            else:
                hi = mid - 1

        return -1

TIME O(LOG N)SPACE O(1)PYTHON · RACE PACE · 51 LN

class MountainArray:
    def __init__(self, arr: List[int]):
        self._arr = arr

    def get(self, index: int) -> int:
        return self._arr[index]

    def length(self) -> int:
        return len(self._arr)


class Solution:
    def findInMountainArray(self, target: int, mountainArr: List[int]) -> int:
        arr = MountainArray(mountainArr)
        for i in range(arr.length()):     # read every index, in order
            if arr.get(i) == target:
                return i
        return -1

TIME O(N)SPACE O(1)PYTHON · TRAINING PACE · 18 LN

class MountainArray {
    private final int[] arr;

    MountainArray(int[] arr) {
        this.arr = arr;
    }

    int get(int index) {
        return arr[index];
    }

    int length() {
        return arr.length;
    }
}

class Solution {
    public int findInMountainArray(int target, int[] mountainArr) {
        MountainArray arr = new MountainArray(mountainArr);
        int n = arr.length();

        int lo = 0, hi = n - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (arr.get(mid) < arr.get(mid + 1)) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        int peak = lo;

        lo = 0;
        hi = peak;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            int v = arr.get(mid);
            if (v == target) {
                return mid;
            } else if (v < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        lo = peak + 1;
        hi = n - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            int v = arr.get(mid);
            if (v == target) {
                return mid;
            } else if (v > target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        return -1;
    }
}

TIME O(LOG N)SPACE O(1)JAVA · RACE PACE · 63 LN

class MountainArray {
    private final int[] arr;

    MountainArray(int[] arr) {
        this.arr = arr;
    }

    int get(int index) {
        return arr[index];
    }

    int length() {
        return arr.length;
    }
}

class Solution {
    public int findInMountainArray(int target, int[] mountainArr) {
        MountainArray arr = new MountainArray(mountainArr);
        for (int i = 0; i < arr.length(); i++) {    // read every index, in order
            if (arr.get(i) == target) {
                return i;
            }
        }
        return -1;
    }
}

TIME O(N)SPACE O(1)JAVA · TRAINING PACE · 27 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED