NeetCode #300LC-1095HardBinary SearchNC 250
← Back to All Problems#300 · #1095 · Find in Mountain Array(山脉数组中查找目标值)
📌 Problem Statement & Constraints
This is an interactive problem. A
MountainArray is strictly increasing then strictly decreasing. Given a target, return the minimum index where it appears, or -1. You may call get(k) at most 100 times, and length() once. Constraints: 3 <= length <= 10^4, 0 <= target <= 10^9.💡 Core Algorithmic Approaches
- Three binary searches. First, find the peak: compare
get(mid)withget(mid+1); if increasing, the peak is to the right, otherwise at or left ofmid. - Second, binary search the increasing left side
[0, peak]for the target. - Third, binary search the decreasing right side
[peak, n-1], inverting the comparison. - Searching the left side first is required because the problem asks for the minimum index.
💻 Benchmark Python3 Implementation
class Solution:
def findInMountainArray(self, target: int, mountainArr: "MountainArray") -> int:
n = mountainArr.length()
# 1) find the peak
lo, hi = 0, n - 1
while lo < hi:
mid = (lo + hi) // 2
if mountainArr.get(mid) < mountainArr.get(mid + 1):
lo = mid + 1 # still ascending
else:
hi = mid
peak = lo
# 2) ascending side [0, peak]
lo, hi = 0, peak
while lo <= hi:
mid = (lo + hi) // 2
v = mountainArr.get(mid)
if v == target:
return mid # minimum index by construction
if v < target:
lo = mid + 1
else:
hi = mid - 1
# 3) descending side [peak, n-1]
lo, hi = peak, n - 1
while lo <= hi:
mid = (lo + hi) // 2
v = mountainArr.get(mid)
if v == target:
return mid
if v > target: # descending -> go right for smaller values
lo = mid + 1
else:
hi = mid - 1
return -1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(log n) calls to get: three binary searches, about 3 * log2(10^4) ≈ 42 calls, within the 100-call budget.
💾 Space Complexity
O(1): a few indices.
⚠️ Interview Pitfalls & Follow-ups
- Searching the descending side first: the answer must be the minimum index, so the ascending side must be checked first.
- Inverting the comparison on the descending side: there, smaller values are to the right, so
v > targetmeans move right. - Off-by-one in the peak search: the comparison is between
get(mid)andget(mid+1), which requiresmid < n - 1; the loop conditionlo < higuarantees it. - Exceeding the call budget: caching
getresults or using a helper is wise if the budget were tighter; three binary searches fit comfortably here.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.