# LeetCode 1095. Find in Mountain Array

## Description

https://leetcode.com/problems/find-in-mountain-array/

(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: array = [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: array = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 3 does not exist in `the array,` so we return -1.
```

Constraints:

• `3 <= mountain_arr.length() <= 104`
• `0 <= target <= 109`
• `0 <= mountain_arr.get(index) <= 109`

## Explanation

Find the peak of the mountain first. If the target is the peak of the mountain, return the peak index. If the target is greater than the peak, return -1. Otherwise, use binary search on the uphill of the mountain first, if the target is still not found, search on the downhill of the mountain.

## Python Solution

``````# """
# 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:
if mountain_arr.get(0) == target:
return 0

peak_idx = self.find_peak(mountain_arr)

if mountain_arr.get(peak_idx) < target:
return -1

left = self.binary_search(target, mountain_arr, 0, peak_idx - 1, True)
if left != -1:
return left

if mountain_arr.get(peak_idx) == target:
return peak_idx

right = self.binary_search(target, mountain_arr, peak_idx, mountain_arr.length() - 1, False)

if right != -1:
return right

return -1

def find_peak(self, mountain_arr):
peak = -1

start = 0
end = mountain_arr.length() - 1

while start + 1 < end:
mid = (start + end) // 2

if mountain_arr.get(mid - 1) < mountain_arr.get(mid) and mountain_arr.get(mid) > mountain_arr.get(mid + 1):
return mid
elif mountain_arr.get(mid) < mountain_arr.get(mid - 1):
end = mid
elif mountain_arr.get(mid) < mountain_arr.get(mid + 1):
start = mid

if mountain_arr.get(start) > mountain_arr.get(end):
peak = start
else:
peak = end

return peak

def binary_search(self, target, mountain_arr, start, end, is_increasing=True):

while start + 1 < end:
mid = (start + end) // 2

if mountain_arr.get(mid) == target:
end = mid
elif mountain_arr.get(mid) < target:
if is_increasing:
start = mid
else:
end = mid
else:
if is_increasing:
end = mid
else:
start = mid

if mountain_arr.get(start) == target:
return start

if mountain_arr.get(end) == target:
return end

return -1``````
• Time Complexity: O(log(N)).
• Space Complexity: O(1).