Find in Mountain Array

HARD

Description

(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:

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() <= 10⁴
0 <= target <= 10⁹
0 <= mountainArr.get(index) <= 10⁹

Approaches

Checkout 2 different approaches to solve Find in Mountain Array. Click on different approaches to view the approach and algorithm in detail.

Linear Scan (Brute Force)

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.

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 Analysis

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

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find in Mountain Array. Click on different languages to view the code.

/** * // 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 Solution

Watch the video walkthrough for Find in Mountain Array

Algorithms:

Binary Search

Data Structures:

Array