Minimum Number of Removals to Make Mountain Array

class Solution {
public:
    vector<int> calculateLIS(vector<int>& sequence) {
        vector<int> lengths(sequence.size(), 1);
        vector<int> lis = {sequence[0]};

        for (int i = 1; i < sequence.size(); i++) {
            int idx = lower_bound(lis.begin(), lis.end(), sequence[i]) - lis.begin();

            if (idx == lis.size()) {
                lis.push_back(sequence[i]);
            } else {
                lis[idx] = sequence[i];
            }

            lengths[i] = lis.size();
        }

        return lengths;
    }

    int minDeletionsToGetMountainArray(vector<int>& nums) {
        int N = nums.size();
        vector<int> ascSeq = calculateLIS(nums);

        reverse(nums.begin(), nums.end());
        vector<int> descSeq = calculateLIS(nums);
        reverse(descSeq.begin(), descSeq.end());

        int minValue = INT_MAX;
        for (int i = 0; i < N; i++) {
            if (ascSeq[i] > 1 && descSeq[i] > 1) {
                minValue = min(minValue, N - ascSeq[i] - descSeq[i] + 1);
            }
        }

        return minValue;
    }
};

The given C++ code offers a solution to find the minimum number of removals required to turn an array into a mountain array. A mountain array is defined as an array where elements increase to a peak where they begin to decrease. The core of the solution involves dynamic programming techniques to determine the longest increasing subsequence (LIS) from both the left (ascending sequence) and the right (descending sequence).

• Begin by calculating the ascending LIS for the original array using the calculateLIS function. This function uses a binary search approach to determine the length of the LIS at each position of the array, storing the result in a vector.

• Reverse the input array and reuse the calculateLIS function to calculate the descending LIS, then restore the original order by reversing the results.

• After both LIS sequences are procured, iterate through the array to determine the potential peak of the mountain. Check if an index has a valid ascending and descending sequence length greater than 1, then calculate the potential minimum removals by using the formula: total array length minus the sum of lengths of ascending and descending sequences at that index, plus 1 (for the peak itself).

• The result of the function minDeletionsToGetMountainArray returns the smallest number of deletions across all potential peaks, leveraging the information from both LIS calculations to find the optimal solution.

This well-structured algorithm ensures that the process is both efficient and clear, making use of dynamic programming principles and careful array manipulations to achieve the desired result.

class Solution {

    private List<Integer> computeLISLengths(List<Integer> elements) {
        List<Integer> lengths = new ArrayList<>(
            Collections.nCopies(elements.size(), 1)
        );
        List<Integer> lis = new ArrayList<>();
        lis.add(elements.get(0));

        for (int i = 1; i < elements.size(); i++) {
            int idx = findPosition(lis, elements.get(i));

            // Extend LIS if current element is greater
            if (idx == lis.size()) {
                lis.add(elements.get(i));
            } else {
                // Replace in LIS for optimum subsequence
                lis.set(idx, elements.get(i));
            }

            lengths.set(i, lis.size());
        }

        return lengths;
    }

    // Binary search for finding the correct position in LIS
    private int findPosition(List<Integer> lis, int item) {
        int start = 0, end = lis.size() - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (lis.get(mid) >= item) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    public int computeMinRemovalsForMountain(int[] data) {
        int n = data.length;
        List<Integer> dataList = new ArrayList<>();
        for (int x : data) dataList.add(x);

        List<Integer> ascLIS = computeLISLengths(dataList);

        Collections.reverse(dataList);
        List<Integer> descLIS = computeLISLengths(dataList);
        Collections.reverse(descLIS);

        int minRemovals = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (ascLIS.get(i) > 1 && descLIS.get(i) > 1) {
                minRemovals = Math.min(
                    minRemovals,
                    n - ascLIS.get(i) - descLIS.get(i) + 1
                );
            }
        }

        return minRemovals;
    }
}

This solution addresses the problem of finding the minimum number of removals necessary to transform an array into a "mountain" array, where a mountain array is defined as an array that first strictly increases to a peak element and then strictly decreases.

The approach involves the following key steps:

1. Compute the Longest Increasing Subsequence (LIS) lengths from the left (ascending) and from the right (descending) to identify potential peak elements.
2. Convert the given integer array into a List for processing.
3. Calculate the LIS lengths for both ascending sequences and descending sequences, where the descending sequence computation involves reversing the array to reuse the LIS method.
4. Iterate through the element positions considering each as a possible peak. For each element, sum the lengths of LIS on both sides (excluding the peak itself since it gets counted in both).
5. Calculate potential minimum removals using the formula n - (LIS length from the left at i + LIS length from the right at i - 1). The formula corresponds to the full length of the array minus the total number of elements participating in the mountain form at index i.
6. Return the minimal value of such calculations, which represents the minimum removals required to form a valid mountain array.

This algorithm leverages dynamic programming to compute the LIS efficiently by binary search and provides a comprehensive method to decide removals based on forming the mountain sequence optimally. This code is implemented in Java and utilizes essential data structures like ArrayList for holding operations, emphasizing a clear and effective strategy to tackle the explored problem.

class Solution:
    def findLIS(self, sequence: List[int]) -> List[int]:
        lis_dp = [1] * len(sequence)
        increasing_sequence = [sequence[0]]

        for index in range(1, len(sequence)):
            position = self.binarySearch(increasing_sequence, sequence[index])

            if position == len(increasing_sequence):
                increasing_sequence.append(sequence[index])
            else:
                increasing_sequence[position] = sequence[index]

            lis_dp[index] = len(increasing_sequence)

        return lis_dp

    def binarySearch(self, sorted_list: List[int], value: int) -> int:
        low, high = 0, len(sorted_list)
        while low < high:
            mid = (low + high) // 2
            if sorted_list[mid] < value:
                low = mid + 1
            else:
                high = mid
        return low

    def removeMountainIndexes(self, nums: List[int]) -> int:
        length_nums = len(nums)

        lis_lengths = self.findLIS(nums)

        nums.reverse()
        lds_lengths = self.findLIS(nums)
        lds_lengths.reverse()

        lowest_removals = float("inf")
        for i in range(length_nums):
            if lis_lengths[i] > 1 and lds_lengths[i] > 1:
                lowest_removals = min(
                    lowest_removals, length_nums - lis_lengths[i] - lds_lengths[i] + 1
                )

        return lowest_removals

The solution to find the minimum number of removals to make a mountain array in Python involves several steps leveraging dynamic programming and binary search. The task is essentially to determine the smallest sequence you can remove from the array to leave a remaining sequence that increases to a peak and then decreases, a property typical of a mountain array.

• First, define a helper function findLIS to compute the Longest Increasing Subsequence (LIS) lengths for any sequence. This function uses a dynamic programming approach where lis_dp tracks the length of LIS ending at each index. It utilizes a binary search (binarySearch method) to maintain a list called increasing_sequence that efficiently finds positions for potential LIS improvement.
• The primary function removeMountainIndexes determines the minimum removals needed. It first evaluates the LIS from the front of the array nums using findLIS.
• To handle the decreasing sequence, the input array nums is first reversed, and the LIS of this reversed array is calculated, which actually represents the Longest Decreasing Subsequence (LDS) for the original array. Remember to reverse this result to align with the original array order.
• Iterate through each index of the array, considering an element as a potential peak if it is part of both LIS and LDS and has length greater than 1. Calculate the potential minimum removals using the formula: total length of the array - (LIS length + LDS length at the index - 1).
• Finally, return the smallest computed removal count which results in retaining a mountain-like array structure.

This algorithm efficiently finds the necessary minimum removals to achieve the desired mountain array by combining the insights from LIS and LDS, leveraging dynamic programming techniques for optimal performance.