Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1095. Find in Mountain Array - Leetcode Solution

Code Implementation

# This is the Leetcode interface for MountainArray:
# class MountainArray:
#     def get(self, index: int) -> int:
#     def length(self) -> int:

class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        def find_peak():
            l, r = 0, mountain_arr.length() - 1
            while l < r:
                m = (l + r) // 2
                if mountain_arr.get(m) < mountain_arr.get(m + 1):
                    l = m + 1
                else:
                    r = m
            return l

        def binary_search(l, r, target, asc=True):
            while l <= r:
                m = (l + r) // 2
                val = mountain_arr.get(m)
                if val == target:
                    return m
                if asc:
                    if val < target:
                        l = m + 1
                    else:
                        r = m - 1
                else:
                    if val > target:
                        l = m + 1
                    else:
                        r = m - 1
            return -1

        peak = find_peak()
        # Search in ascending part
        idx = binary_search(0, peak, target, asc=True)
        if idx != -1:
            return idx
        # Search in descending part
        return binary_search(peak+1, mountain_arr.length()-1, target, asc=False)
      
/**
 * // 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 {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int n = mountainArr.length();
        // Find peak
        int l = 0, r = n - 1;
        while (l < r) {
            int m = (l + r) / 2;
            if (mountainArr.get(m) < mountainArr.get(m + 1))
                l = m + 1;
            else
                r = m;
        }
        int peak = l;
        // Binary search ascending
        int left = 0, right = peak;
        while (left <= right) {
            int m = (left + right) / 2;
            int val = mountainArr.get(m);
            if (val == target)
                return m;
            else if (val < target)
                left = m + 1;
            else
                right = m - 1;
        }
        // Binary search descending
        left = peak + 1, right = n - 1;
        while (left <= right) {
            int m = (left + right) / 2;
            int val = mountainArr.get(m);
            if (val == target)
                return m;
            else if (val > target)
                left = m + 1;
            else
                right = m - 1;
        }
        return -1;
    }
};
      
/**
 * // This is the 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();
        // Find peak
        int l = 0, r = n - 1;
        while (l < r) {
            int m = (l + r) / 2;
            if (mountainArr.get(m) < mountainArr.get(m + 1))
                l = m + 1;
            else
                r = m;
        }
        int peak = l;
        // Binary search ascending
        int left = 0, right = peak;
        while (left <= right) {
            int m = (left + right) / 2;
            int val = mountainArr.get(m);
            if (val == target)
                return m;
            else if (val < target)
                left = m + 1;
            else
                right = m - 1;
        }
        // Binary search descending
        left = peak + 1;
        right = n - 1;
        while (left <= right) {
            int m = (left + right) / 2;
            int val = mountainArr.get(m);
            if (val == target)
                return m;
            else if (val > target)
                left = m + 1;
            else
                right = m - 1;
        }
        return -1;
    }
}
      
/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * function MountainArray() {
 *     @return {number}
 *     this.get = function(index) {
 *         ...
 *     };
 *     @return {number}
 *     this.length = function() {
 *         ...
 *     };
 * }
 */

var findInMountainArray = function(target, mountainArr) {
    function findPeak() {
        let l = 0, r = mountainArr.length() - 1;
        while (l < r) {
            const m = Math.floor((l + r) / 2);
            if (mountainArr.get(m) < mountainArr.get(m + 1)) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }

    function binarySearch(l, r, target, asc = true) {
        while (l <= r) {
            const m = Math.floor((l + r) / 2);
            const val = mountainArr.get(m);
            if (val === target) return m;
            if (asc) {
                if (val < target) l = m + 1;
                else r = m - 1;
            } else {
                if (val > target) l = m + 1;
                else r = m - 1;
            }
        }
        return -1;
    }

    const peak = findPeak();
    let idx = binarySearch(0, peak, target, true);
    if (idx !== -1) return idx;
    return binarySearch(peak + 1, mountainArr.length() - 1, target, false);
};

Problem Description

Given a Mountain Array (an array that increases strictly to a single peak and then decreases strictly), you are to find the index of a given target value. You have access only through a special interface, MountainArray, which provides get(index) and length() methods. The goal is to return the smallest index where mountainArr.get(index) == target, or -1 if the target does not exist in the array.

Key constraints:
  • You cannot access the array directly—only via get() and length().
  • You should minimize the number of get() calls.
  • The array increases to a single peak, then decreases.
  • There is always exactly one peak.
  • Return the smallest index if the target appears more than once.

Thought Process

When first approaching this problem, you might think to just search the array from start to end, checking each value with get() to see if it matches the target. However, this would be inefficient, especially given the constraints on the number of calls to get().

Recognizing the "mountain" property is key. The array strictly increases to a peak, then strictly decreases. This means both halves of the array are sorted (one ascending, one descending), which allows us to use binary search techniques.

The main insight is to:
  • First, locate the peak using binary search.
  • Then, perform binary search for the target in the ascending part (left of the peak).
  • If not found, perform binary search in the descending part (right of the peak).
This approach leverages the sorted nature of each half to minimize get() calls.

Solution Approach

To solve the problem efficiently, we break it down into three main steps:
  1. Find the Peak Index:
    Use binary search to find the index of the peak (the maximum value). At each step, compare get(mid) and get(mid + 1):
    • If get(mid) < get(mid + 1), the peak is to the right, so move the left boundary to mid + 1.
    • Else, the peak is at mid or to the left, so move the right boundary to mid.
    When the search ends, left equals right, which is the peak index.
  2. Binary Search in the Ascending Part:
    Perform binary search from index 0 to peak (inclusive). Since this part is sorted in ascending order, use standard binary search:
    • If get(mid) == target, return mid.
    • If get(mid) < target, move left to mid + 1.
    • Else, move right to mid - 1.
  3. Binary Search in the Descending Part:
    If the target was not found in the ascending part, perform binary search from peak + 1 to length - 1. This part is sorted in descending order, so reverse the comparison:
    • If get(mid) == target, return mid.
    • If get(mid) > target, move left to mid + 1.
    • Else, move right to mid - 1.
If neither search finds the target, return -1.

This method ensures we use at most O(log n) get() calls for each search, which is efficient and meets the problem's constraints.

Example Walkthrough

Sample Input:
mountainArr = [1, 5, 9, 12, 8, 4, 2], target = 8

Step 1: Find the Peak
- Start with l = 0, r = 6.
- mid = 3, get(3) = 12, get(4) = 8 → 12 > 8, so peak is at or before 3. Set r = 3.
- l = 0, r = 3; mid = 1, get(1) = 5, get(2) = 9 → 5 < 9, so peak is after 1. Set l = 2.
- l = 2, r = 3; mid = 2, get(2) = 9, get(3) = 12 → 9 < 12, so peak is after 2. Set l = 3.
- Now l = r = 3, so the peak is at index 3 (12).

Step 2: Binary Search Ascending (indices 0 to 3)
- l = 0, r = 3; mid = 1, get(1) = 5 < 8, so l = 2.
- l = 2, r = 3; mid = 2, get(2) = 9 > 8, so r = 1.
- Search ends, not found.

Step 3: Binary Search Descending (indices 4 to 6)
- l = 4, r = 6; mid = 5, get(5) = 4 < 8, so (descending) r = 4.
- l = 4, r = 4; mid = 4, get(4) = 8 == 8, found at index 4.

Result: Return 4 (the index of 8).

Time and Space Complexity

Brute-force Approach:
- Time Complexity: O(n) (you would check every element with get() up to n times).
- Space Complexity: O(1) (no extra space needed).

Optimized Approach (Binary Search):
- Time Complexity: O(log n) for peak-finding + O(log n) for each binary search = O(log n) overall.
- Space Complexity: O(1) (no extra space used).

The binary search approach is much more efficient, especially for large arrays, and crucially reduces the number of get() calls.

Summary

The "Find in Mountain Array" problem leverages the unique structure of the mountain array—strictly increasing to a peak, then strictly decreasing. By first finding the peak with binary search, then searching for the target in each sorted half, we reduce the number of interface calls and achieve logarithmic time complexity. The solution is elegant because it combines multiple binary searches, each tailored to the array's order, and makes optimal use of the available interface.