Find in Mountain Array Interview Question for Amazon

You are given a mountain array, which is an array that first increases to a peak and then decreases. You are also given a target value. Your task is to find the minimum index of the target value within the mountain array. You cannot directly access the array, but you can use the MountainArray interface, which provides two methods:

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

Your solution must make no more than 100 calls to MountainArray.get(). If the target value appears multiple times, return the smallest index. If the target value does not appear in the array, return -1.

For example:

mountainArr = [1, 2, 3, 4, 5, 3, 1], target = 3. The output should be 2 because 3 appears at indices 2 and 5, and the smaller index is 2.
mountainArr = [0, 1, 2, 4, 2, 1], target = 3. The output should be -1 because 3 does not appear in the array.
mountainArr = [1, 5, 2, 1], target = 5. The output should be 1.

Write a function that efficiently finds the target value in the mountain array.

Find in Mountain Array

Problem Description

Given a mountain array mountainArr, find 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.

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]

Naive Solution

The simplest approach is to iterate through the array and check if each element is equal to the target. If we find the target, we return the index. If we reach the end of the array without finding the target, we return -1.

Code (Python)

def findInMountainArray_naive(target, mountain_arr):
    n = mountain_arr.length()
    for i in range(n):
        if mountain_arr.get(i) == target:
            return i
    return -1

Time Complexity: O(N)

Where N is the length of the mountain array.

Space Complexity: O(1)

We use constant extra space.

Optimal Solution

Since the array is a mountain array, we can use binary search to find the target more efficiently.

The algorithm is as follows:

Find the peak element in the mountain array.
Search for the target in the left part of the mountain array (from index 0 to peak index) using binary search.
If the target is not found in the left part, search for the target in the right part of the mountain array (from peak index + 1 to the end) using binary search.

Code (Python)

class MountainArray:
    def __init__(self, arr):
        self.arr = arr

    def get(self, index):
        return self.arr[index]

    def length(self):
        return len(self.arr)


def findInMountainArray(target, mountain_arr):
    def find_peak_index(arr):
        low = 0
        high = arr.length() - 1
        while low < high:
            mid = (low + high) // 2
            if arr.get(mid) < arr.get(mid + 1):
                low = mid + 1
            else:
                high = mid
        return low

    def binary_search(arr, target, low, high, ascending):
        while low <= high:
            mid = (low + high) // 2
            mid_val = arr.get(mid)
            if mid_val == target:
                return mid
            elif mid_val < target:
                if ascending:
                    low = mid + 1
                else:
                    high = mid - 1
            else:
                if ascending:
                    high = mid - 1
                else:
                    low = mid + 1
        return -1

    peak_index = find_peak_index(mountain_arr)
    left_result = binary_search(mountain_arr, target, 0, peak_index, True)
    if left_result != -1:
        return left_result
    right_result = binary_search(mountain_arr, target, peak_index + 1, mountain_arr.length() - 1, False)
    return right_result

Time Complexity: O(logN)

Where N is the length of the mountain array. We perform binary search three times.

Space Complexity: O(1)

We use constant extra space.

Edge Cases

Empty array: The mountain array must have at least 3 elements.
Target not found: Return -1.
Target found multiple times: Return the minimum index.