Find in Mountain Array
Hard · Binary Search · Explanation and code example
Binary Search + Caching
How it works
The MountainArray API may have limited calls or expensive operations. During peak-finding, we query values at mid - 1, mid, and mid + 1, and some of these indices may be queried again in subsequent binary searches. By caching previously retrieved values, we avoid redundant API calls. This is particularly useful when the peak-finding phase overlaps with the search regions.
Steps
- Create a cache (hash map) to store retrieved values.
- Implement a cached
getfunction that checks the cache before calling the API. - Find the peak using binary search with the cached getter.
- Implement a generic binary search helper that takes an
ascendingparameter to handle both increasing and decreasing portions. - Search the ascending left portion first; if found, return immediately.
- Search the descending right portion and return the result.
Complexity
- Time complexity:
O(log n) - Space complexity:
O(log n)
Things to watch for
Searching Right Side Before Left Side
Since the problem requires returning the minimum index when the target appears multiple times, you must search the ascending (left) portion first. If you search the descending (right) portion first or return the first match found without considering index order, you may return a larger index when a smaller one exists.
Incorrect Binary Search Direction for Descending Portion
When searching the descending right portion of the mountain, the binary search logic must be reversed. In an ascending array, smaller values are on the left; in a descending array, smaller values are on the right. Forgetting to flip the comparison logic will cause the search to move in the wrong direction.
Off-by-One Errors in Peak Finding
When finding the peak, the search bounds should be [1, length - 2] to ensure safe access to mid - 1 and mid + 1. Using [0, length - 1] can cause index out of bounds errors. Additionally, ensure the peak is correctly identified as the element greater than both neighbors, not just one.
Exceeding API Call Limits
The problem often restricts the number of get() calls (e.g., 100 calls). Without caching, you may query the same index multiple times during peak finding and subsequent searches. Implementing a cache to store previously retrieved values prevents exceeding the call limit and avoids time limit issues.
Not Handling Target at Peak Position
The target might be at the peak itself. If your left portion search excludes the peak and your right portion search also misses it due to boundary conditions, the target at the peak will never be found. Ensure at least one of your searches includes the peak index in its range.
Python code example
from functools import cache
# """
# 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, mountainArr: 'MountainArray') -> int:
length = mountainArr.length()
cache = {}
def get(i):
if i not in cache:
cache[i] = mountainArr.get(i)
return cache[i]
# Find Peak
l, r = 1, length - 2
while l <= r:
m = (l + r) >> 1
left, mid, right = get(m - 1), get(m), get(m + 1)
if left < mid < right:
l = m + 1
elif left > mid > right:
r = m - 1
else:
break
peak = m
def binary_search(l, r, ascending):
while l <= r:
m = (l + r) >> 1
val = get(m)
if val == target:
return m
if ascending == (val < target):
l = m + 1
else:
r = m - 1
return -1
# Search left portion
res = binary_search(0, peak, True)
if res != -1:
return res
# Search right portion
return binary_search(peak, length - 1, False)
C++ code example
/**
* // 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 {
private:
unordered_map<int, int> cache;
int get(int index, MountainArray &mountainArr) {
if (cache.find(index) == cache.end()) {
cache[index] = mountainArr.get(index);
}
return cache[index];
}
int binarySearch(int l, int r, bool ascending, int target, MountainArray &mountainArr) {
while (l <= r) {
int m = (l + r) >> 1;
int val = get(m, mountainArr);
if (val == target) {
return m;
}
if (ascending == (val < target)) {
l = m + 1;
} else {
r = m - 1;
}
}
return -1;
}
public:
int findInMountainArray(int target, MountainArray &mountainArr) {
int length = mountainArr.length();
// Find Peak
int l = 1, r = length - 2, peak = 0;
while (l <= r) {
int m = (l + r) >> 1;
int left = get(m - 1, mountainArr);
int mid = get(m, mountainArr);
int right = get(m + 1, mountainArr);
if (left < mid && mid < right) {
l = m + 1;
} else if (left > mid && mid > right) {
r = m - 1;
} else {
peak = m;
break;
}
}
// Search left portion
int res = binarySearch(0, peak, true, target, mountainArr);
if (res != -1) {
return res;
}
// Search right portion
return binarySearch(peak, length - 1, false, target, mountainArr);
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.