1095. Find in Mountain Array

Problem Description

This is an interactive problem where you need to find a target value in a mountain array with limited access.

A mountain array is defined as an array that:

Has at least 3 elements
Has a peak element at some index i (where 0 < i < arr.length - 1)
Strictly increases from the start to the peak: arr[0] < arr[1] < ... < arr[i]
Strictly decreases from the peak to the end: arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

You're given a MountainArray object and a target value. Your task is to find and return the minimum index where mountainArr.get(index) == target. If the target doesn't exist in the array, return -1.

The catch is that you cannot directly access the array. You can only use two methods:

MountainArray.get(k): Returns the element at index k (0-indexed)
MountainArray.length(): Returns the length of the array

There's a constraint: your solution must make no more than 100 calls to MountainArray.get(), otherwise it will be judged as Wrong Answer.

The solution uses a two-phase approach:

Find the peak: Uses binary search to locate the peak of the mountain array by comparing adjacent elements. If get(mid) > get(mid + 1), the peak is at or before mid; otherwise, it's after mid.
Search for target: Once the peak is found, the array is divided into two parts:
- The ascending part (from start to peak): Regular binary search
- The descending part (from peak+1 to end): Binary search with reversed comparison logic

The clever use of the parameter k (1 or -1) in the search function allows the same binary search logic to work for both ascending and descending portions by multiplying the comparison values by k.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is recognizing that a mountain array has special properties we can exploit. Since we have a strict limit on the number of calls (100), we need an efficient approach - this immediately suggests binary search, which runs in O(log n) time.

The mountain array essentially consists of two sorted sequences joined at a peak: one ascending and one descending. If we can find the peak, we can treat each side as a sorted array and apply binary search.

Why find the peak first? Without knowing where the peak is, we can't determine which "side" of the mountain we're on when we find an element. The comparison logic differs between the ascending side (where larger indices mean larger values) and the descending side (where larger indices mean smaller values).

To find the peak efficiently, we observe that at any point in the array:

If arr[mid] > arr[mid + 1], we're on the descending side or at the peak itself, so the peak must be at position mid or earlier
If arr[mid] < arr[mid + 1], we're on the ascending side, so the peak must be after position mid

This allows us to binary search for the peak in O(log n) calls.

Once we have the peak, searching for the target becomes straightforward - we perform binary search on the ascending portion first (since we want the minimum index). If not found there, we search the descending portion.

The elegant trick in the code is using a multiplier k (1 for ascending, -1 for descending) to unify the binary search logic. By multiplying both the current element and target by k, we convert the descending search into an ascending one: in the descending portion, smaller values are actually "greater" in terms of their position from the peak, so multiplying by -1 reverses the comparison appropriately.

This approach ensures we use at most 3 * log n calls to get(): one binary search to find the peak, and potentially two more to search both sides, well within the 100-call limit.

Learn more about Binary Search patterns.

Solution Implementation

1# """ 2# This is MountainArray's API interface. 3# You should not implement it, or speculate about its implementation 4# """ 5# class MountainArray: 6# def get(self, index: int) -> int: 7# def length(self) -> int: 8 9 10class Solution: 11 def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int: 12 def search_ascending(left: int, right: int) -> int: 13 """ 14 Binary search in ascending portion using template. 15 Feasible: mountain_arr.get(mid) >= target 16 """ 17 first_true_index = -1 18 while left <= right: 19 mid = (left + right) // 2 20 if mountain_arr.get(mid) >= target: 21 first_true_index = mid 22 right = mid - 1 23 else: 24 left = mid + 1 25 # Check if found value equals target 26 if first_true_index != -1 and mountain_arr.get(first_true_index) == target: 27 return first_true_index 28 return -1 29 30 def search_descending(left: int, right: int) -> int: 31 """ 32 Binary search in descending portion using template. 33 Feasible: mountain_arr.get(mid) <= target (values decrease, so <= is the boundary) 34 """ 35 first_true_index = -1 36 while left <= right: 37 mid = (left + right) // 2 38 if mountain_arr.get(mid) <= target: 39 first_true_index = mid 40 right = mid - 1 41 else: 42 left = mid + 1 43 # Check if found value equals target 44 if first_true_index != -1 and mountain_arr.get(first_true_index) == target: 45 return first_true_index 46 return -1 47 48 # Get the length of the mountain array 49 array_length = mountain_arr.length() 50 51 # Step 1: Find the peak element using binary search template 52 # Feasible: mountain_arr.get(mid) > mountain_arr.get(mid + 1) (on descending side) 53 left, right = 0, array_length - 1 54 first_true_index = -1 55 while left <= right: 56 mid = (left + right) // 2 57 if mid < array_length - 1 and mountain_arr.get(mid) > mountain_arr.get(mid + 1): 58 first_true_index = mid 59 right = mid - 1 60 else: 61 left = mid + 1 62 peak_index = first_true_index 63 64 # Step 2: Search in ascending part (from start to peak) 65 result = search_ascending(0, peak_index) 66 67 # Step 3: If not found, search in descending part (from peak+1 to end) 68 if result == -1: 69 result = search_descending(peak_index + 1, array_length - 1) 70 71 return result 72

1/** 2 * // This is MountainArray's API interface. 3 * // You should not implement it, or speculate about its implementation 4 * interface MountainArray { 5 * public int get(int index) {} 6 * public int length() {} 7 * } 8 */ 9 10class Solution { 11 private MountainArray mountainArray; 12 private int targetValue; 13 14 /** 15 * Finds the minimum index of target in a mountain array. 16 * A mountain array is an array that increases to a peak and then decreases. 17 * 18 * @param target The value to search for 19 * @param mountainArr The mountain array to search in 20 * @return The minimum index where target is found, or -1 if not found 21 */ 22 public int findInMountainArray(int target, MountainArray mountainArr) { 23 int arrayLength = mountainArr.length(); 24 this.mountainArray = mountainArr; 25 this.targetValue = target; 26 27 // Step 1: Find peak using template 28 // Feasible: get(mid) > get(mid + 1) (on descending side) 29 int left = 0; 30 int right = arrayLength - 1; 31 int firstTrueIndex = -1; 32 33 while (left <= right) { 34 int mid = left + (right - left) / 2; 35 if (mid < arrayLength - 1 && mountainArr.get(mid) > mountainArr.get(mid + 1)) { 36 firstTrueIndex = mid; 37 right = mid - 1; 38 } else { 39 left = mid + 1; 40 } 41 } 42 int peakIndex = firstTrueIndex; 43 44 // Step 2: Search ascending part 45 int result = searchAscending(0, peakIndex); 46 47 // Step 3: If not found, search descending part 48 if (result == -1) { 49 result = searchDescending(peakIndex + 1, arrayLength - 1); 50 } 51 52 return result; 53 } 54 55 /** 56 * Binary search in ascending portion using template. 57 * Feasible: get(mid) >= target 58 */ 59 private int searchAscending(int left, int right) { 60 int firstTrueIndex = -1; 61 while (left <= right) { 62 int mid = left + (right - left) / 2; 63 if (mountainArray.get(mid) >= targetValue) { 64 firstTrueIndex = mid; 65 right = mid - 1; 66 } else { 67 left = mid + 1; 68 } 69 } 70 if (firstTrueIndex != -1 && mountainArray.get(firstTrueIndex) == targetValue) { 71 return firstTrueIndex; 72 } 73 return -1; 74 } 75 76 /** 77 * Binary search in descending portion using template. 78 * Feasible: get(mid) <= target 79 */ 80 private int searchDescending(int left, int right) { 81 int firstTrueIndex = -1; 82 while (left <= right) { 83 int mid = left + (right - left) / 2; 84 if (mountainArray.get(mid) <= targetValue) { 85 firstTrueIndex = mid; 86 right = mid - 1; 87 } else { 88 left = mid + 1; 89 } 90 } 91 if (firstTrueIndex != -1 && mountainArray.get(firstTrueIndex) == targetValue) { 92 return firstTrueIndex; 93 } 94 return -1; 95 } 96} 97

1/** 2 * // This is the MountainArray's API interface. 3 * // You should not implement it, or speculate about its implementation 4 * class MountainArray { 5 * public: 6 * int get(int index); 7 * int length(); 8 * }; 9 */ 10 11class Solution { 12public: 13 int findInMountainArray(int target, MountainArray& mountainArr) { 14 int arrayLength = mountainArr.length(); 15 16 // Step 1: Find peak using template 17 // Feasible: get(mid) > get(mid + 1) 18 int left = 0, right = arrayLength - 1; 19 int firstTrueIndex = -1; 20 while (left <= right) { 21 int mid = left + (right - left) / 2; 22 if (mid < arrayLength - 1 && mountainArr.get(mid) > mountainArr.get(mid + 1)) { 23 firstTrueIndex = mid; 24 right = mid - 1; 25 } else { 26 left = mid + 1; 27 } 28 } 29 int peakIndex = firstTrueIndex; 30 31 // Lambda for ascending search: Feasible: get(mid) >= target 32 auto searchAscending = [&](int searchLeft, int searchRight) -> int { 33 int firstTrue = -1; 34 while (searchLeft <= searchRight) { 35 int mid = searchLeft + (searchRight - searchLeft) / 2; 36 if (mountainArr.get(mid) >= target) { 37 firstTrue = mid; 38 searchRight = mid - 1; 39 } else { 40 searchLeft = mid + 1; 41 } 42 } 43 if (firstTrue != -1 && mountainArr.get(firstTrue) == target) { 44 return firstTrue; 45 } 46 return -1; 47 }; 48 49 // Lambda for descending search: Feasible: get(mid) <= target 50 auto searchDescending = [&](int searchLeft, int searchRight) -> int { 51 int firstTrue = -1; 52 while (searchLeft <= searchRight) { 53 int mid = searchLeft + (searchRight - searchLeft) / 2; 54 if (mountainArr.get(mid) <= target) { 55 firstTrue = mid; 56 searchRight = mid - 1; 57 } else { 58 searchLeft = mid + 1; 59 } 60 } 61 if (firstTrue != -1 && mountainArr.get(firstTrue) == target) { 62 return firstTrue; 63 } 64 return -1; 65 }; 66 67 // Step 2: Search ascending part 68 int result = searchAscending(0, peakIndex); 69 70 // Step 3: If not found, search descending part 71 if (result == -1) { 72 result = searchDescending(peakIndex + 1, arrayLength - 1); 73 } 74 75 return result; 76 } 77}; 78

1/** 2 * // This is the MountainArray's API interface. 3 * // You should not implement it, or speculate about its implementation 4 * class MountainArray { 5 * get(index: number): number {} 6 * 7 * length(): number {} 8 * } 9 */ 10 11/** 12 * Finds the minimum index of target in a mountain array 13 * A mountain array increases to a peak and then decreases 14 * @param target - The value to search for 15 * @param mountainArr - The mountain array to search in 16 * @returns The minimum index where target is found, or -1 if not found 17 */ 18function findInMountainArray(target: number, mountainArr: MountainArray): number { 19 const arrayLength = mountainArr.length(); 20 21 // Step 1: Find peak using template 22 // Feasible: get(mid) > get(mid + 1) 23 let left = 0; 24 let right = arrayLength - 1; 25 let firstTrueIndex = -1; 26 27 while (left <= right) { 28 const mid = Math.floor((left + right) / 2); 29 if (mid < arrayLength - 1 && mountainArr.get(mid) > mountainArr.get(mid + 1)) { 30 firstTrueIndex = mid; 31 right = mid - 1; 32 } else { 33 left = mid + 1; 34 } 35 } 36 const peakIndex = firstTrueIndex; 37 38 /** 39 * Binary search in ascending portion: Feasible: get(mid) >= target 40 */ 41 const searchAscending = (searchLeft: number, searchRight: number): number => { 42 let firstTrue = -1; 43 while (searchLeft <= searchRight) { 44 const mid = Math.floor((searchLeft + searchRight) / 2); 45 if (mountainArr.get(mid) >= target) { 46 firstTrue = mid; 47 searchRight = mid - 1; 48 } else { 49 searchLeft = mid + 1; 50 } 51 } 52 if (firstTrue !== -1 && mountainArr.get(firstTrue) === target) { 53 return firstTrue; 54 } 55 return -1; 56 }; 57 58 /** 59 * Binary search in descending portion: Feasible: get(mid) <= target 60 */ 61 const searchDescending = (searchLeft: number, searchRight: number): number => { 62 let firstTrue = -1; 63 while (searchLeft <= searchRight) { 64 const mid = Math.floor((searchLeft + searchRight) / 2); 65 if (mountainArr.get(mid) <= target) { 66 firstTrue = mid; 67 searchRight = mid - 1; 68 } else { 69 searchLeft = mid + 1; 70 } 71 } 72 if (firstTrue !== -1 && mountainArr.get(firstTrue) === target) { 73 return firstTrue; 74 } 75 return -1; 76 }; 77 78 // Step 2: Search ascending part 79 const result = searchAscending(0, peakIndex); 80 81 // Step 3: If not found, search descending part 82 return result !== -1 ? result : searchDescending(peakIndex + 1, arrayLength - 1); 83} 84

Solution Approach

The implementation uses the binary search template three times: once to find the peak, once to search the ascending portion, and once to search the descending portion.

Step 1: Find the Peak Using Template

Feasible condition: get(mid) > get(mid + 1) - Are we on the descending side or at the peak?

first_true_index = -1 while left <= right:  mid = (left + right) // 2  if mid < n - 1 and mountain_arr.get(mid) > mountain_arr.get(mid + 1):  first_true_index = mid  right = mid - 1  else:  left = mid + 1 peak_index = first_true_index

Step 2: Search Ascending Portion Using Template

Feasible condition: get(mid) >= target

Pattern: [false, false, ..., true, true, true] (values increase left to right)

first_true_index = -1 while left <= right:  mid = (left + right) // 2  if mountain_arr.get(mid) >= target:  first_true_index = mid  right = mid - 1  else:  left = mid + 1 # Verify found value equals target if first_true_index != -1 and mountain_arr.get(first_true_index) == target:  return first_true_index

Step 3: Search Descending Portion Using Template

Feasible condition: get(mid) <= target

Pattern: [false, false, ..., true, true, true] (values decrease left to right, so smaller values are on the right)

first_true_index = -1 while left <= right:  mid = (left + right) // 2  if mountain_arr.get(mid) <= target:  first_true_index = mid  right = mid - 1  else:  left = mid + 1 # Verify found value equals target

Why Different Feasible Conditions?

Ascending: Values increase, so first position where value >= target gives us the target (or proves it doesn't exist)
Descending: Values decrease, so first position where value <= target gives us the target (or proves it doesn't exist)

Time Complexity: O(log n) - Three binary searches, each taking O(log n) time.

Space Complexity: O(1) - Only using constant extra space.

API Calls: Maximum 3 * log n calls to mountain_arr.get(), well within the 100-call limit.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with a concrete example:

Mountain Array: [1, 3, 5, 7, 6, 4, 2] Target: 4 Expected Output: 5 (index where 4 is located)

Step 1: Find the Peak

We start with l = 0, r = 6 (array length - 1).

Iteration 1:

mid = (0 + 6) >> 1 = 3
Compare get(3) = 7 with get(4) = 6
Since 7 > 6, we're on the descending side or at peak
Update r = 3

Iteration 2:

l = 0, r = 3
mid = (0 + 3) >> 1 = 1
Compare get(1) = 3 with get(2) = 5
Since 3 < 5, we're on the ascending side
Update l = 2

Iteration 3:

l = 2, r = 3
mid = (2 + 3) >> 1 = 2
Compare get(2) = 5 with get(3) = 7
Since 5 < 7, we're on the ascending side
Update l = 3

Now l = r = 3, so the peak is at index 3 with value 7.

Step 2: Search for Target = 4

Search ascending portion [0, 3] with k = 1:

l = 0, r = 3
mid = 1: 1 * get(1) = 3 vs 1 * 4 = 4
- Since 3 < 4, update l = 2
l = 2, r = 3
mid = 2: 1 * get(2) = 5 vs 1 * 4 = 4
- Since 5 >= 4, update r = 2
Now l = r = 2, check get(2) = 5 ≠ 4
Return -1 (not found in ascending portion)

Search descending portion [4, 6] with k = -1:

l = 4, r = 6
mid = 5: -1 * get(5) = -4 vs -1 * 4 = -4
- Since -4 >= -4, update r = 5
Now l = 4, r = 5
mid = 4: -1 * get(4) = -6 vs -1 * 4 = -4
- Since -6 < -4, update l = 5
Now l = r = 5, check get(5) = 4 = 4 ✓
Return 5

Final Answer: 5

The solution efficiently found the target using only 10 calls to get(): 3 to find the peak, 3 for the ascending search, and 4 for the descending search.

Time and Space Complexity

Time Complexity: O(log n)

The algorithm consists of three binary search operations:

First binary search to find the peak element: O(log n) where each iteration makes 2 calls to mountain_arr.get()
Second binary search on the ascending part (left side): O(log n) where each iteration makes 1 call to mountain_arr.get()
Third binary search on the descending part (right side) - only executed if target not found in ascending part: O(log n) where each iteration makes 1 call to mountain_arr.get()

Since these searches are performed sequentially (not nested), the total time complexity is O(log n) + O(log n) + O(log n) = O(log n).

The total number of API calls to mountain_arr.get() is at most O(log n) calls.

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

A few integer variables (l, r, mid, n, ans)
The search helper function which doesn't use recursion
The parameter k in the search function

No additional data structures are created that scale with input size, making the space complexity constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using the Wrong Binary Search Template

A common mistake is using while left < right with right = mid instead of the standard template:

# Alternative template (not recommended) while left < right:  mid = (left + right) // 2  if mountain_arr.get(mid) > mountain_arr.get(mid + 1):  right = mid  else:  left = mid + 1

Solution: Use the standard template with while left <= right and first_true_index:

first_true_index = -1 while left <= right:  mid = (left + right) // 2  if mid < n - 1 and mountain_arr.get(mid) > mountain_arr.get(mid + 1):  first_true_index = mid  right = mid - 1  else:  left = mid + 1

2. Incorrect Feasible Condition for Descending Search

Using >= target for descending arrays (which have values in decreasing order):

# WRONG for descending arrays if mountain_arr.get(mid) >= target:  first_true_index = mid  right = mid - 1

Why it's wrong: In a descending array, values decrease from left to right. The boundary where values become <= target is what we're looking for.

Solution: Use <= target for descending arrays:

# CORRECT for descending arrays if mountain_arr.get(mid) <= target:  first_true_index = mid  right = mid - 1

3. Incorrect Binary Search Boundaries for Descending Portion

Including the peak in both ascending and descending searches:

# WRONG - Including peak twice result = search_ascending(0, peak_index) if result == -1:  result = search_descending(peak_index, array_length - 1) # Should be peak_index + 1

Solution: Start descending search from peak_index + 1:

result = search_ascending(0, peak_index) if result == -1:  result = search_descending(peak_index + 1, array_length - 1)

4. Not Validating Found Value Equals Target

Returning first_true_index without checking if the value actually equals target:

# WRONG return first_true_index

Why it's wrong: The feasible condition (>= target or <= target) doesn't guarantee equality. The value at first_true_index might be greater or less than target.

Solution: Always verify:

if first_true_index != -1 and mountain_arr.get(first_true_index) == target:  return first_true_index return -1

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

How many ways can you arrange the three letters A, B and C?

I don't know