Find in Mountain Array

You are given an interactive problem where you can only access a mountain array through a specific MountainArray interface. The interface provides two methods:

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

A mountain array is defined as an array that:

• Has at least 3 elements (arr.length >= 3).
• Has a single peak element arr[i] such that:
  • arr[0] < arr[1] < ... < arr[i-1] < arr[i]
  • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

Your task is to find the minimum index where mountainArr.get(index) equals the given target. If no such index exists, return -1. You are limited to making at most 100 calls to MountainArray.get. Any 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 indices 2 and 5. The minimum index is 2.

Example 2:

Input: mountainArr = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 3 does not exist in the array.

Constraints:

• 3 <= mountainArr.length() <= 10^4
• 0 <= target <= 10^9
• 0 <= mountainArr.get(index) <= 10^9

How would you solve this problem efficiently, given the constraint on the number of calls to MountainArray.get?

# """
# 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:
        n = mountain_arr.length()
        
        # Find the peak index
        left, right = 0, n - 1
        peak_index = 0
        while left < right:
            mid = (left + right) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                left = mid + 1
            else:
                right = mid
        peak_index = left
        
        # Search in the left side of the mountain
        left, right = 0, peak_index
        while left <= right:
            mid = (left + right) // 2
            mid_val = mountain_arr.get(mid)
            if mid_val == target:
                return mid
            elif mid_val < target:
                left = mid + 1
            else:
                right = mid - 1
        
        # Search in the right side of the mountain
        left, right = peak_index, n - 1
        while left <= right:
            mid = (left + right) // 2
            mid_val = mountain_arr.get(mid)
            if mid_val == target:
                return mid
            elif mid_val < target:
                right = mid - 1
            else:
                left = mid + 1
        
        return -1

Naive Approach

The naive approach would be to iterate through the entire array using mountain_arr.get(i) for each index i from 0 to mountain_arr.length() - 1. If we find the target, we return the index. If we reach the end without finding the target, we return -1. This is simple, but violates the constraint of making at most 100 calls to mountain_arr.get(), especially for larger arrays.

Optimal Approach

The optimal approach leverages binary search. Since the array is a mountain array, we can break the search into three steps:

1. Find the peak index: Use binary search to find the index of the peak element in the mountain array.
2. Search the left side: Use binary search to search for the target in the ascending part of the array (from index 0 to the peak index).
3. Search the right side: Use binary search to search for the target in the descending part of the array (from the peak index to the end of the array).

If the target is found in either the left or right side, return the index. If the target is not found in either side, return -1.

Example

Let's say mountainArr = [1, 2, 3, 4, 5, 3, 1] and target = 3.

1. Find the peak: The peak is 5 at index 4.
2. Search left: Search [1, 2, 3, 4, 5] for 3. It's found at index 2.
3. Return: Return 2.

If target = 0:

1. Find the peak: The peak is 5 at index 4.
2. Search left: Search [1, 2, 3, 4, 5] for 0. It's not found.
3. Search right: Search [5, 3, 1] for 0. It's not found.
4. Return: Return -1.

Big(O) Runtime Analysis

• Finding the peak: Binary search takes O(log n) time, where n is the length of the array.
• Searching the left side: Binary search takes O(log n) time.
• Searching the right side: Binary search takes O(log n) time.

Therefore, the overall runtime complexity is O(log n) + O(log n) + O(log n) = O(log n).

Big(O) Space Usage Analysis

The algorithm uses a constant amount of extra space for variables like left, right, mid, and peak_index. Therefore, the space complexity is O(1).

Edge Cases

• Empty array: The problem states that mountainArr.length() >= 3, so we don't need to handle an empty array.
• Target is the peak: The algorithm correctly handles this because the target will be found during the binary search on the left side (if peak index is included) or right side.
• Target appears multiple times: The algorithm returns the minimum index, which is the first occurrence on the left side. If it's not on the left, it'll be on the right, and the first occurrence there will be returned.
• Target does not exist: The algorithm returns -1, as required.
• Array is strictly increasing or decreasing: Although not a valid mountain array, the code would still produce a result by identifying one end as the peak. This can be handled by validating the mountain array property.