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.

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.

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].

2. 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].

3. 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.

4. 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

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.