Scale Engineer

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() <= 104
  • 0 <= target <= 109
  • 0 <= mountainArr.get(index) <= 109

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.

/** * // This is the 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 {    public int findInMountainArray(int target, MountainArray mountainArr) {        int n = mountainArr.length();        for (int i = 0; i < n; i++) {            if (mountainArr.get(i) == target) {                return i;            }        }        return -1;    }}

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.

Solutions

/** * // 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 ; } }

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 →

Next problem