> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Find in Mountain Array Python Solution

> Tested Python solution for LeetCode 1095 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 1095, Hard. Topics: Array, Binary Search, Interactive. [View on LeetCode](https://leetcode.com/problems/find-in-mountain-array/description/).

Generate this problem as a practice environment: tested reference solution, 16 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1095   # by problem number
lcpy gen -s find_in_mountain_array   # by problem name
```

## 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*.

### Examples

```
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.
```

```
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() <= 10^4`
* `0 <= target <= 10^9`
* `0 <= mountainArr.get(index) <= 10^9`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_in_mountain_array/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_in_mountain_array/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class MountainArray:
    def get(self, index: int) -> int:
        raise NotImplementedError

    def length(self) -> int:
        raise NotImplementedError


class Solution:
    # Time: O(log n) — three binary searches (peak, ascending side, descending side)
    # Space: O(1)
    def find_in_mountain_array(self, target: int, mountain_arr: MountainArray) -> int:
        n = mountain_arr.length()

        # 1. Find the peak index (mountainArr is strictly increasing then decreasing).
        lo, hi = 1, n - 2
        while lo < hi:
            mid = (lo + hi) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                lo = mid + 1
            else:
                hi = mid
        peak = lo

        # 2. Binary search the strictly ascending left slope for target (min index).
        lo, hi = 0, peak
        while lo <= hi:
            mid = (lo + hi) // 2
            value = mountain_arr.get(mid)
            if value == target:
                return mid
            if value < target:
                lo = mid + 1
            else:
                hi = mid - 1

        # 3. Binary search the strictly descending right slope for target.
        lo, hi = peak + 1, n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            value = mountain_arr.get(mid)
            if value == target:
                return mid
            if value > target:
                lo = mid + 1
            else:
                hi = mid - 1

        return -1
```

## Complexity

| Time                                                                     | Space |
| ------------------------------------------------------------------------ | ----- |
| O(log n) — three binary searches (peak, ascending side, descending side) | O(1)  |

## Tags

[NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).