Minimum Number of Removals to Make Mountain Array

• The problem of finding the minimum number of removals is equivalent to finding the length of the longest subsequence that is a mountain array.
• We can iterate through each element nums[i] and consider it as the potential peak of a mountain subsequence.
• For each potential peak nums[i], we need to find the length of the Longest Increasing Subsequence (LIS) ending at i and the length of the Longest Decreasing Subsequence (LDS) starting at i.
• The length of the mountain with peak nums[i] is length(LIS) + length(LDS) - 1.
• We can use dynamic programming to find these lengths.
  1. Create an array lis of size n. lis[i] will store the length of the LIS ending at index i.
  2. Calculate lis by iterating from left to right. For each i, lis[i] = 1 + max(lis[j]) for all j < i where nums[j] < nums[i].
  3. Create an array lds of size n. lds[i] will store the length of the LDS starting at index i.
  4. Calculate lds by iterating from right to left. For each i, lds[i] = 1 + max(lds[j]) for all j > i where nums[j] < nums[i].
  5. Iterate through all possible peaks i. If lis[i] > 1 and lds[i] > 1 (to ensure both slopes exist), calculate the mountain length lis[i] + lds[i] - 1 and find the maximum among all valid peaks.
  6. The result is n - maxLength.

A mountain array has a single peak. We can iterate through every element nums[i] and treat it as the peak of a potential mountain subsequence. For nums[i] to be a valid peak, there must be a strictly increasing subsequence ending at nums[i] and a strictly decreasing subsequence starting from nums[i]. The length of such a mountain subsequence would be the sum of the lengths of these two subsequences, minus one (since the peak is counted in both).

We can compute the lengths of these subsequences using dynamic programming:

1. Longest Increasing Subsequence (LIS) from the left: We create an array lis where lis[i] stores the length of the longest increasing subsequence of nums that ends at index i. We can compute this in O(n^2) time.

2. Longest Decreasing Subsequence (LDS) from the right: Similarly, we create an array lds where lds[i] stores the length of the longest decreasing subsequence of nums that starts at index i. This is equivalent to finding the LIS from right to left. This also takes O(n^2) time.

After computing both lis and lds arrays, we iterate through each index i from 0 to n-1. For each i, if lis[i] > 1 and lds[i] > 1 (which ensures that there's at least one element on the increasing slope and one on the decreasing slope), we consider nums[i] as a potential peak. The length of the mountain array with this peak is lis[i] + lds[i] - 1. We find the maximum possible length over all valid peaks.

Finally, the minimum number of removals is the total number of elements n minus this maximum length.

1import java.util.Arrays;2 3class Solution {4    public int minimumMountainRemovals(int[] nums) {5        int n = nums.length;6        int[] lis = new int[n];7        int[] lds = new int[n];8        Arrays.fill(lis, 1);9        Arrays.fill(lds, 1);10 11        // Calculate LIS lengths from left to right12        for (int i = 1; i < n; i++) {13            for (int j = 0; j < i; j++) {14                if (nums[i] > nums[j]) {15                    lis[i] = Math.max(lis[i], lis[j] + 1);16                }17            }18        }19 20        // Calculate LDS lengths (as LIS from right to left)21        for (int i = n - 2; i >= 0; i--) {22            for (int j = n - 1; j > i; j--) {23                if (nums[i] > nums[j]) {24                    lds[i] = Math.max(lds[i], lds[j] + 1);25                }26            }27        }28 29        int maxLength = 0;30        for (int i = 0; i < n; i++) {31            // A valid mountain peak must have both a left and a right side.32            if (lis[i] > 1 && lds[i] > 1) {33                maxLength = Math.max(maxLength, lis[i] + lds[i] - 1);34            }35        }36 37        return n - maxLength;38    }39}

• This approach follows the same high-level strategy as the O(n^2) DP solution: find the longest mountain subsequence by checking every possible peak.
• The improvement comes from optimizing the calculation of the LIS and LDS arrays from O(n^2) to O(n log n).
• Optimized LIS/LDS Calculation:
  1. To compute lis[i] (length of LIS ending at i), we maintain a sorted list, tails, representing the smallest tail of all increasing subsequences of a given length.
  2. For each num in nums, we use binary search on tails to find its place. This tells us the length of the LIS ending with num.
  3. We perform this process once from left to right to compute the lis array.
  4. We repeat the process from right to left to compute the lds array.
  5. The rest of the logic (finding the max length and the result) remains the same as the previous approach.

The fundamental idea is identical to the first approach: find the length of the longest mountain subsequence by considering each element as a potential peak. The length of a mountain with peak nums[i] is lis[i] + lds[i] - 1.

The optimization lies in how we compute the lis and lds arrays. The standard O(n^2) LIS algorithm can be improved to O(n log n).

Algorithm for O(n log n) LIS/LDS:

1. Calculate lis array (LIS from left):

   • We'll use an auxiliary list, tails, which will store the smallest tail of all increasing subsequences of a certain length. This list is always sorted.
   • We iterate through nums from left to right. For each nums[i], we find the position to insert it into tails to maintain sorted order using binary search. Let this position be idx.
   • If idx is at the end of tails, we append nums[i]. Otherwise, we replace the element at tails[idx] with nums[i]. This step ensures that for a given subsequence length, we keep the one with the smallest possible tail, which gives a better chance for extension later.
   • The length of the LIS ending at nums[i] is idx + 1. We store this in lis[i].

2. Calculate lds array (LIS from right):

   • We apply the exact same logic, but we iterate through nums from right to left (i = n-1 down to 0). This calculates the length of the LIS ending at i considering elements to its right, which is precisely the length of the LDS starting at i that we need. We store this in lds[i].

3. Find Longest Mountain:

   • With the lis and lds arrays computed, we iterate through them. For any index i where lis[i] > 1 and lds[i] > 1, we calculate the potential mountain length lis[i] + lds[i] - 1 and update our maxLength.

4. Final Result:

   • The minimum removals required is n - maxLength.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public int minimumMountainRemovals(int[] nums) {7        int n = nums.length;8        int[] lis = new int[n];9        List<Integer> tails = new ArrayList<>();10 11        // Calculate LIS from left to right12        for (int i = 0; i < n; i++) {13            int num = nums[i];14            int idx = Collections.binarySearch(tails, num);15            if (idx < 0) {16                idx = -(idx + 1);17            }18 19            if (idx == tails.size()) {20                tails.add(num);21            } else {22                tails.set(idx, num);23            }24            lis[i] = idx + 1;25        }26 27        int[] lds = new int[n];28        tails.clear();29 30        // Calculate LIS from right to left (which is LDS)31        for (int i = n - 1; i >= 0; i--) {32            int num = nums[i];33            int idx = Collections.binarySearch(tails, num);34            if (idx < 0) {35                idx = -(idx + 1);36            }37 38            if (idx == tails.size()) {39                tails.add(num);40            } else {41                tails.set(idx, num);42            }43            lds[i] = idx + 1;44        }45 46        int maxLength = 0;47        for (int i = 0; i < n; i++) {48            if (lis[i] > 1 && lds[i] > 1) {49                maxLength = Math.max(maxLength, lis[i] + lds[i] - 1);50            }51        }52 53        return n - maxLength;54    }55}