Skip to main content
CodePeetCodePeet
CodePeet 250

Find in Mountain Array

HARDProblemSolveExternal Links

Description

You are given a mountain array and a target value. A mountain array is one that first strictly increases to a peak element and then strictly decreases. Formally, an array arr is a mountain array if:

  • arr.length >= 3
  • There exists some index i with 0 < i < arr.length - 1 such that arr[0] < arr[1] < ... < arr[i] and arr[i] > arr[i+1] > ... > arr[arr.length - 1].

Your task is to find the minimum index where the target value appears in the mountain array. If it does not exist, return -1.

Important constraint: You cannot access the array directly. You may only interact with it through a MountainArray interface that provides two methods:

  • MountainArray.get(k) — returns the element at index k
  • MountainArray.length() — returns the length of the array

You are limited to at most 100 calls to MountainArray.get, so a linear scan is too wasteful for large inputs. You need a strategy that minimizes the number of element accesses.

Examples

Example 1

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

Output: 2

Explanation: The value 3 appears at two positions in the array: index 2 (in the ascending portion) and index 5 (in the descending portion). Since we need the minimum index, we return 2.

Example 2

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

Output: -1

Explanation: The value 3 does not exist anywhere in the array. The peak element is 4 at index 3, but 3 is not present on either the ascending side [0, 1, 2, 4] or the descending side [4, 2, 1]. So we return -1.

Example 3

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

Output: 1

Explanation: The peak element 5 is at index 1. It matches the target, so we return 1.

Constraints

  • 3 ≤ mountainArr.length() ≤ 10^4
  • 0 ≤ target ≤ 10^9
  • 0 ≤ mountainArr.get(index) ≤ 10^9
  • At most 100 calls to MountainArray.get are allowed

Editorial

Brute Force

Intuition

The simplest way to find a target in any array is a linear scan: walk through every element from left to right, and return the first index where the value matches the target.

Think of it like looking for a specific house number on a street. You start at the beginning and check every house one by one until you find the one you want. The first match you encounter is guaranteed to be the minimum index, since you are scanning left to right.

Since we need the minimum index, a left-to-right scan naturally returns the correct answer upon the first match.

Step-by-Step Explanation

Let's trace through with mountainArr = [1, 2, 3, 4, 5, 3, 1], target = 3:

Step 1: Start at index 0. Call mountainArr.get(0) = 1. Is 1 == 3? No. Move on.

Step 2: Check index 1. Call mountainArr.get(1) = 2. Is 2 == 3? No. Move on.

Step 3: Check index 2. Call mountainArr.get(2) = 3. Is 3 == 3? Yes! We found the target.

Step 4: Return index 2. Since we scan left to right, this is guaranteed to be the minimum index.

Linear Scan — Finding Target in Mountain Array — Watch how we scan each element from left to right, comparing it to the target, and stop at the first match.

Algorithm

  1. Get the length n of the mountain array
  2. For each index i from 0 to n-1:
    • Call mountainArr.get(i)
    • If the returned value equals target, return i
  3. If no match is found after scanning all elements, return -1

Code

/**
 * // This is the MountainArray's API interface.
 * class MountainArray {
 *   public:
 *     int get(int index);
 *     int length();
 * };
 */

class Solution {
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;
            }
        }
        return -1;
    }
};
# """
# 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()
        for i in range(n):
            if mountain_arr.get(i) == target:
                return i
        return -1
/**
 * // This is MountainArray's API interface.
 * interface MountainArray {
 *     public int get(int index) {}
 *     public int length() {}
 * }
 */

class Solution {
    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;
            }
        }
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(n)

We potentially scan every element in the array once. Each call to mountainArr.get is O(1), and we make at most n such calls. So total time is O(n).

Space Complexity: O(1)

We only use a loop counter variable. No additional data structures are needed.

Why This Approach Is Not Efficient

The linear scan makes up to n calls to mountainArr.get, where n can be as large as 10^4. However, the problem explicitly limits us to at most 100 calls. For an array of length 10,000, a linear scan would need up to 10,000 calls — far exceeding the 100-call budget.

The key insight we are ignoring is the structure of the mountain array: it is sorted in ascending order on the left side of the peak and sorted in descending order on the right side. When you have a sorted array and need to find a target, binary search lets you find it in O(log n) calls instead of O(n).

With binary search, even for n = 10^4, we would need at most log₂(10000) ≈ 14 calls per search — well within the 100-call limit.

Optimal Approach - Triple Binary Search

Intuition

A mountain array has a very useful property: it is composed of two sorted halves separated by a peak. The left half (from index 0 to the peak) is sorted in ascending order, and the right half (from the peak to the last index) is sorted in descending order.

Imagine hiking up a mountain trail with numbered mile markers that increase as you climb and decrease as you descend. If someone asks 'Where is mile marker 7?', you would not walk the entire trail. Instead:

  1. First, find the summit — the highest point on the trail.
  2. Then search the uphill side — since markers increase going up, you can use binary search on the ascending portion.
  3. If not found on the uphill side, search the downhill side — since markers decrease going down, you can use a reversed binary search on the descending portion.

This gives us a three-step strategy:

Step A — Find the peak index using binary search. At each midpoint, compare arr[mid] with arr[mid+1]. If the mid element is smaller, the peak is to the right. If larger, the peak is at mid or to the left.

Step B — Binary search the ascending half (indices 0 to peak) using standard binary search. If the target is found here, return this index (it is the minimum index because the ascending half comes first).

Step C — Binary search the descending half (indices peak+1 to n-1) using reversed binary search (where smaller values are to the right). If found here, return this index. Otherwise, return -1.

This approach uses at most log₂(n) + log₂(n) + log₂(n) = 3·log₂(n) calls, which for n = 10^4 is about 42 — comfortably within the 100-call budget.

Mountain array visualization showing ascending left half, peak, and descending right half with three binary search zones marked
Mountain array visualization showing ascending left half, peak, and descending right half with three binary search zones marked

Step-by-Step Explanation

Let's trace through with mountainArr = [1, 2, 3, 4, 5, 3, 1], target = 3:

Phase A: Find the Peak

Step 1: Initialize left = 0, right = 6.

Step 2: mid = (0 + 6) / 2 = 3. mountainArr.get(3) = 4, mountainArr.get(4) = 5. Since 4 < 5, the peak is to the right. Set left = 4.

Step 3: mid = (4 + 6) / 2 = 5. mountainArr.get(5) = 3, mountainArr.get(6) = 1. Since 3 > 1, the peak is at mid or to the left. Set right = 5.

Step 4: mid = (4 + 5) / 2 = 4. mountainArr.get(4) = 5, mountainArr.get(5) = 3. Since 5 > 3, set right = 4.

Step 5: left == right == 4. Peak found at index 4 (value 5).

Phase B: Binary Search Ascending Half [0..4]

Step 6: left = 0, right = 4. mid = 2. mountainArr.get(2) = 3. Is 3 == 3? Yes! Target found at index 2.

Step 7: Return 2. Since we searched the ascending half first (which has smaller indices), this is guaranteed to be the minimum index.

Triple Binary Search — Finding Target in Mountain Array — Watch the three-phase binary search: first find the peak, then search the ascending half, then (if needed) search the descending half.

Algorithm

  1. Find the peak index using binary search:

    • Initialize left = 0, right = n - 1
    • While left < right:
      • Compute mid = (left + right) / 2
      • If arr[mid] < arr[mid + 1], set left = mid + 1 (ascending, peak is to the right)
      • Else, set right = mid (descending or at peak, peak is at mid or to the left)
    • Peak index = left

  2. Binary search the ascending half [0, peak]:

    • Standard binary search for target
    • If arr[mid] < target, search right half
    • If arr[mid] > target, search left half
    • If arr[mid] == target, return mid

  3. If not found in ascending half, binary search the descending half [peak + 1, n - 1]:

    • Reversed binary search (descending order)
    • If arr[mid] > target, search right half (smaller values are to the right)
    • If arr[mid] < target, search left half
    • If arr[mid] == target, return mid

  4. If not found in either half, return -1

Code

/**
 * // This is the MountainArray's API interface.
 * class MountainArray {
 *   public:
 *     int get(int index);
 *     int length();
 * };
 */

class Solution {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int n = mountainArr.length();
        
        // Step 1: Find peak index
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        int peak = left;
        
        // Step 2: Binary search ascending half [0, peak]
        left = 0;
        right = peak;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = mountainArr.get(mid);
            if (val == target) return mid;
            else if (val < target) left = mid + 1;
            else right = mid - 1;
        }
        
        // Step 3: Binary search descending half [peak+1, n-1]
        left = peak + 1;
        right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = mountainArr.get(mid);
            if (val == target) return mid;
            else if (val > target) left = mid + 1;
            else right = mid - 1;
        }
        
        return -1;
    }
};
# """
# 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()
        
        # Step 1: Find peak index
        left, right = 0, n - 1
        while left < right:
            mid = (left + right) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                left = mid + 1
            else:
                right = mid
        peak = left
        
        # Step 2: Binary search ascending half [0, peak]
        left, right = 0, peak
        while left <= right:
            mid = (left + right) // 2
            val = mountain_arr.get(mid)
            if val == target:
                return mid
            elif val < target:
                left = mid + 1
            else:
                right = mid - 1
        
        # Step 3: Binary search descending half [peak+1, n-1]
        left, right = peak + 1, n - 1
        while left <= right:
            mid = (left + right) // 2
            val = mountain_arr.get(mid)
            if val == target:
                return mid
            elif val > target:
                left = mid + 1
            else:
                right = mid - 1
        
        return -1
/**
 * // This is MountainArray's API interface.
 * interface MountainArray {
 *     public int get(int index) {}
 *     public int length() {}
 * }
 */

class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        int n = mountainArr.length();
        
        // Step 1: Find peak index
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        int peak = left;
        
        // Step 2: Binary search ascending half [0, peak]
        left = 0;
        right = peak;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = mountainArr.get(mid);
            if (val == target) return mid;
            else if (val < target) left = mid + 1;
            else right = mid - 1;
        }
        
        // Step 3: Binary search descending half [peak+1, n-1]
        left = peak + 1;
        right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = mountainArr.get(mid);
            if (val == target) return mid;
            else if (val > target) left = mid + 1;
            else right = mid - 1;
        }
        
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(log n)

We perform three binary searches, each taking O(log n) time:

  • Finding the peak: O(log n) — each iteration halves the search space, making at most 2 calls to get()
  • Searching ascending half: O(log n) — standard binary search, at most 1 call to get() per iteration
  • Searching descending half: O(log n) — reversed binary search, at most 1 call to get() per iteration

Total: 3 × O(log n) = O(log n). For n = 10^4, this is about 3 × 14 = 42 calls at most, well within the 100-call limit.

Space Complexity: O(1)

We only use a constant number of variables (left, right, mid, peak, val). No auxiliary data structures are needed.