Find in Mountain Array — LeetCode 1095 Python Solution
HardArrayBinary SearchInteractive
- Problem
- #1095
- Pattern
- Monotonic Stack
- Reading time
- 5 min
- Source
- leetcode.com
The 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] > ...
Example
- 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.
Python solution
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 ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(log n) or O(n log n) |
| Space | O(1) auxiliary |
Pattern: Monotonic Stack
Answer "what is the next greater element" for every position in one pass. LeetCode 1095. Find in Mountain Array is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1095. Find in Mountain Array?
- LeetCode 1095. Find in Mountain Array is rated Hard on LeetCode.
- What topics does LeetCode 1095. Find in Mountain Array cover?
- LeetCode 1095. Find in Mountain Array is tagged Array, Binary Search and Interactive on LeetCode.