Find in Mountain Array

Hard

Asked by:

54 views

Topics:

ArraysBinary Search

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the mountain array guaranteed to have at least 3 elements, and is it guaranteed to have a peak?
If the target value appears multiple times in the array, should I return the index of the first occurrence or any occurrence?
What should I return if the target is not found in the mountain array?
Is the mountain array strictly increasing before the peak and strictly decreasing after the peak, or can plateaus exist?
What are the possible ranges for the target value and the elements within the mountain array?

Brute Force Solution

Approach

Imagine you're searching for a specific number hidden within a special list that goes up and then down like a mountain. The brute force way means you simply check every single number in the list one by one until you find the one you're looking for.

Here's how the algorithm would work step-by-step:

Start at the beginning of the list.
Compare the number you're looking for with the first number on the list.
If they are the same, you've found it! You're done.
If they are different, move to the next number in the list.
Repeat the comparison: is the number you're looking for the same as this number in the list?
Keep going through the list, one number at a time, until you either find a match or you reach the very end of the list.
If you get to the end of the list without finding a match, then the number you were looking for isn't in the list.

Code Implementation

def find_in_mountain_array_brute_force(mountain_array, target):
    array_length = len(mountain_array)

    # Iterate through each element in the mountain array
    for current_index in range(array_length):
        # Check if the current element matches the target
        if mountain_array[current_index] == target:
            return current_index

    # If target is not found after iterating, return -1
    return -1

Big(O) Analysis

Time Complexity

O(n) – The brute force approach iterates through the mountain array at most once. In the worst-case scenario, the target element is at the very end of the array, or not present at all, requiring a complete traversal. This traversal involves visiting each of the 'n' elements in the array once for comparison. Thus, the time complexity is directly proportional to the input size 'n', resulting in O(n).

Space Complexity

O(1) – The provided brute-force algorithm iterates through the input list without using any auxiliary data structures like temporary arrays, hash maps, or sets. It only involves comparing the target value with each element of the list sequentially. Thus, the space required for the algorithm remains constant, irrespective of the input size (N). This constant space usage is primarily for loop counters or index variables.

Optimal Solution

Approach

The key idea is to efficiently search through the mountain by figuring out where the peak is, and then searching on either side. This is much faster than checking every single number in the mountain.

Here's how the algorithm would work step-by-step:

First, find the very top of the mountain. We can do this quickly by repeatedly dividing the mountain in half and checking if we are going up or down.
Once we know the peak, we know that everything to the left is going uphill, and everything to the right is going downhill.
Now, search the uphill side for the number we are looking for. Again, we can use a divide-and-conquer strategy by checking the middle.
If the number is not on the uphill side, repeat the search process on the downhill side of the mountain, using a similar divide-and-conquer approach.
The end result is we either find the number in one of the two sections, or determine it is not in the mountain at all.

Code Implementation

def find_in_mountain_array(target, mountain_array):
    array_length = len(mountain_array)

    def find_peak_index(mountain_array):
        start_index = 0
        end_index = array_length - 1

        while start_index < end_index:
            middle_index = (start_index + end_index) // 2

            # Move to the right side of the mountain if ascending.
            if mountain_array[middle_index] < mountain_array[middle_index + 1]:
                start_index = middle_index + 1
            else:
                # Move to the left side of the mountain if descending.
                end_index = middle_index

        return start_index

    def binary_search_ascending(mountain_array, target, start_index, end_index):
        while start_index <= end_index:
            middle_index = (start_index + end_index) // 2
            middle_value = mountain_array[middle_index]

            if middle_value == target:
                return middle_index
            elif middle_value < target:
                start_index = middle_index + 1
            else:
                end_index = middle_index - 1

        return -1

    def binary_search_descending(mountain_array, target, start_index, end_index):
        while start_index <= end_index:
            middle_index = (start_index + end_index) // 2
            middle_value = mountain_array[middle_index]

            if middle_value == target:
                return middle_index
            elif middle_value > target:
                end_index = middle_index - 1
            else:
                start_index = middle_index + 1

        return -1

    peak_index = find_peak_index(mountain_array)

    # First search the ascending part of the mountain array.
    ascending_result = binary_search_ascending(mountain_array, target, 0, peak_index)
    if ascending_result != -1:
        return ascending_result

    # If not found, search the descending part of the mountain array.
    descending_result = binary_search_descending(mountain_array, target, peak_index + 1, array_length - 1)

    return descending_result

Big(O) Analysis

Time Complexity

O(log n) – The algorithm consists of three main steps: finding the peak, searching the left side (ascending), and searching the right side (descending). Each of these steps uses binary search. Binary search on an array of size n has a time complexity of O(log n). Since we perform binary search at most three times, the overall time complexity is O(log n) + O(log n) + O(log n), which simplifies to O(log n).

Space Complexity

O(log N) – The algorithm uses binary search, which is implemented recursively or iteratively. When implemented recursively, the space complexity depends on the maximum depth of the recursion, which corresponds to the number of times the mountain is divided in half. In the worst case, this depth is log2(N), where N represents the size of the mountain array. Each recursive call adds a frame to the call stack, consuming a constant amount of memory, so the auxiliary space is proportional to log N. Therefore, the space complexity is O(log N).

Edge Cases

Case	How to Handle
Null or empty mountain array	Return -1 immediately as there is nothing to search.
Mountain array with only one or two elements	Check if the array adheres to the mountain property (at least 3 elements) and return -1 if it does not; otherwise, handle edge cases where target may be present.
Target is smaller than all elements in the mountain array	The binary search will exhaust the search space, and the algorithm should return -1 in this case.
Target is larger than the peak element	The binary search on both increasing and decreasing sides will exhaust without finding the target, so the algorithm should return -1.
Target is present multiple times in the increasing or decreasing part of the mountain	Binary search may find any one of the occurrences and should be acceptable as the problem doesn't require a specific index.
Integer overflow when calculating the middle index in binary search	Use mid = low + (high - low) / 2 to prevent integer overflow.
Peak is at the very beginning or the very end of the array	Handle this edge case during peak finding binary search to avoid index out of bounds exceptions.
The target exists only at the peak of the mountain	The peak finding needs to be performed before searching the increasing and decreasing portions, and checking if target is equal to peak value, returning peak's index in that case.

Null or empty mountain array

How to Handle:

Return -1 immediately as there is nothing to search.

Mountain array with only one or two elements

How to Handle:

Check if the array adheres to the mountain property (at least 3 elements) and return -1 if it does not; otherwise, handle edge cases where target may be present.

Target is smaller than all elements in the mountain array

How to Handle:

The binary search will exhaust the search space, and the algorithm should return -1 in this case.

Target is larger than the peak element

How to Handle:

The binary search on both increasing and decreasing sides will exhaust without finding the target, so the algorithm should return -1.

Target is present multiple times in the increasing or decreasing part of the mountain

How to Handle:

Binary search may find any one of the occurrences and should be acceptable as the problem doesn't require a specific index.

Integer overflow when calculating the middle index in binary search

How to Handle:

Use mid = low + (high - low) / 2 to prevent integer overflow.

Peak is at the very beginning or the very end of the array

How to Handle:

Handle this edge case during peak finding binary search to avoid index out of bounds exceptions.

The target exists only at the peak of the mountain

How to Handle:

The peak finding needs to be performed before searching the increasing and decreasing portions, and checking if target is equal to peak value, returning peak's index in that case.