Mountain Array and LIS

This is a biweekly problem of this week (Thanksgiving week of 2020 :)).

1671. Minimum Number of Removals to Make Mountain Array

Solutions

We can change the problem to LIS and LDS problem. LIS has the O(N²) and O(N log K) where K is the length of the LIS.

O(N²) , runtime 524 ms.

class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        const int n = nums.size();
        vector<int> I(n, 1), D(n, 1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    I[i] = max(I[i], I[j] + 1);
                }
            }
        }
        for (int i = n-1; i >=0; --i) {
            for (int j = n-1; j > i; --j) {
                if (nums[j] < nums[i]) {
                    D[i] = max(D[i], D[j] + 1);
                }
            }
        }
        int ret = 0;
        for (int i = 1; i < n - 1; ++i) {
            ret = max(ret, (I[i] + D[i] - 1) >=3 ? I[i] + D[i] - 1:0);
        }
        return n - ret;
    }
};

O(N log K) , runtime 40ms.

The basic idea for this one is maintaining a longest increasing sequence and greedly updating the old longest increasing sequence by some available small values.
For example, if we have 1, 10, 2, 5, 4

• for 1, we have [1]
• for 10, we have [1, 10]
• for 2, we have [1, 2], 10 is updated to 2 as [1, 2] can have more potential to build a longer sequence than [1, 10],
• for 5, we have [1, 2, 5]
• for 4, we have [1, 2, 4].

class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        const int n = nums.size();
        vector<int> I(n, 1), D(n, 1);
        vector<int> LIS(n, 0), LDS(n, 0);
        int k =0;
        for (int i = 0; i < n; ++i) {// n log k
            auto pos = lower_bound(LIS.begin(), LIS.begin()+k, nums[i])-LIS.begin();
            LIS[pos] = nums[i];
            if (pos==k) k = pos + 1;
            I[i] = k;
        }
        k = 0;
        for (int i = n-1; i >=0; --i) {// n log k
            auto pos = lower_bound(LDS.begin(), LDS.begin()+k, nums[i])-LDS.begin();
            LDS[pos] = nums[i];
            if (pos==k) k = pos + 1;
            D[i] = k;
        }
        int ret = 0;
        for (int i = 1; i < n - 1; ++i) {
            ret = max(ret, (I[i] + D[i] - 1) >=3 ? I[i] + D[i] - 1:0);
        }
        return n - ret;
    }
};

Thanks for reading.