HardArrayBinary Search

Find in Mountain Array

1 approach, code in every language

A mountain array is an array that strictly increases up to a single highest element and then strictly decreases afterwards. You are given such an array wrapped behind an interface: you cannot read it directly, but you can call get(i) to fetch the value at position i and length() to learn the size. Calls to get are treated as expensive, so the number of them should be kept small.

Given a target value, return the smallest index whose value equals the target. If the target does not appear anywhere in the mountain array, return -1.

Example 1

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

Output: 2

The value 3 appears at index 2 on the rising side and again at index 5 on the falling side. The smallest such index is 2.

Example 2

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

Output: -1

There is no element equal to 3 anywhere in the mountain, so the answer is -1.

Constraints

3 <= mountainArr.length() <= 10^4
0 <= target <= 10^9
0 <= mountainArr.get(i) <= 10^9

Locate the Peak, Then Search Each Side

Binary search for the summit, then run two ordered binary searches on the two slopes.

Loading animation…

Intuition

A mountain array is made of two sorted halves: the part before the peak is strictly increasing and the part after it is strictly decreasing. If we first find the peak, each half becomes a normal sorted array and standard binary search applies. Because the smallest matching index must be as far left as possible, we search the ascending half first and only fall back to the descending half if the target was not found there.

Algorithm walkthrough

1Binary search the whole array by comparing get(mid) with get(mid + 1) to find the peak index where the array stops rising.
2Run an ascending binary search over the range from 0 to the peak; if the value is found, return that index immediately.
3If not found, run a descending binary search over the range from peak + 1 to the last index, flipping the comparison because values decrease.
4Return the matching index from the descending search if any.
5If neither side contains the target, return -1.

Implementation

# This is MountainArray's API interface.
# class MountainArray:
#     def get(self, index: int) -> int:
#     def length(self) -> int:

class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        n = mountain_arr.length()
        lo, hi = 0, n - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                lo = mid + 1
            else:
                hi = mid
        peak = lo

        lo, hi = 0, peak
        while lo <= hi:
            mid = (lo + hi) // 2
            val = mountain_arr.get(mid)
            if val == target:
                return mid
            elif val < target:
                lo = mid + 1
            else:
                hi = mid - 1

        lo, hi = peak + 1, n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            val = mountain_arr.get(mid)
            if val == target:
                return mid
            elif val > target:
                lo = mid + 1
            else:
                hi = mid - 1
        return -1

Time

O(log n)

Space

O(1)

Three binary searches, each logarithmic, keep the number of get calls near 3 * log n.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free