Taro Logo

Minimum Number of Removals to Make Mountain Array

Hard
Google logo
Google
2 views
Topics:
ArraysDynamic Programming

You may recall that an array arr is a mountain array if and only if:

  • arr.length >= 3
  • There exists some index i (0-indexed) 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 an integer array nums, return the minimum number of elements to remove to make nums a mountain array.

For example:

  1. nums = [1,3,1] Output: 0 Explanation: The array itself is a mountain array so we do not need to remove any elements.
  2. nums = [2,1,1,5,6,2,3,1] Output: 3 Explanation: One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].

What is the most efficient solution, and what are the time and space complexities?

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:

  1. What are the constraints on the size and the values within the input array `nums`? Can I expect negative numbers, zeros, or only positive integers?
  2. If the input array is already a mountain array, should I return 0?
  3. If it's impossible to form a mountain array from the input, what value should I return?
  4. Can the mountain array have a peak at the very beginning or the very end of the array (i.e., a strictly decreasing or strictly increasing array)?
  5. Are duplicate values allowed in the input array, and if so, how should they be handled when forming the strictly increasing and strictly decreasing subsequences?

Brute Force Solution

Approach

The brute force method for finding the fewest removals to make a mountain involves trying all possible combinations of keeping some numbers and removing others. We check each of these combinations to see if it forms a valid mountain, and then keep track of the smallest number of removals required.

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

  1. Consider every possible selection of numbers from the original list.
  2. For each selected list of numbers, check if it forms a valid mountain. A valid mountain goes up, reaches a peak, and then goes down.
  3. If a selected list is a valid mountain, calculate how many numbers were removed from the original list to obtain it.
  4. Keep track of the minimum number of removals needed to form a mountain across all the selections.
  5. The lowest number of removals found across all valid mountain selections is the answer.

Code Implementation

def minimum_mountain_removals_brute_force(numbers):
    list_length = len(numbers)
    minimum_removals = list_length

    for i in range(1 << list_length):
        selected_numbers = []

        for j in range(list_length):
            if (i >> j) & 1:
                selected_numbers.append(numbers[j])

        selected_length = len(selected_numbers)

        if selected_length >= 3:
            # Check if it forms a mountain
            peak_found = False
            peak_index = -1
            for k in range(1, selected_length - 1):
                if selected_numbers[k] > selected_numbers[k - 1] and \
                   selected_numbers[k] > selected_numbers[k + 1]:
                    peak_found = True
                    peak_index = k
                    break

            if peak_found:
                is_mountain = True

                # Verify increasing sequence before peak
                for k in range(1, peak_index + 1):
                    if selected_numbers[k] <= selected_numbers[k - 1]:
                        is_mountain = False
                        break

                # Verify decreasing sequence after peak
                if is_mountain:
                    for k in range(peak_index + 1, selected_length):
                        if selected_numbers[k] >= selected_numbers[k - 1]:
                            is_mountain = False
                            break

                if is_mountain:
                    #Calculate the number of removals
                    removals = list_length - selected_length
                    minimum_removals = min(minimum_removals, removals)

    return minimum_removals

Big(O) Analysis

Time Complexity
O(2^n * n)The brute force approach considers all possible subsets of the input array. For an array of size n, there are 2^n possible subsets. For each subset, we need to check if it forms a valid mountain array, which takes O(n) time in the worst case, because we must iterate the subset to determine that it is a mountain array. Therefore, the overall time complexity is O(2^n * n).
Space Complexity
O(N)The brute force approach implicitly explores all possible subsets of the input array of size N. Although not explicitly mentioned as storing all subsets, checking all combinations requires storing a list of selected numbers in each recursive call to check if it forms a valid mountain. The size of this list in the worst case, where we keep almost all elements, can be close to N. Therefore, the maximum depth of the implicit recursion and the storage for each selected list contribute O(N) space in the worst case, where N is the length of the input array.

Optimal Solution

Approach

To find the fewest removals to form a mountain, we'll find the longest mountain-shaped sequence that already exists within the given sequence. Then, we'll remove everything else. The trick is to efficiently find this longest mountain.

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

  1. For each position in the sequence, imagine it's the peak of a potential mountain.
  2. Look to the left of this potential peak and find the longest increasing sequence ending at that peak.
  3. Look to the right of the potential peak and find the longest decreasing sequence starting at that peak.
  4. Add the lengths of the increasing and decreasing sequences (minus 1, since the peak is counted twice) to find the length of the mountain centered at that peak.
  5. Repeat this for every position in the sequence, always recording the longest mountain you've found so far.
  6. Once you've considered every possible peak, take the length of the original sequence and subtract the length of the longest mountain you found. This difference is the minimum number of removals needed.

Code Implementation

def minimum_number_of_removals_to_make_mountain_array(number_array):
    array_length = len(number_array)
    longest_increasing_sequence = [1] * array_length
    longest_decreasing_sequence = [1] * array_length

    for i in range(1, array_length):
        for j in range(i):
            if number_array[i] > number_array[j]:
                longest_increasing_sequence[i] = max(longest_increasing_sequence[i], longest_increasing_sequence[j] + 1)

    # Calculate decreasing sequences from right to left.
    for i in range(array_length - 2, -1, -1):
        for j in range(array_length - 1, i, -1):
            if number_array[i] > number_array[j]:
                longest_decreasing_sequence[i] = max(longest_decreasing_sequence[i], longest_decreasing_sequence[j] + 1)

    maximum_mountain_length = 0

    # Find the longest mountain.
    for i in range(array_length):
        if longest_increasing_sequence[i] > 1 and longest_decreasing_sequence[i] > 1:
            maximum_mountain_length = max(maximum_mountain_length, longest_increasing_sequence[i] + longest_decreasing_sequence[i] - 1)

    # The result is the difference between the array length and mountain length.
    return array_length - maximum_mountain_length

Big(O) Analysis

Time Complexity
O(n²)The algorithm iterates through each element of the input array of size n, considering each as a potential peak of a mountain. For each potential peak, it calculates the longest increasing subsequence to the left and the longest decreasing subsequence to the right. Calculating these subsequences involves iterating through portions of the array again, leading to nested loops. In the worst case, calculating the increasing and decreasing subsequences for each peak takes O(n) time. Since this subsequence calculation is performed for each of the n elements, the overall time complexity is O(n*n), which simplifies to O(n²).
Space Complexity
O(N)The algorithm uses two arrays, `increasing` and `decreasing`, to store the lengths of the longest increasing and decreasing subsequences for each position in the input array. Both of these arrays have a size equal to the length of the input array, which we denote as N. Therefore, the auxiliary space required is proportional to the input size N, resulting in a space complexity of O(N).

Edge Cases

CaseHow to Handle
Empty or null input arrayReturn 0 since an empty array is trivially a mountain (or can be considered such after 0 removals).
Array with size 1 or 2Return the size of the array, as a mountain array needs at least one increasing and one decreasing element to be valid.
Array with all identical elementsReturn array.length - 1 because you need to remove all but one element to make it technically a mountain, assuming a single element is considered a valid trivial mountain.
Array already a valid mountain arrayReturn 0, because no removals are needed.
Array sorted in strictly increasing orderReturn array.length - 1, keep the last element as the 'peak'.
Array sorted in strictly decreasing orderReturn array.length - 1, keep the first element as the 'peak'.
Array with a very large number of elementsThe longest increasing subsequence algorithm must be efficient (O(n log n)) to avoid time limit exceeding errors; dynamic programming alone may be too slow.
Integer overflow when calculating LIS lengths for very large input arraysThe LIS calculations themselves won't overflow given problem constraints, but be mindful of memory usage as LIS arrays may be large.