Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Find in Mountain Array

Search a rise-then-fall array for a target in O(log n): find the peak, binary search the rising side, then the falling side with the comparison reversed.

hardPattern: Peak Finding

Updated Long read: 10 min read

Approaches at a glance

ApproachTimeSpace
Linear scanO(n)O(1)
Find the peak, then search each slopeO(log n)O(1)

The problem

A mountain array has at least three elements, climbs strictly to one highest value, and then falls strictly. The highest value is not at either end.

Given a mountain array and a target, return the smallest index at which the target appears, or -1 if it does not appear. The solution must run in O(log n) time.

heights = [1, 4, 7, 10, 8, 4, 2], target = 8    →  4
heights = [1, 4, 7, 10, 8, 4, 2], target = 4    →  1    (4 is also at index 5; 1 is smaller)
heights = [1, 4, 7, 10, 8, 4, 2], target = 5    →  -1
heights = [1, 4, 7, 10, 8, 4, 2], target = 10   →  3    (the peak)

A value can appear at most twice: once on the way up and once on the way down. Each slope is strictly increasing or strictly decreasing, so it cannot repeat a value within itself.

The read limit in the original

In the original version of this problem you are not handed the array. You get an object with two operations, "give me the value at index i" and "give me the length", and a hard cap of 100 value reads for arrays of up to 10,000 elements. A linear scan fails that cap immediately. On this page the function takes a plain array, which keeps the code easy to run, but the solution is written as if every read were expensive: it reads only O(log n) elements.

Approach 1: linear scan

Look at every element from the left and return the first match.

JavaScript

function findInMountainLinear(heights, target) {
  for (let i = 0; i < heights.length; i++) {
    if (heights[i] === target) return i;
  }
  return -1;
}

Python

def find_in_mountain_linear(heights, target):
    for i, value in enumerate(heights):
        if value == target:
            return i
    return -1

Time O(n), space O(1). Scanning from the left gives the smallest index for free. It ignores the shape of the data entirely, and with the read limit of the original it would use up to 10,000 reads where only 100 are allowed.

A mountain is two sorted arrays

Ordinary binary search cannot run on the whole mountain, because the mountain is not sorted. Split it at the peak, though, and each piece is:

[1, 4, 7, 10,   8, 4, 2]
 └ ascending ┘  └ descending ┘
   index 0..3     index 4..6

So the plan has three steps, each one a binary search:

  1. Find the peak. This is Peak Index in a Mountain Array.
  2. Search the rising side, from index 0 to the peak, with the usual exact-match search.
  3. If that fails, search the falling side, from just after the peak to the end, with the comparison reversed.

The order of steps 2 and 3 matters. Every index on the rising side is smaller than every index on the falling side, so a match on the rising side is automatically the smallest index. The falling side is searched only when the rising side has no match.

Approach 2: find the peak, then search each slope

Step 1: the peak

Compare the middle with its right-hand neighbour. If the neighbour is larger, the middle is still climbing and the peak is further right. Otherwise the peak is the middle or to its left.

JavaScript

function mountainPeak(heights) {
  let lo = 0;
  let hi = heights.length - 1;
 
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (heights[mid] < heights[mid + 1]) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  return lo;
}

Python

def mountain_peak(heights):
    lo = 0
    hi = len(heights) - 1
 
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if heights[mid] < heights[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo

Step 2: the rising side

A standard exact-match binary search, limited to the range lo to hi (both inclusive).

JavaScript

function searchRisingSide(heights, target, lo, hi) {
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (heights[mid] === target) return mid;
 
    if (heights[mid] < target) {
      lo = mid + 1;   // values grow to the right, so go right for something bigger
    } else {
      hi = mid - 1;
    }
  }
  return -1;
}

Python

def search_rising_side(heights, target, lo, hi):
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if heights[mid] == target:
            return mid
 
        if heights[mid] < target:
            lo = mid + 1   # values grow to the right, so go right for something bigger
        else:
            hi = mid - 1
    return -1

Step 3: the falling side

The same search with one character changed. On a descending run, bigger values are on the left, so when the middle is too small the search must move left, not right.

JavaScript

function searchFallingSide(heights, target, lo, hi) {
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (heights[mid] === target) return mid;
 
    if (heights[mid] > target) {
      lo = mid + 1;   // values shrink to the right, so go right for something smaller
    } else {
      hi = mid - 1;
    }
  }
  return -1;
}

Python

def search_falling_side(heights, target, lo, hi):
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if heights[mid] == target:
            return mid
 
        if heights[mid] > target:
            lo = mid + 1   # values shrink to the right, so go right for something smaller
        else:
            hi = mid - 1
    return -1

Putting the three together

JavaScript

function findInMountain(heights, target) {
  const peak = mountainPeak(heights);
 
  const onRisingSide = searchRisingSide(heights, target, 0, peak);
  if (onRisingSide !== -1) return onRisingSide;
 
  return searchFallingSide(heights, target, peak + 1, heights.length - 1);
}

Python

def find_in_mountain(heights, target):
    peak = mountain_peak(heights)
 
    on_rising_side = search_rising_side(heights, target, 0, peak)
    if on_rising_side != -1:
        return on_rising_side
 
    return search_falling_side(heights, target, peak + 1, len(heights) - 1)

The peak belongs to the rising search (range 0 to peak), so the falling search starts at peak + 1. Including the peak in both would do no harm, only a wasted read.

Walkthrough

heights = [1, 4, 7, 10, 8, 4, 2], target = 8.

Step 1: find the peak.

lo hi mid (value) Next value Action
0 6 3 (10) 8 Falling: hi = 3
0 3 1 (4) 7 Rising: lo = 2
2 3 2 (7) 10 Rising: lo = 3
3 3 Peak is index 3

Step 2: search the rising side, index 0 to 3, for 8.

lo hi mid (value) Compare with 8 Action
0 3 1 (4) Smaller lo = 2
2 3 2 (7) Smaller lo = 3
3 3 3 (10) Larger hi = 2
3 2 The range is empty Not on this side

Step 3: search the falling side, index 4 to 6, for 8.

lo hi mid (value) Compare with 8 Action
4 6 5 (4) Smaller, and bigger values are to the left hi = 4
4 4 4 (8) Equal Return 4

For target = 4, step 2 finds the 4 at index 1 on its first look and returns straight away. The second 4, at index 5, is never examined, which is how the smallest index is guaranteed.

Time O(log n): three binary searches, one after another, each at most about log₂ n steps. Space O(1).

Counting the reads

For the largest array the original allows, 10,000 elements, a binary search takes at most 14 steps.

Step Reads per step Reads at most
Find the peak 2 (the middle and its neighbour) 28
Search the rising side 1 14
Search the falling side 1 14
Total 56

That fits inside the cap of 100 with room to spare. The linear scan does not come close.

Comparing the approaches

Linear scan Peak, then two searches
Time O(n) O(log n)
Space O(1) O(1)
Reads for 10,000 elements Up to 10,000 At most 56
Returns the smallest index Yes, by scanning left to right Yes, by searching the rising side first
Amount of code A few lines Three short functions and a wrapper

Try it yourself

Copy all four functions of approach 2 from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

console.log(findInMountain([1, 4, 7, 10, 8, 4, 2], 8)); // 4
console.log(findInMountain([1, 4, 7, 10, 8, 4, 2], 4)); // 1
console.log(findInMountain([1, 4, 7, 10, 8, 4, 2], 5)); // -1
console.log(findInMountain([1, 4, 7, 10, 8, 4, 2], 10)); // 3
console.log(findInMountain([1, 4, 7, 10, 8, 4, 2], 2)); // 6

Python

print(find_in_mountain([1, 4, 7, 10, 8, 4, 2], 8))  # 4
print(find_in_mountain([1, 4, 7, 10, 8, 4, 2], 4))  # 1
print(find_in_mountain([1, 4, 7, 10, 8, 4, 2], 5))  # -1
print(find_in_mountain([1, 4, 7, 10, 8, 4, 2], 10))  # 3
print(find_in_mountain([1, 4, 7, 10, 8, 4, 2], 2))  # 6

The comment after each line is the result you should see.

Common mistakes

  • Searching the falling side first. If the target is on both slopes, that returns the larger index. Always try the rising side first.
  • Not reversing the comparison on the falling side. An ascending search on descending data moves away from the target and reports -1 for values that are there.
  • Trying to do it in one binary search. Comparing the target with the middle of the whole mountain says nothing about direction: a target smaller than the middle could be on either slope. The peak has to be found first.
  • Using hi = mid - 1 when finding the peak. The middle may be the peak, so it must stay in the range. The two side searches do use mid - 1, because there the middle has just been ruled out.
  • Stopping when the rising side has no match. The target may exist only on the way down, as 8 does in the walkthrough.
  • Reading the same index repeatedly. With a real read limit, store a value in a variable instead of asking for it twice in one step.

The three building blocks are set out side by side in the peak finding pattern. Search in Rotated Sorted Array is a close cousin: also two sorted runs, joined differently.

Original problem: LeetCode 1095: Find in Mountain Array