Find in Mountain Array

Hard

#1038Time: O(N), where N is the length of the array. In the worst-case scenario, we might have to scan the entire array.Space: O(1), as we only use a constant amount of extra space for loop variables.

Algorithms

Binary Search

Data structures

Array

Prompt

(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] > ... > 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 index k (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:

the array,

Constraints:

3 <= mountainArr.length() <= 10⁴
0 <= target <= 10⁹
0 <= mountainArr.get(index) <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This is a straightforward brute-force approach where we iterate through the array from the beginning to the end. For each index i, we call mountainArr.get(i) and check if its value equals the target. Since we are looking for the minimum index, the first match we find will be our answer.

Algorithm

Get the length of the array, n = mountainArr.length().
Loop for i from 0 to n - 1.
In each iteration, get current_element = mountainArr.get(i).
If current_element == target, we have found the first occurrence. Return the current index i.
If the loop completes without finding the target, return -1.

Walkthrough

The algorithm iterates from index i = 0 to mountainArr.length() - 1. In each iteration, it retrieves the element mountainArr.get(i) and compares this element with the target. If they are equal, it means we have found the target. Since we are iterating from the left, the first occurrence found will be at the minimum index, so we can immediately return i. If the loop completes without finding the target, it means the target is not in the array, and we return -1.

1/**2 * // This is the MountainArray's API interface.3 * // You should not implement it, or speculate about its implementation4 * interface MountainArray {5 *     public int get(int index);6 *     public int length();7 * }8 */9class Solution {10    public int findInMountainArray(int target, MountainArray mountainArr) {11        int n = mountainArr.length();12        for (int i = 0; i < n; i++) {13            if (mountainArr.get(i) == target) {14                return i;15            }16        }17        return -1;18    }19}

Complexity

Time

O(N), where N is the length of the array. In the worst-case scenario, we might have to scan the entire array.

Space

O(1), as we only use a constant amount of extra space for loop variables.

Trade-offs

Pros

Very simple to understand and implement.
Guaranteed to find the minimum index if the target exists.

Cons

Highly inefficient for large arrays.
Exceeds the problem's constraint of 100 calls to MountainArray.get, making it an invalid solution for this specific problem.

This is an efficient approach that fully leverages the special structure of the mountain array. The strategy is to first locate the peak of the mountain and then perform two separate binary searches on the two slopes (the increasing part and the decreasing part). This approach is highly efficient and respects the 100-call limit on mountainArr.get().

Algorithm

Find Peak Index:
- Use binary search on the indices 0 to n-1 to find the peak element's index.
- For a mid index, if mountainArr.get(mid) < mountainArr.get(mid + 1), the peak is to the right, so we search in [mid + 1, right].
- Otherwise, the peak is at or to the left of mid, so we search in [left, mid].
- The loop terminates when left == right, which gives the peakIndex.
Search Left Slope (Increasing Part):
- Perform a standard binary search for the target in the range [0, peakIndex].
- If the target is found, return its index immediately. This is the minimum index.
Search Right Slope (Decreasing Part):
- If the target was not found on the left slope, perform a modified binary search for the target in the range [peakIndex, n - 1].
- The modification accounts for the decreasing order of elements.
- If the target is found, return its index.
Return -1:
- If the target is not found in either search, it doesn't exist in the array. Return -1.

Walkthrough

The problem can be solved efficiently by breaking it down into three main steps:

Find the Peak Index: The array consists of an increasing sequence followed by a decreasing one. The peak is the largest element. We can find its index using a modified binary search in O(log N) time. By comparing mountainArr.get(mid) with mountainArr.get(mid + 1), we can determine if we are on the increasing or decreasing slope and narrow our search space accordingly.
Search in the Increasing Part: With the peakIndex, we know the subarray from 0 to peakIndex is sorted in increasing order. We can run a standard binary search for the target here. If found, we return the index. This will be the minimum index since we search this part first.
Search in the Decreasing Part: If the target isn't in the first part, we search the decreasing slope from peakIndex to n-1. This requires a binary search adapted for a decreasingly sorted array. If the target is found, we return its index.

If both searches fail, the target is not in the array, and we return -1.

1/**2 * // This is the MountainArray's API interface.3 * // You should not implement it, or speculate about its implementation4 * interface MountainArray {5 *     public int get(int index);6 *     public int length();7 * }8 */9class Solution {10    public int findInMountainArray(int target, MountainArray mountainArr) {11        int n = mountainArr.length();12        13        // 1. Find the peak index14        int left = 0, right = n - 1;15        int peakIndex = 0;16        while (left < right) {17            int mid = left + (right - left) / 2;18            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {19                left = mid + 1;20            } else {21                right = mid;22            }23        }24        peakIndex = left;25        26        // 2. Search in the increasing part (left of the peak)27        left = 0;28        right = peakIndex;29        while (left <= right) {30            int mid = left + (right - left) / 2;31            int midVal = mountainArr.get(mid);32            if (midVal == target) {33                return mid;34            } else if (midVal < target) {35                left = mid + 1;36            } else {37                right = mid - 1;38            }39        }40        41        // 3. Search in the decreasing part (right of the peak)42        left = peakIndex;43        right = n - 1;44        while (left <= right) {45            int mid = left + (right - left) / 2;46            int midVal = mountainArr.get(mid);47            if (midVal == target) {48                return mid;49            } else if (midVal < target) {50                right = mid - 1;51            } else {52                left = mid + 1;53            }54        }55        56        return -1;57    }58}

Complexity

Time

O(log N). Finding the peak takes O(log N), and the two subsequent binary searches also take O(log N) each. The total complexity is O(log N).

Space

O(1). We only use a constant amount of extra space for variables like `left`, `right`, `mid`, and `peakIndex`.

Trade-offs

Pros

Extremely efficient, with logarithmic time complexity.
Stays well within the 100 API call limit.
Guaranteed to find the minimum index because it searches the increasing part first.

Cons

More complex to implement compared to a linear scan.
Requires careful implementation of three separate binary search variations (peak finding, increasing search, decreasing search).

Solutions

Solution

1/** * // This is MountainArray's API interface. * // You should not implement it, or speculate about its implementation * interface MountainArray { * public int get(int index) {} * public int length() {} * } */ class Solution { private MountainArray mountainArr ; private int target ; public int findInMountainArray ( int target , MountainArray mountainArr ) { int n = mountainArr . length (); int l = 0 , r = n - 1 ; while ( l < r ) { int mid = ( l + r ) >>> 1 ; if ( mountainArr . get ( mid ) > mountainArr . get ( mid + 1 )) { r = mid ; } else { l = mid + 1 ; } } this . mountainArr = mountainArr ; this . target = target ; int ans = search ( 0 , l , 1 ); return ans == - 1 ? search ( l + 1 , n - 1 , - 1 ) : ans ; } private int search ( int l , int r , int k ) { while ( l < r ) { int mid = ( l + r ) >>> 1 ; if ( k * mountainArr . get ( mid ) >= k * target ) { r = mid ; } else { l = mid + 1 ; } } return mountainArr . get ( l ) == target ? l : - 1 ; } }

1/** * // 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 { public: int findInMountainArray ( int target , MountainArray & mountainArr ) { int n = mountainArr . length (); int l = 0 , r = n - 1 ; while ( l < r ) { int mid = ( l + r ) >> 1 ; if ( mountainArr . get ( mid ) > mountainArr . get ( mid + 1 )) { r = mid ; } else { l = mid + 1 ; } } auto search = [ & ]( int l , int r , int k ) -> int { while ( l < r ) { int mid = ( l + r ) >> 1 ; if ( k * mountainArr . get ( mid ) >= k * target ) { r = mid ; } else { l = mid + 1 ; } } return mountainArr . get ( l ) == target ? l : - 1 ; }; int ans = search ( 0 , l , 1 ); return ans == - 1 ? search ( l + 1 , n - 1 , - 1 ) : ans ; } };

1# """ # 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 ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem