Find in Mountain Array

NeetCode: Find in Mountain Array · LeetCode: 1095. Find in Mountain Array · Difficulty: Hard

A mountain array strictly increases up to a single peak and then strictly decreases. You cannot read it directly: you only have get(i) and length() from a MountainArray interface, and get is expensive (LeetCode allows at most 100 calls). Return the minimum index whose value equals target, or -1 if there is none.

Example

Text

Input:  array = [1,2,3,4,5,3,1], target = 3    Output: 2   (3 appears at 2 and 5)
Input:  array = [0,1,2,4,2,1],   target = 3    Output: -1

LeetCode supplies MountainArray as an interface with int get(int index) and int length(). The programs below declare that interface and implement it with a mock class that owns an int[] and counts every get call in a field.

Brute force: scan from the left

Read every element from index 0 upward and return the first match. Scanning left to right automatically returns the minimum index. It makes up to n calls to get, which exceeds the call budget for large arrays.

LeetCode's Java signature is int findInMountainArray(int target, MountainArray mountainArr).

Java

public class Main {
    interface MountainArray {
        int get(int index);

        int length();
    }

    static class MockMountainArray implements MountainArray {
        private final int[] data;
        int calls = 0;

        MockMountainArray(int... data) {
            this.data = data;
        }

        public int get(int index) {
            calls++;
            return data[index];
        }

        public int length() {
            return data.length;
        }
    }

    static class Solution {
        public int findInMountainArray(int target, MountainArray arr) {
            for (int i = 0; i < arr.length(); i++) {
                if (arr.get(i) == target) {
                    return i;
                }
            }
            return -1;
        }
    }

    static void run(int target, int... data) {
        MockMountainArray arr = new MockMountainArray(data);
        int ans = new Solution().findInMountainArray(target, arr);
        System.out.println("index " + ans + " after " + arr.calls + " get calls");
    }

    public static void main(String[] args) {
        run(3, 1, 2, 3, 4, 5, 3, 1);
        run(3, 0, 1, 2, 4, 2, 1);
        run(1, 1);
        run(1);
    }
}

Output

index 2 after 3 get calls
index -1 after 6 get calls
index 0 after 1 get calls
index -1 after 0 get calls

Time: O(n) calls. Space: O(1).

Optimal: find the peak, then two plain binary searches

A mountain is an ascending array glued to a descending array at the peak. Three small steps:

Find the peak. Compare get(mid) with get(mid + 1). If get(mid) is smaller, the array is still climbing and the peak is to the right; otherwise the peak is at mid or to its left.
Search the ascending side [0, peak]. If found, that is the smallest index, so return it.
Only if not found, search the descending side [peak + 1, n - 1], same search with the comparison flipped.

Searching the left side first guarantees the minimum index. The peak search takes about 2 log n calls and each side search about log n, so a few dozen calls for n = 10^4, within the limit of 100. The last test below checks that 1000 elements need at most 40 calls.

Java

public class Main {
    interface MountainArray {
        int get(int index);

        int length();
    }

    static class MockMountainArray implements MountainArray {
        private final int[] data;
        int calls = 0;

        MockMountainArray(int... data) {
            this.data = data;
        }

        public int get(int index) {
            calls++;
            return data[index];
        }

        public int length() {
            return data.length;
        }
    }

    static class Solution {
        private int findPeak(MountainArray arr) {
            int lo = 0, hi = arr.length() - 1;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (arr.get(mid) < arr.get(mid + 1)) {
                    lo = mid + 1; // still climbing
                } else {
                    hi = mid; // mid could be the peak
                }
            }
            return lo;
        }

        // Binary search on arr[lo..hi]; `ascending` selects the comparison direction.
        private int search(MountainArray arr, int target, int lo, int hi, boolean ascending) {
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                int v = arr.get(mid);
                if (v == target) {
                    return mid;
                }
                if ((v < target) == ascending) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
            return -1;
        }

        public int findInMountainArray(int target, MountainArray arr) {
            int n = arr.length();
            if (n == 0) {
                return -1;
            }
            int peak = findPeak(arr);
            int left = search(arr, target, 0, peak, true);
            if (left != -1) {
                return left;
            }
            return search(arr, target, peak + 1, n - 1, false);
        }
    }

    static void run(int target, int... data) {
        MockMountainArray arr = new MockMountainArray(data);
        int ans = new Solution().findInMountainArray(target, arr);
        System.out.println("index " + ans + " after " + arr.calls + " get calls");
    }

    public static void main(String[] args) {
        run(3, 1, 2, 3, 4, 5, 3, 1);
        run(3, 0, 1, 2, 4, 2, 1);
        run(1, 1);
        run(1);

        // 1000 elements: 0,2,4,...,998 up, then 997,995,...,1 down.
        int[] big = new int[1000];
        for (int i = 0; i < 500; i++) {
            big[i] = i * 2;
            big[999 - i] = i * 2 + 1;
        }
        MockMountainArray arr = new MockMountainArray(big);
        int ans = new Solution().findInMountainArray(1, arr);
        System.out.println("big: index " + ans + " within 40 calls: " + (arr.calls <= 40));
    }
}

Output

index 2 after 7 get calls
index -1 after 10 get calls
index 0 after 1 get calls
index -1 after 0 get calls
big: index 999 within 40 calls: true

Time: O(log n) calls to get. Space: O(1).

Edge cases

An empty array returns -1.
When the peak is the last element, the descending range [peak + 1, n - 1] is empty and the search returns -1 immediately.

How to explain it in an interview

Baseline: scan left to right with get and return the first match. That is O(n) calls, which exceeds the 100-call budget.
Key idea: a mountain is two sorted arrays joined at the peak, so once the peak is known, each side is an ordinary binary search.
Steps: (1) findPeak comparing mid and mid + 1; (2) binary search the ascending side; (3) if not found, binary search the descending side with the comparison flipped; (4) return -1 if both fail.
Complexity: O(log n) calls to get (roughly 4 log n), O(1) space.
Common questions: search the left side first because any match there has a smaller index than one on the descending side. A small HashMap<Integer, Integer> can cache get results to avoid repeated calls to the same index.