# Find in Mountain Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-in-mountain-array)
Canonical: https://scaleengineer.com/dsa/problems/find-in-mountain-array
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## Problem
_(This problem is an **interactive problem**.)_

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_. Also, any solutions that attempt to circumvent the judge will result in disqualification.

**Example 1:**

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

**Example 2:**

**Input:** mountainArr = [0,1,2,4,2,1], target = 3
**Output:** -1
**Explanation:** 3 does not exist in `the array,` so we return -1.

**Constraints:**

* `3 <= mountainArr.length() <= 104`
* `0 <= target <= 109`
* `0 <= mountainArr.get(index) <= 109`

# Approaches
## Linear Scan (Brute Force)
This is a straightforward brute-force approach where we iterate through the array from the beginning to the end. For each index `i`, we call `mountainArr.get(i)` and check if its value equals the `target`. Since we are looking for the minimum index, the first match we find will be our answer.
**Time:** O(N), where N is the length of the array. In the worst-case scenario, we might have to scan the entire array. · **Space:** O(1), as we only use a constant amount of extra space for loop variables.
**Pros:** Very simple to understand and implement.; Guaranteed to find the minimum index if the target exists.
**Cons:** Highly inefficient for large arrays.; Exceeds the problem's constraint of 100 calls to `MountainArray.get`, making it an invalid solution for this specific problem.
### Explanation
The algorithm iterates from index `i = 0` to `mountainArr.length() - 1`. In each iteration, it retrieves the element `mountainArr.get(i)` and compares this element with the `target`. If they are equal, it means we have found the target. Since we are iterating from the left, the first occurrence found will be at the minimum index, so we can immediately return `i`. If the loop completes without finding the `target`, it means the target is not in the array, and we return `-1`.

```java
/**
 * // 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();
        for (int i = 0; i < n; i++) {
            if (mountainArr.get(i) == target) {
                return i;
            }
        }
        return -1;
    }
}
```
### Algorithm
- Get the length of the array, `n = mountainArr.length()`.
- Loop for `i` from `0` to `n - 1`.
- In each iteration, get `current_element = mountainArr.get(i)`.
- If `current_element == target`, we have found the first occurrence. Return the current index `i`.
- If the loop completes without finding the target, return `-1`.

## Three-Step Binary Search
This is an efficient approach that fully leverages the special structure of the mountain array. The strategy is to first locate the peak of the mountain and then perform two separate binary searches on the two slopes (the increasing part and the decreasing part). This approach is highly efficient and respects the 100-call limit on `mountainArr.get()`.
**Time:** O(log N). Finding the peak takes O(log N), and the two subsequent binary searches also take O(log N) each. The total complexity is O(log N). · **Space:** O(1). We only use a constant amount of extra space for variables like `left`, `right`, `mid`, and `peakIndex`.
**Pros:** Extremely efficient, with logarithmic time complexity.; Stays well within the 100 API call limit.; Guaranteed to find the minimum index because it searches the increasing part first.
**Cons:** More complex to implement compared to a linear scan.; Requires careful implementation of three separate binary search variations (peak finding, increasing search, decreasing search).
### Explanation
The problem can be solved efficiently by breaking it down into three main steps:

1.  **Find the Peak Index:** The array consists of an increasing sequence followed by a decreasing one. The peak is the largest element. We can find its index using a modified binary search in O(log N) time. By comparing `mountainArr.get(mid)` with `mountainArr.get(mid + 1)`, we can determine if we are on the increasing or decreasing slope and narrow our search space accordingly.

2.  **Search in the Increasing Part:** With the `peakIndex`, we know the subarray from `0` to `peakIndex` is sorted in increasing order. We can run a standard binary search for the `target` here. If found, we return the index. This will be the minimum index since we search this part first.

3.  **Search in the Decreasing Part:** If the target isn't in the first part, we search the decreasing slope from `peakIndex` to `n-1`. This requires a binary search adapted for a decreasingly sorted array. If the target is found, we return its index.

If both searches fail, the target is not in the array, and we return -1.

```java
/**
 * // 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();
        
        // 1. Find the peak index
        int left = 0, right = n - 1;
        int peakIndex = 0;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        peakIndex = left;
        
        // 2. Search in the increasing part (left of the peak)
        left = 0;
        right = peakIndex;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midVal = mountainArr.get(mid);
            if (midVal == target) {
                return mid;
            } else if (midVal < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        // 3. Search in the decreasing part (right of the peak)
        left = peakIndex;
        right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midVal = mountainArr.get(mid);
            if (midVal == target) {
                return mid;
            } else if (midVal < target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return -1;
    }
}
```
### Algorithm
1.  **Find Peak Index:**
    - Use binary search on the indices `0` to `n-1` to find the peak element's index.
    - For a `mid` index, if `mountainArr.get(mid) < mountainArr.get(mid + 1)`, the peak is to the right, so we search in `[mid + 1, right]`.
    - Otherwise, the peak is at or to the left of `mid`, so we search in `[left, mid]`.
    - The loop terminates when `left == right`, which gives the `peakIndex`.
2.  **Search Left Slope (Increasing Part):**
    - Perform a standard binary search for the `target` in the range `[0, peakIndex]`.
    - If the target is found, return its index immediately. This is the minimum index.
3.  **Search Right Slope (Decreasing Part):**
    - If the target was not found on the left slope, perform a modified binary search for the `target` in the range `[peakIndex, n - 1]`.
    - The modification accounts for the decreasing order of elements.
    - If the target is found, return its index.
4.  **Return -1:**
    - If the target is not found in either search, it doesn't exist in the array. Return `-1`.

# Solutions
### Java

```java
/** * // 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 { private MountainArray mountainArr ; private int target ; public int findInMountainArray ( int target , MountainArray mountainArr ) { int n = mountainArr . length (); int l = 0 , r = n - 1 ; while ( l < r ) { int mid = ( l + r ) >>> 1 ; if ( mountainArr . get ( mid ) > mountainArr . get ( mid + 1 )) { r = mid ; } else { l = mid + 1 ; } } this . mountainArr = mountainArr ; this . target = target ; int ans = search ( 0 , l , 1 ); return ans == - 1 ? search ( l + 1 , n - 1 , - 1 ) : ans ; } private int search ( int l , int r , int k ) { while ( l < r ) { int mid = ( l + r ) >>> 1 ; if ( k * mountainArr . get ( mid ) >= k * target ) { r = mid ; } else { l = mid + 1 ; } } return mountainArr . get ( l ) == target ? l : - 1 ; } }
```

### CPP

```cpp
/** * // 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 (); int l = 0 , r = n - 1 ; while ( l < r ) { int mid = ( l + r ) >> 1 ; if ( mountainArr . get ( mid ) > mountainArr . get ( mid + 1 )) { r = mid ; } else { l = mid + 1 ; } } auto search = [ & ]( int l , int r , int k ) -> int { while ( l < r ) { int mid = ( l + r ) >> 1 ; if ( k * mountainArr . get ( mid ) >= k * target ) { r = mid ; } else { l = mid + 1 ; } } return mountainArr . get ( l ) == target ? l : - 1 ; }; int ans = search ( 0 , l , 1 ); return ans == - 1 ? search ( l + 1 , n - 1 , - 1 ) : ans ; } };
```

### Python

```python
# """ # 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 : def search ( l : int , r : int , k : int ) -> int : while l < r : mid = ( l + r ) >> 1 if k * mountain_arr . get ( mid ) >= k * target : r = mid else : l = mid + 1 return - 1 if mountain_arr . get ( l ) != target else l n = mountain_arr . length () l , r = 0 , n - 1 while l < r : mid = ( l + r ) >> 1 if mountain_arr . get ( mid ) > mountain_arr . get ( mid + 1 ): r = mid else : l = mid + 1 ans = search ( 0 , l , 1 ) return search ( l + 1 , n - 1 , - 1 ) if ans == - 1 else ans
```