• Posts

Problem 1671 Minimum Number of Removals to Make Mountain Array

Problem Statement

Link - Problem 1671

Question

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.

Example 1:

Input: nums = [1,3,1]
Output: 0
Explanation: The array itself is a mountain array so we do not need to remove any elements.

Example 2:

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

Constraints:

• 3 <= nums.length <= 1000
• 1 <= nums[i] <= 109
• It is guaranteed that you can make a mountain array out of nums.

Solution

class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size();
        vector<int> LIS(n, 1), LDS(n, 1);

        // Compute LIS up to each index
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    LIS[i] = max(LIS[i], LIS[j] + 1);
                }
            }
        }

        // Compute LDS from each index
        for (int i = n - 1; i >= 0; --i) {
            for (int j = n - 1; j > i; --j) {
                if (nums[i] > nums[j]) {
                    LDS[i] = max(LDS[i], LDS[j] + 1);
                }
            }
        }

        int maxMountainLength = 0;

        // Find the maximum mountain length
        for (int i = 1; i < n - 1; ++i) {
            if (LIS[i] > 1 && LDS[i] > 1) {  // Valid peak
                maxMountainLength = max(maxMountainLength, LIS[i] + LDS[i] - 1);
            }
        }

        return n - maxMountainLength;
    }
};

Complexity Analysis

| Algorithm           | Time Complexity | Space Complexity |
| ------------------- | --------------- | ---------------- |
| Dynamic Programming | O(n^2)          | O(n)             |

Explanation

Intial Thoughts

To approach this problem, think about how a mountain range forms - it has to increase and then decrease. We need to find the longest sequence of numbers in the array that follows this pattern. It’s also essential to identify the peak point where the sequence starts to decrease. This requires analyzing the array from both ends towards the center. Consider how many elements can be removed to make the array resemble a mountain range.

Intuitive Analysis

Imagine the array as a series of hills and valleys. The goal is to find the largest mountain that can be formed by removing elements. Think of the Longest Increasing Subsequence (LIS) and Longest Decreasing Subsequence (LDS) as tools to analyze the increase and decrease patterns in the array. By combining these patterns, we can identify the peak of the mountain and calculate the minimum number of elements to remove. Consider the trade-offs between removing elements to create a longer mountain range versus preserving the existing patterns.

1. Intuition

• To solve this problem, we need to understand the concept of a mountain array and how to identify it
• A mountain array has a peak element that is greater than its neighbors, and the elements before the peak are in increasing order, while the elements after the peak are in decreasing order
• We can use dynamic programming to find the longest increasing subsequence (LIS) and the longest decreasing subsequence (LDS) in the array
• The key insight is to find the maximum mountain length by combining the LIS and LDS at each index
• We need to ensure that the peak element is valid by checking if the LIS and LDS at that index are both greater than 1
• The minimum number of elements to remove is the difference between the total length of the array and the maximum mountain length
• This approach works because it considers all possible mountain arrays that can be formed from the given array

2. Implementation

• We start by initializing two arrays LIS and LDS of size n with all elements set to 1, where n is the length of the input array nums
• We then compute the LIS up to each index using a nested loop, where LIS[i] is updated to max(LIS[i], LIS[j] + 1) if nums[i] > nums[j]
• Similarly, we compute the LDS from each index using a nested loop, where LDS[i] is updated to max(LDS[i], LDS[j] + 1) if nums[i] > nums[j]
• We initialize maxMountainLength to 0 and iterate through the array to find the maximum mountain length by combining LIS[i] and LDS[i] at each index
• We update maxMountainLength to max(maxMountainLength, LIS[i] + LDS[i] - 1) if LIS[i] > 1 and LDS[i] > 1
• Finally, we return n - maxMountainLength as the minimum number of elements to remove to make the array a mountain array
• The time complexity of this solution is O(n^2) due to the nested loops, and the space complexity is O(n) for the LIS and LDS arrays

Complexity Analysis

Time Complexity:

• The algorithm consists of three main loops: for (int i = 0; i < n; ++i) and for (int i = n - 1; i >= 0; --i) to compute LIS and LDS respectively, and for (int i = 1; i < n - 1; ++i) to find the maximum mountain length. Each of these loops has a time complexity of O(n). However, within the first two loops, there are nested loops that also run in O(n) time, resulting in an overall time complexity of O(n^2). This is because for each element, we are potentially comparing it with every other element.
• The dominant operations in the algorithm are the nested loops used to compute LIS and LDS. In the worst case, the if (nums[i] > nums[j]) condition is evaluated n*(n-1)/2 times, which simplifies to O(n^2). The maximum mountain length computation loop has a linear time complexity of O(n), but it does not dominate the overall time complexity.
• Therefore, the time complexity of the algorithm is O(n^2) because the nested loops used to compute LIS and LDS result in quadratic time complexity. This classification holds for both the worst and average cases, as the algorithm must always compare each element with every other element. The best case time complexity is also O(n^2), as the algorithm’s structure does not allow for a better performance even when the input is optimally arranged.

Space Complexity:

• The algorithm uses two additional vectors, LIS and LDS, to store the lengths of the longest increasing and decreasing subsequences respectively. Each of these vectors has a length of n, where n is the number of elements in the input array.
• The space complexity is dominated by the memory used to store the LIS and LDS vectors. The input array also occupies space, but it is not included in the space complexity analysis because it is part of the input, not the extra space used by the algorithm.
• Therefore, the space complexity of the algorithm is O(n) because we need to store the LIS and LDS values for each element in the input array. This classification applies to both the worst and average cases, as the algorithm always requires the same amount of extra space regardless of the input arrangement.

Footnote

This question is rated as Hard difficulty.

Hints

Think the opposite direction instead of minimum elements to remove the maximum mountain subsequence

Think of LIS it’s kind of close

Similar Questions: