Find in Mountain Array solution and explanation
Google
9 more videos on this problem
Find in Mountain Array - Leetcode 1095 - PythonNeetCodeIO · 12:39 · 19K views
Find in Mountain Array | Binary Search | Using Same Code | AMAZON | Leetcode - 1095codestorywithMIK · 19:18 · 8K views
1095. Find in Mountain Array (LeetCode Weekly Contest 142)Kelvin Chandra · 7:55 · 4K views
LeetCode 1095. Find in Mountain ArrayHappy Coding · 19:33 · 1K views
Find in Mountain Array - Java - Binary Search - 1095 LeetCode hard in 15 mins - ExplainedLeet Logics · 15:56 · 774 views
1095. Find in Mountain Array | Leetcode daily challengeRuntime Error · 18:35 · 724 views
1095. Find in Mountain Array | HARD | Hindi | Java Binary SearchUdyan is here · 12:59 · 623 views
1095. Find in Mountain Array | Leetcode | Searching | DSACoding with Tamilarasan · 16:06 · 473 views
Code EveryDay | Array, Binary Search | Asked in: Google, Amazon | 1095 Find in Mountain ArrayProgramming Pathshala · 45:49 · 344 views
LeetCode 1095. [HARD] Find in Mountain ArrayFrancesco Manicardi · 4:43 · 299 views
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
iwith0 < i < arr.length - 1such 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 indexk(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: 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.
Example 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() <= 1040 <= target <= 1090 <= mountainArr.get(index) <= 109
Approach overview
Problem Overview: You are given a mountain array where values strictly increase to a peak and then strictly decrease. The task is to find the index of a target value using only the provided MountainArray.get() API while minimizing calls to the array.
Approach 1: Brute-force Linear Scan (O(n) time, O(1) space)
The simplest strategy is to iterate through the array from index 0 to n - 1 and call get(i) for each position. If the returned value matches the target, return the index immediately. This approach works because every element is checked exactly once. However, the problem is interactive and restricts the number of API calls, so scanning the entire array can exceed the allowed limit for large inputs. Time complexity is O(n) and extra space is O(1). This approach mainly helps verify correctness before optimizing.
Approach 2: Binary Search with Peak Finding (O(log n) time, O(1) space)
A mountain array has two sorted regions: strictly increasing before the peak and strictly decreasing after it. First locate the peak index using binary search. Compare get(mid) with get(mid + 1). If the sequence is rising, move right; otherwise move left. This identifies the maximum element in O(log n) calls.
Once the peak is known, run two separate binary searches. Search the left side [0, peak] as a normal ascending array. If the target is not found, search the right side [peak + 1, n - 1] but reverse the comparison logic because that portion is descending. Each search takes O(log n), keeping the total time complexity O(log n) and space O(1).
This approach leverages the structural guarantee of a mountain array instead of scanning blindly. It also minimizes calls to the MountainArray interface, which is critical for interactive problems. The algorithm mainly relies on concepts from arrays and interactive problems where API usage is constrained.
Recommended for interviews: Binary search with peak finding is the expected solution. Interviewers want to see that you recognize the two monotonic segments and apply binary search correctly on both sides. Showing the brute-force scan first demonstrates baseline reasoning, but the optimized O(log n) approach proves you understand how to exploit problem structure.
Approach 1: Binary Search with Peak Finding
In this approach, the task is broken into three main steps:
- First, find the peak element of the mountain array using binary search. The peak is defined as the highest element where
arr[i] > arr[i+1]andarr[i] > arr[i-1]. - Once the peak is identified, the array is split into two parts: one is increasing and the other is decreasing. Perform binary search separately on these two parts.
- On the increasing part of the array (from the start to the peak), perform binary search for the target. If found, note the index.
- On the decreasing part of the array (from peak to the end), perform a descending order binary search for the target. If found, compare the index with the previously found index in the increasing part to ensure the minimum index is returned.
class MountainArray:
def get(self, index: int) -> int:
# Return the element at index in the mountain array.
pass
def length(self) -> int:
# Return the length of the mountain array.
pass
class Solution:
def findPeakIndex(self, mountainArr: 'MountainArray') -> int:
left, right = 0, mountainArr.length() - 1
while left < right:
mid = left + (right - left) // 2
if mountainArr.get(mid) < mountainArr.get(mid + 1):
left = mid + 1
else:
right = mid
return left
def binarySearch(self, mountainArr: 'MountainArray', start: int, end: int, target: int, is_ascending: bool) -> int:
while start <= end:
mid = start + (end - start) // 2
value = mountainArr.get(mid)
if value == target:
return mid
if is_ascending:
if value < target:
start = mid + 1
else:
end = mid - 1
else:
if value > target:
start = mid + 1
else:
end = mid - 1
return -1
def findInMountainArray(self, target: int, mountainArr: 'MountainArray') -> int:
peak = self.findPeakIndex(mountainArr)
index = self.binarySearch(mountainArr, 0, peak, target, True)
if index != -1:
return index
return self.binarySearch(mountainArr, peak + 1, mountainArr.length() - 1, target, False)interface MountainArray {
int get(int index);
int length();
}
public class Solution {
private int findPeakIndex(MountainArray mountainArr) {
int left = 0;
int right = mountainArr.length() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
private int binarySearch(MountainArray mountainArr, int start, int end, int target, boolean isAscending) {
while (start <= end) {
int mid = start + (end - start) / 2;
int value = mountainArr.get(mid);
if (value == target) {
return mid;
}
if (isAscending) {
if (value < target) {
start = mid + 1;
} else {
end = mid - 1;
}
} else {
if (value > target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
public int findInMountainArray(int target, MountainArray mountainArr) {
int peak = findPeakIndex(mountainArr);
int index = binarySearch(mountainArr, 0, peak, target, true);
if (index != -1) {
return index;
}
return binarySearch(mountainArr, peak + 1, mountainArr.length() - 1, target, false);
}
}#include <iostream>
#include <vector>
using namespace std;
// Mockup of MountainArray, simulating interface.
class MountainArray {
public:
int get(int index) const;
int length() const;
};
int findPeakIndex(const MountainArray &mountainArr) {
int left = 0;
int right = mountainArr.length() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
int binarySearch(const MountainArray &mountainArr, int start, int end, int target, bool isAscending) {
while (start <= end) {
int mid = start + (end - start) / 2;
int value = mountainArr.get(mid);
if (value == target) {
return mid;
}
if (isAscending) {
if (value < target) {
start = mid + 1;
} else {
end = mid - 1;
}
} else {
if (value > target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
int findInMountainArray(int target, const MountainArray &mountainArr) {
int peak = findPeakIndex(mountainArr);
int index = binarySearch(mountainArr, 0, peak, target, true);
if (index != -1) {
return index;
}
return binarySearch(mountainArr, peak + 1, mountainArr.length() - 1, target, false);
}class MountainArray {
get(index) {
// Returns the element of the array at index 'index'.
}
length() {
// Returns the number of elements in the mountain array.
}
}
class Solution {
findPeakIndex(mountainArr) {
let left = 0;
let right = mountainArr.length() - 1;
while (left < right) {
const mid = Math.floor(left + (right - left) / 2);
if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
binarySearch(mountainArr, start, end, target, isAscending) {
while (start <= end) {
const mid = Math.floor(start + (end - start) / 2);
const value = mountainArr.get(mid);
if (value === target) {
return mid;
}
if (isAscending) {
if (value < target) {
start = mid + 1;
} else {
end = mid - 1;
}
} else {
if (value > target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
findInMountainArray(target, mountainArr) {
const peak = this.findPeakIndex(mountainArr);
let index = this.binarySearch(mountainArr, 0, peak, target, true);
if (index !== -1) {
return index;
}
return this.binarySearch(mountainArr, peak + 1, mountainArr.length() - 1, target, false);
}
}#include <stdio.h>
// Forward declaration of the MountainArray API.
// You don't need to implement this interface, it is provided by the problem constraints.
struct MountainArray {
int (*get)(struct MountainArray*, int index);
int (*length)(struct MountainArray*);
};
int findPeakIndex(struct MountainArray* mountainArr) {
int left = 0;
int right = mountainArr->length(mountainArr) - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (mountainArr->get(mountainArr, mid) < mountainArr->get(mountainArr, mid + 1)) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
int binarySearch(struct MountainArray* mountainArr, int start, int end, int target, int isAscending) {
while (start <= end) {
int mid = start + (end - start) / 2;
int value = mountainArr->get(mountainArr, mid);
if (value == target) {
return mid;
}
if (isAscending) {
if (value < target) {
start = mid + 1;
} else {
end = mid - 1;
}
} else {
if (value > target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
int findInMountainArray(int target, struct MountainArray* mountainArr) {
int peak = findPeakIndex(mountainArr);
int index = binarySearch(mountainArr, 0, peak, target, 1);
if (index != -1) {
return index;
}
return binarySearch(mountainArr, peak + 1, mountainArr->length(mountainArr) - 1, target, 0);
}public interface MountainArray {
int Get(int index);
int Length();
}
public class Solution {
private int FindPeakIndex(MountainArray mountainArr) {
int left = 0;
int right = mountainArr.Length() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (mountainArr.Get(mid) < mountainArr.Get(mid + 1)) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
private int BinarySearch(MountainArray mountainArr, int start, int end, int target, bool isAscending) {
while (start <= end) {
int mid = start + (end - start) / 2;
int value = mountainArr.Get(mid);
if (value == target) {
return mid;
}
if (isAscending) {
if (value < target) {
start = mid + 1;
} else {
end = mid - 1;
}
} else {
if (value > target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
public int FindInMountainArray(int target, MountainArray mountainArr) {
int peak = FindPeakIndex(mountainArr);
int index = BinarySearch(mountainArr, 0, peak, target, true);
if (index != -1) {
return index;
}
return BinarySearch(mountainArr, peak + 1, mountainArr.Length() - 1, target, false);
}
}The Python implementation follows the same logic as the previously described solutions: a binary search to find the peak, followed by two additional binary searches on the segregated parts of the array to locate the target efficiently.
Time Complexity: O(log n) for peak finding, with a further 2 * O(log n) for the binary searches.
Overall complexity: O(log n).
Space Complexity: O(1), no extra space is required for operation.
Approach 2: Brute-force Approach
This approach involves directly accessing each element linearly until the condition is satisfied (even though this is not allowed by the problem constraints). It is less optimal and efficient compared to the above implementations, requiring traversal of the entire array.
class MountainArray:
def get(self, index: int) -> int:
# Return the element at index in the mountain array.
pass
def length(self) -> int:
# Return the length of the mountain array.
pass
class Solution:
def findInMountainArray(self, target: int, mountainArr: 'MountainArray') -> int:
length = mountainArr.length()
for i in range(length):
if mountainArr.get(i) == target:
return i
return -1interface MountainArray {
int get(int index);
int length();
}
public class Solution {
public int findInMountainArray(int target, MountainArray mountainArr) {
int len = mountainArr.length();
for (int i = 0; i < len; i++) {
if (mountainArr.get(i) == target) {
return i;
}
}
return -1;
}
}#include <iostream>
#include <vector>
using namespace std;
// Mockup of MountainArray, simulating interface.
class MountainArray {
public:
int get(int index) const;
int length() const;
};
int findInMountainArray(int target, const MountainArray &mountainArr) {
int len = mountainArr.length();
for (int i = 0; i < len; ++i) {
if (mountainArr.get(i) == target) {
return i;
}
}
return -1;
}class MountainArray {
get(index) {
// Returns the element of the array at index 'index'.
}
length() {
// Returns the number of elements in the mountain array.
}
}
class Solution {
findInMountainArray(target, mountainArr) {
let len = mountainArr.length();
for (let i = 0; i < len; i++) {
if (mountainArr.get(i) === target) {
return i;
}
}
return -1;
}
}#include <stdio.h>
// Forward declaration of the MountainArray API.
// You don't need to implement this interface, it is provided by the problem constraints.
struct MountainArray {
int (*get)(struct MountainArray*, int index);
int (*length)(struct MountainArray*);
};
int findInMountainArray(int target, struct MountainArray* mountainArr) {
int len = mountainArr->length(mountainArr);
int index = -1;
for (int i = 0; i < len; ++i) {
if (mountainArr->get(mountainArr, i) == target) {
return i;
}
}
return index;
}public interface MountainArray {
int Get(int index);
int Length();
}
public class Solution {
public int FindInMountainArray(int target, MountainArray mountainArr) {
int len = mountainArr.Length();
for (int i = 0; i < len; i++) {
if (mountainArr.Get(i) == target) {
return i;
}
}
return -1;
}
}The Python brute-force method iterates across each element of the array sequentially, which could come at a significant performance cost. It outputs the index at which the target is present via linear inspection. If not found after iterating through all elements, -1 is returned due to inefficiencies in this simple, non-optimized approach.
Time Complexity: O(n) as it analyzes each item of the array individually.
Space Complexity: O(1), operating within constant auxiliary space.
Approach 3: Default Approach
/**
* // This is the MountainArray's API interface.
* // You should not implement it, or speculate about its implementation
* class Master {
* get(index: number): number {}
*
* length(): number {}
* }
*/
function findInMountainArray(target: number, mountainArr: MountainArray) {
const n = mountainArr.length();
let l = 0;
let r = n - 1;
while (l < r) {
const mid = (l + r) >> 1;
if (mountainArr.get(mid) > mountainArr.get(mid + 1)) {
r = mid;
} else {
l = mid + 1;
}
}
const search = (l: number, r: number, k: number): number => {
while (l < r) {
const mid = (l + r) >> 1;
if (k * mountainArr.get(mid) >= k * target) {
r = mid;
} else {
l = mid + 1;
}
}
return mountainArr.get(l) === target ? l : -1;
};
const ans = search(0, l, 1);
return ans === -1 ? search(l + 1, n - 1, -1) : ans;
}/**
* // This is the MountainArray's API interface.
* // You should not implement it, or speculate about its implementation
* type MountainArray struct {
* }
*
* func (this *MountainArray) get(index int) int {}
* func (this *MountainArray) length() int {}
*/
func findInMountainArray(target int, mountainArr *MountainArray) int {
n := mountainArr.length()
l, r := 0, n-1
for l < r {
mid := (l + r) >> 1
if mountainArr.get(mid) > mountainArr.get(mid+1) {
r = mid
} else {
l = mid + 1
}
}
search := func(l, r, k int) int {
for l < r {
mid := (l + r) >> 1
if k*mountainArr.get(mid) >= k*target {
r = mid
} else {
l = mid + 1
}
}
if mountainArr.get(l) == target {
return l
}
return -1
}
ans := search(0, l, 1)
if ans == -1 {
return search(l+1, n-1, -1)
}
return ans
}impl Solution {
#[allow(dead_code)]
pub fn find_in_mountain_array(target: i32, mountain_arr: &MountainArray) -> i32 {
let n = mountain_arr.length();
// First find the maximum element in the array
let mut l = 0;
let mut r = n - 1;
while l < r {
let mid = (l + r) >> 1;
if mountain_arr.get(mid) > mountain_arr.get(mid + 1) {
r = mid;
} else {
l = mid + 1;
}
}
let left = Self::binary_search(mountain_arr, 0, l, 1, target);
if left == -1 {
Self::binary_search(mountain_arr, l, n - 1, -1, target)
} else {
left
}
}
#[allow(dead_code)]
fn binary_search(m: &MountainArray, mut l: i32, mut r: i32, k: i32, target: i32) -> i32 {
let n = m.length();
while l < r {
let mid = (l + r) >> 1;
if k * m.get(mid) >= k * target {
r = mid;
} else {
l = mid + 1;
}
}
if m.get(l) == target {
l
} else {
-1
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search with Peak Finding | Time Complexity: |
| Brute-force Approach | Time Complexity: |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute-force Linear Scan | O(n) | O(1) | Quick baseline solution or when constraints are very small |
| Binary Search with Peak Finding | O(log n) | O(1) | Optimal solution for mountain arrays and interactive API limits |
Frequently asked questions
Is Find in Mountain Array easy or hard?
Find in Mountain Array is classified as a Hard problem on LeetCode. The difficulty comes from combining peak detection, two directional binary searches, and restrictions on the number of API calls.
Find in Mountain Array Python/Java solution
Implement the optimized method by first locating the peak with binary search and then searching both sides. The same algorithm works across Python, Java, C++, C, C#, and JavaScript because it only requires index-based comparisons using the MountainArray API.
How to solve Find in Mountain Array in O(log n)?
First locate the peak using binary search by comparing mid and mid+1 values. After finding the peak index, run a standard binary search on the left increasing section. If the target is not found, run another binary search on the right decreasing section with reversed comparisons.
What is the best approach for Find in Mountain Array?
The best approach uses binary search to first locate the peak of the mountain array and then perform two binary searches on the increasing and decreasing halves. This leverages the array's structure and minimizes API calls. The total time complexity is O(log n) with O(1) space.
Is Find in Mountain Array asked at Google/Amazon/Meta?
Find in Mountain Array appears in interview preparation sets commonly associated with companies like Google and Amazon because it combines binary search with constrained API access. The problem tests understanding of monotonic segments and efficient search strategies.
What data structure is used in Find in Mountain Array?
The core data structure is an array accessed through the MountainArray interface. The algorithm relies on binary search operations over the array indices rather than additional structures, keeping space complexity constant.
What is the time complexity of Find in Mountain Array?
The optimal solution runs in O(log n) time. One binary search identifies the peak element and two additional binary searches check the ascending and descending segments. Each step takes logarithmic time, and space complexity remains O(1).