Tech Blogs LLD SDE Playbook DSA

Find in Mountain Array

Hard Top 250
Associated Patterns
Binary Search
Interviewed At (Company Tags)
GoogleAmazonMicrosoft
External Reference View on LeetCode

Problem Description

You may recall that an array arr is a mountain array if and only if:

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

Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target. If such an index does not exist, return -1.

You cannot access the mountain array directly. You may only access the array using a MountainArray interface:

  • MountainArray.get(k) returns the element of the array at index k (0-indexed).
  • MountainArray.length() returns the length of the array.

Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer.

Examples

Example 1:

Input: array = [1,2,3,4,5,3,1], target = 3 Output: 2 Explanation: 3 exists in the array at index 2 and index 5. The minimum index is 2.

Example 2:

Input: array = [0,1,2,4,2,1], target = 3 Output: -1 Explanation: 3 does not exist in the array.

Constraints

  • 3 <= mountainArr.length() <= 10⁴
  • 0 <= target <= 10⁹
  • 0 <= mountainArr.get(index) <= 10⁹

To solve this within the 100 API call limit, we use a three-step binary search strategy:

  1. Find the Peak Index: Run binary search to find the peak of the mountain. At each step, compare arr[mid] with arr[mid + 1]. If arr[mid] < arr[mid + 1], we are in the rising slope, so the peak is to the right; otherwise, we are in the falling slope, so the peak is at or to the left of mid.
  2. Search the Rising Slope: Run standard binary search for the target on the sorted increasing left half [0, peak]. If found, return the index immediately.
  3. Search the Falling Slope: If not found on the left, run binary search on the decreasing right half [peak + 1, n - 1]. Note that the comparison logic is reversed because the slope is decreasing.

Locate the peak of the mountain array, then execute binary search on both slopes.

/**
 * // This is MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface MountainArray {
 *     public int get(int index);
 *     public int length();
 * }
 */

class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        int n = mountainArr.length();
        
        // 1. Find peak index
        int peak = findPeak(mountainArr, 0, n - 1);

        // 2. Binary search on the rising left slope
        int leftIdx = binarySearch(mountainArr, target, 0, peak, true);
        if (leftIdx != -1) return leftIdx;

        // 3. Binary search on the falling right slope
        return binarySearch(mountainArr, target, peak + 1, n - 1, false);
    }

    private int findPeak(MountainArray arr, int left, int right) {
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr.get(mid) < arr.get(mid + 1)) {
                left = mid + 1; // peak is on the right
            } else {
                right = mid; // peak is on the left (or is mid itself)
            }
        }
        return left;
    }

    private int binarySearch(MountainArray arr, int target, int left, int right, boolean ascending) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = arr.get(mid);
            if (val == target) {
                return mid;
            }
            if (ascending) {
                if (val < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                if (val > target) {
                    left = mid + 1; // since descending, target is further right
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}
# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
# 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()
        
        # Find peak index
        left, right = 0, n - 1
        while left < right:
            mid = left + (right - left) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                left = mid + 1
            else:
                right = mid
        peak = left
        
        # Binary search on ascending half
        left, right = 0, peak
        while left <= right:
            mid = left + (right - left) // 2
            val = mountain_arr.get(mid)
            if val == target:
                return mid
            elif val < target:
                left = mid + 1
            else:
                right = mid - 1
                
        # Binary search on descending half
        left, right = peak + 1, n - 1
        while left <= right:
            mid = left + (right - left) // 2
            val = mountain_arr.get(mid)
            if val == target:
                return mid
            elif val > target:  # descending check
                left = mid + 1
            else:
                right = mid - 1
                
        return -1
/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * class MountainArray {
 *   public:
 *     int get(int index);
 *     int length();
 * };
 */

class Solution {
private:
    int findPeak(MountainArray& arr, int left, int right) {
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr.get(mid) < arr.get(mid + 1)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    int binarySearch(MountainArray& arr, int target, int left, int right, bool ascending) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = arr.get(mid);
            if (val == target) return mid;
            if (ascending) {
                if (val < target) left = mid + 1;
                else right = mid - 1;
            } else {
                if (val > target) left = mid + 1;
                else right = mid - 1;
            }
        }
        return -1;
    }

public:
    int findInMountainArray(int target, MountainArray& mountainArr) {
        int n = mountainArr.length();
        int peak = findPeak(mountainArr, 0, n - 1);

        int leftIdx = binarySearch(mountainArr, target, 0, peak, true);
        if (leftIdx != -1) return leftIdx;

        return binarySearch(mountainArr, target, peak + 1, n - 1, false);
    }
};

Complexity Analysis

  • Time Complexity: O(log n) since we execute exactly three binary search phases, each taking O(log n) API calls.
  • Space Complexity: O(1) auxiliary space as we track boundaries using simple variables.

Where It Breaks

If the array is not a valid single-peak mountain (e.g. contains multiple local peaks or flat plateaus), the peak finding step fails.

Common Mistakes

  • Incorrect binary search logic on decreasing slope: Using ascending slope conditions (val < target shifts right) on the decreasing slope, which fails to locate elements.
  • Too many API calls: Calling mountainArr.get repeatedly inside loops instead of caching or comparing adjacent midpoints once, exceeding the 100 call limit.

Frequently Asked Questions

Why does Koko take a peak finding approach? Because the left and right halves are sorted in opposite directions, locating the peak allows us to partition the problem into two standard sorted sub-searches.

What happens if target is at the peak? The binary search on the rising left slope [0, peak] will find it at the peak index and return it.

← All Problems