1671. Minimum Number of Removals to Make Mountain Array


Problem Description

The problem provides an array of integers named nums and defines a mountain array as an array that increases in value to a certain point (the peak) and then strictly decreases in value thereafter. A mountain array must have at least one element before and after the peak, meaning at minimum the array size should be 3. The goal is to find the minimum number of elements that must be removed from nums so that the remaining array is a mountain array. Thus, the task is to transform nums into a mountain array using the fewest possible deletions.

Intuition

To solve this problem, the intuition is to find the longest increasing subsequence (LIS) from the left to a peak and from the peak to the right for each element in the array, considering that element as the peak. Since we need at least one element before and after the peak for the array to be a mountain array, we exclude peaks at the boundaries (first and last element).

The key insight is that the number of elements we need to delete from the array to form a mountain array is equal to the total number of elements minus the length of the longest subsequence that forms a mountain array. This longest subsequence will be the combination of the longest strictly increasing subsequence that reaches up to the peak (but not including the peak) and the longest strictly decreasing subsequence that starts just after the peak.

For each possible peak in the array, we determine the length of the LIS up to (but not including) that peak and the length of the longest decreasing subsequence (LDS) starting just after that peak and ending at the last element. Adding the lengths of these two subsequences together and subtracting one (to account for the peak being counted twice) gives us the length of the longest mountain subsequence that has that specific element as the peak. By iterating over all the elements (treating each as the peak) and applying this logic, and then maximizing the resultant lengths, we find the length of the desired longest mountain subsequence within the array. Subtracting this length from the total number of elements in the original array gives the minimum number of elements that need to be removed to form a valid mountain array.

Learn more about Greedy, Binary Search and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Solution Approach

The solution leverages dynamic programming to find the Longest Increasing Subsequence (LIS) from the left and the longest decreasing subsequence from the right for each element.

To achieve this, two arrays left and right of the same size as the input nums are created. Initially, all elements in left and right are set to 1, meaning at the very least, every element can be considered a subsequence of length 1.

  1. LIS from the left: We iterate through each element i from index 1 to n-1, where n is the size of nums. For each i, we also iterate through each previous element j from 0 to i-1. If nums[i] > nums[j], it means the sequence can be extended, and we update left[i] to be the maximum of its current value and left[j] + 1.

  2. Longest decreasing subsequence from the right: We mirror what we did for the LIS from the left, but in reverse. Starting from n-2 down to 0, iterate the current element i and for each i, iterate over every following element j from i+1 to n-1. If nums[i] > nums[j], it indicates that we can extend a decreasing subsequence and we update right[i] with the max of its current value and right[j] + 1.

  3. Once we have both left and right, we iterate through them together using zip(left, right) to calculate the length of the longest mountain subsequence that each element can form, as the peak, where we add the values of left and right together and subtract 1 (to not double-count the peak). We are only interested in the peaks that are not at the boundaries, hence we check if both left[i] > 1 and right[i] > 1.

  4. The length of the largest subsequence forming a mountain is the maximum value of the sequence length found in step 3. Since we want to find the minimum number of removals, we subtract this value from the total length of the input array, n.

By utilizing dynamic programming, this solution builds up subproblems (LIS to the left and right of every element) that help to solve the overall problem (minimum removals to form a mountain array). This avoids the inefficiency of checking every possible subsequence directly, which would be computationally expensive.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the minimum element can be found in:

Example Walkthrough

Let's consider the array nums equal to [2, 1, 1, 5, 6, 2, 3, 1]. The goal is to remove the minimum number of elements to turn nums into a mountain array. Following the solution approach:

  1. Determine LIS from the left: Starting from the second element, compare it with all the previous elements to calculate how long the increasing subsequence can be up to that point.
  • Initialize left array with [1, 1, 1, 1, 1, 1, 1, 1].
  • Traverse the elements from left to right:
    • The subsequence [2] cannot be extended by 1, so left stays the same.
    • The subsequence [1, 1] doesn't extend, so left remains the same.
    • 5 extends [2] and [1], making left[3] = 2 because it forms an increasing subsequence of length 2 starting from either 2 or 1.
    • 6 extends the subsequence ending with 5, so left[4] = 3 because it forms an increasing subsequence of length 3 starting from 2, through 5, to 6.
    • 2 can extend [2], but does not contribute to a longer subsequence, so left[5] = 2.
    • 3 can extend [2, 2], making left[6] = 3 as it forms an increasing subsequence of length 3.
    • 1 doesn't extend any sequences meaningfully, so left doesn't change for it.
  • The left array after iterations: [1, 1, 1, 2, 3, 2, 3, 1].
  1. Find the longest decreasing subsequences from the right: Apply analogous logic as LIS from the left, but in reverse.
  • Initialize right array with [1, 1, 1, 1, 1, 1, 1, 1].
  • Traverse the elements from right to left:
    • 3 starts a new subsequence, so right stays the same.
    • 2 can extend 3, so right[5] = 2.
    • 6 and 5 don't find smaller following elements, no changes.
    • 1 and 1 can extend multiple subsequences, so right[1] and right[2] become 2 because they can extend 2 and 3.
  • The right array after iterations: [1, 2, 2, 1, 1, 2, 1, 1].
  1. Combine the LIS and decreasing subsequences:
  • We calculate the possible length for each element as the peak ignoring the first and last element:
  • Peaks [1, 3, 4, 6]: their combined lengths [1, 2, 3, 3] + [2, 1, 1, 2] - 1.
  • Lengths are [2, 2, 3, 4] for those peaks.
  1. Find the longest mountain and determine minimum removals:
  • The longest mountain has length 4 (from peak 6).
  • Minimum removals = Total length of nums (8) - length of the longest mountain (4).
  • Therefore, the minimum number of elements that needs to be removed to form a mountain array is 8 - 4 = 4.

Using this approach, the elements at positions [3, 4, 5, 6] (zero-based index) form the longest mountain subsequence, [5, 6, 2, 3], and removing the elements at positions [0, 1, 2, 7] results in a valid mountain array with the fewest deletions.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minimumMountainRemovals(self, nums: List[int]) -> int:
5        # Length of the input list
6        length = len(nums)
7
8        # Initialize DP arrays to store the longest increasing subsequence
9        # from the left and from the right for each element
10        left_lis = [1] * length
11        right_lis = [1] * length
12
13        # Populate the left LIS DP array
14        for i in range(1, length):
15            for j in range(i):
16                # If the current number is greater than a number before it,
17                # update the DP array to include the longer subsequence
18                if nums[i] > nums[j]:
19                    left_lis[i] = max(left_lis[i], left_lis[j] + 1)
20
21        # Populate the right LIS DP array
22        for i in range(length - 2, -1, -1):
23            for j in range(i + 1, length):
24                # If the current number is greater than a number after it,
25                # update the DP array to include the longer subsequence
26                if nums[i] > nums[j]:
27                    right_lis[i] = max(right_lis[i], right_lis[j] + 1)
28
29        # Calculate the maximum length of bitonic subsequence
30        # which is a sum of left and right sequences minus 1
31        # because the peak element is counted twice
32        # Only consider peak elements which are part of both LIS and LDS
33        max_bitonic_len = max(
34            (left + right - 1)
35            for left, right in zip(left_lis, right_lis)
36            if left > 1 and right > 1
37        )
38
39        # The minimum number of removals is the total length of the array
40        # minus the maximum length of the bitonic subsequence
41        return length - max_bitonic_len
42
1class Solution {
2    public int minimumMountainRemovals(int[] nums) {
3        int length = nums.length;
4
5        // Arrays to store the longest increasing subsequence ending at each index from the left and right
6        int[] longestIncreasingLeft = new int[length];
7        int[] longestIncreasingRight = new int[length];
8
9        // Initialize the arrays with a default value of 1
10        Arrays.fill(longestIncreasingLeft, 1);
11        Arrays.fill(longestIncreasingRight, 1);
12
13        // Calculate the longest increasing subsequence for each index from the left
14        for (int i = 1; i < length; ++i) {
15            for (int j = 0; j < i; ++j) {
16                if (nums[i] > nums[j]) {
17                    longestIncreasingLeft[i] = Math.max(longestIncreasingLeft[i], longestIncreasingLeft[j] + 1);
18                }
19            }
20        }
21
22        // Calculate the longest increasing subsequence for each index from the right
23        for (int i = length - 2; i >= 0; --i) {
24            for (int j = i + 1; j < length; ++j) {
25                if (nums[i] > nums[j]) {
26                    longestIncreasingRight[i] = Math.max(longestIncreasingRight[i], longestIncreasingRight[j] + 1);
27                }
28            }
29        }
30
31        int maxMountainSize = 0;
32        // Find the maximum size of a valid mountain subsequence
33        for (int i = 0; i < length; ++i) {
34            // To form a mountain, the element nums[i] must be increasing and decreasing, both sides at least by 1 element
35            if (longestIncreasingLeft[i] > 1 && longestIncreasingRight[i] > 1) {
36                // Calculate the length of the mountain and update the maximum mountain size
37                int mountainSize = longestIncreasingLeft[i] + longestIncreasingRight[i] - 1;
38                maxMountainSize = Math.max(maxMountainSize, mountainSize);
39            }
40        }
41
42        // The minimum removals is the array length minus the maximum mountain size
43        return length - maxMountainSize;
44    }
45}
46
1class Solution {
2public:
3    int minimumMountainRemovals(vector<int>& nums) {
4        int size = nums.size();
5        vector<int> left(size, 1), right(size, 1); // Initialize LIS vectors for left and right
6
7        // Compute the length of longest increasing subsequence (LIS) from the left
8        for (int i = 1; i < size; ++i) {
9            for (int j = 0; j < i; ++j) {
10                if (nums[i] > nums[j]) {
11                    left[i] = max(left[i], left[j] + 1); // Update the LIS at i based on j
12                }
13            }
14        }
15
16        // Compute the length of LIS from the right
17        for (int i = size - 2; i >= 0; --i) {
18            for (int j = i + 1; j < size; ++j) {
19                if (nums[i] > nums[j]) {
20                    right[i] = max(right[i], right[j] + 1); // Update the LIS at i based on j
21                }
22            }
23        }
24
25        int maxMountainLength = 0; // Variable to keep track of the longest mountain length
26
27        // Find the maximum length of a bitonic subsequence (peak of the mountain)
28        for (int i = 0; i < size; ++i) {
29            // Ensure we have an increasing and decreasing subsequence, i.e., a peak
30            if (left[i] > 1 && right[i] > 1) {
31                // Update the maxMountainLength if left[i] + right[i] - 1 is greater
32                maxMountainLength = max(maxMountainLength, left[i] + right[i] - 1);
33            }
34        }
35
36        // The minimum removals will be the total number of elements minus the longest mountain length
37        return size - maxMountainLength;
38    }
39};
40
1function minimumMountainRemovals(nums: number[]): number {
2    // Get the length of the input array.
3    const length = nums.length;
4
5    // Initialize arrays to keep track of the length of increasing subsequence from the left and right.
6    const increasingFromLeft = new Array(length).fill(1);
7    const increasingFromRight = new Array(length).fill(1);
8
9    // Populate the increasingFromLeft array with the longest increasing subsequence ending at each index.
10    for (let i = 1; i < length; ++i) {
11        for (let j = 0; j < i; ++j) {
12            if (nums[i] > nums[j]) {
13                increasingFromLeft[i] = Math.max(increasingFromLeft[i], increasingFromLeft[j] + 1);
14            }
15        }
16    }
17
18    // Populate the increasingFromRight array with the longest increasing subsequence starting at each index.
19    for (let i = length - 2; i >= 0; --i) {
20        for (let j = i + 1; j < length; ++j) {
21            if (nums[i] > nums[j]) {
22                increasingFromRight[i] = Math.max(increasingFromRight[i], increasingFromRight[j] + 1);
23            }
24        }
25    }
26
27    // Initialize a variable to keep track of the max length of a bitonic subsequence.
28    let maxLengthBitonic = 0;
29
30    // Calculate the maximum length of the bitonic subsequence.
31    // A bitonic subsequence increases and then decreases.
32    // It must increase and decrease by at least one element on each side.
33    for (let i = 0; i < length; ++i) {
34        if (increasingFromLeft[i] > 1 && increasingFromRight[i] > 1) {
35            maxLengthBitonic = Math.max(maxLengthBitonic, increasingFromLeft[i] + increasingFromRight[i] - 1);
36        }
37    }
38
39    // The minimum mountain removals is the total length minus the max length of bitonic subsequence.
40    return length - maxLengthBitonic;
41}
42
Not Sure What to Study? Take the 2-min Quiz:

How does quick sort divide the problem into subproblems?

Time and Space Complexity

The given Python code defines a function minimumMountainRemovals that finds the minimum number of elements to remove from an array to make the remaining array a mountain array, where a mountain array is defined as an array where elements first strictly increase then strictly decrease.

Time Complexity

The time complexity of the provided solution can be analyzed by examining its nested loops.

  • The first for loop, responsible for populating the left list, contains a nested loop that compares each element to all previous elements to find the longest increasing subsequence up to the current index. This loop runs in O(n^2) time, where n is the length of the nums array.

  • The second for loop, which populates the right list, also contains a nested loop that runs in reverse to find the longest decreasing subsequence from the current index to the end of the array. This loop similarly has a time complexity of O(n^2).

  • After computing the left and right lists, the final line involves a single loop that iterates over both lists to find the maximum value of a + b - 1 where a and b refer to corresponding values of left and right. This loop runs in O(n) time.

Adding up the complexities of these loops, the first two dominant ones give us a time complexity of O(n^2 + n^2) which simplifies to O(n^2) since we drop constants and lower order terms when expressing big O notation.

Therefore, the total time complexity of the function is O(n^2).

Space Complexity

The space complexity is determined by the amount of additional memory the algorithm uses in relation to the input size:

  • We have two lists, left and right, each of size n. Therefore, the space used by these lists is 2n, which in big O notation is O(n).

  • Aside from the left and right lists, there are only a few integer variables used, which do not scale with the input and thus contribute O(1) to the space complexity.

Hence, the total space complexity of the function is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How many times is a tree node visited in a depth first search?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫