Minimum Number of Removals to Make a Mountain Array - Part 2

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
/*  function to returns minimum removals needed
 to make a mountain array */
int minMountainRemovals(vector<int> &a)
{
    /*  Declaring two dp vectors to store the maximum result for any indexing
        from left and right respectively */
    int n = a.size();
    vector<int> dpleft(a.size(), 1);
    vector<int> dpright(a.size(), 1);
    // vector<int> dpleft,dpright;
    
    /* declaring temporary vector lis
    it will help us to fill dpleft and dpright in nlongn complexity */
    vector<int> lis;
    // filing dpleft using lis in nlogn
    for (int i = 0; i < n; i++)
    {
        auto it = lower_bound(lis.begin(), lis.end(), a[i]);
        // if element is to be inserted in lis
        if (it != lis.end())
        {
            int idx = it - lis.begin();
            lis[idx] = a[i];
            dpleft[i] = idx + 1;
        }
        // if element in not present in lis insert at the end
        else
        {
            lis.push_back(a[i]);
            dpleft[i] = lis.size();
        }
    }
    
    // clearing lis vector to use to calculate right lis
    lis.clear();
    // reversing the original vector to calculate lis from back
    reverse(a.begin(), a.end());
    
    // filling dpright
    for (int i = 0; i < n; i++)
    {
        auto it = lower_bound(lis.begin(), lis.end(), a[i]);
        if (it != lis.end())
        {
            int idx = it - lis.begin();
            lis[idx] = a[i];
            dpright[i] = idx + 1;
        }
        // if element in not present in lis insert at end
        else
        {
            lis.push_back(a[i]);
            dpright[i] = lis.size();
        }
    }
    int longest = 0;
    
    // for every index check for longest mountain array,
    for (int i = 1; i < a.size() - 1; i++)
    {
        if (dpleft[i] > 1 && dpright[i] > 1)
        {
            int ans = dpleft[i] + dpright[i] - 1;
            longest = max(longest, ans);
        }
    }
    // returning removals
    return a.size() - longest;
}
int main()
{
    int n;
    cin >> n;
    // taking input for array size
    vector<int> a(n, 0);
    // Taking array input as vector
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    
    // calling minMountainRemovals function to return minimum number of       removals
    int removals = minMountainRemovals(a);
    cout << removals << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input:

8
2 1 1 5 6 2 3 1

Output:

3

Complexity Analysis

Time Complexity: The time complexity of the above approach is O(NlogN). LIS is stored for each indexing in dpleft and dpright array, and this is done with the NlogN approach.

Space Complexity: The time complexity of the above approach is O(N) since the above approach stores result in dpleft and dpright in the single dimensional array.

Check out this problem - Shortest Common Supersequence.

FAQs

1. What is the use of the lower_bound() function in C++?
   The lower_bound() function in C++ is used to return an iterator pointing to the first element in the range [first, last) which has a value not less than the passed parameter value.
    
2. What is the necessary condition to use the lower_bound function on an array or vector?
   To use lower_bound function array or vector must be in sorted form. It is just like a binary search function that only works for sorted data.
    
3. What is LIS?
   The Longest Increasing Subsequence (LIS) is a problem that finds the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. 
    
4. What is dynamic programming?
   Dynamic Programming (DP) is an algorithmic technique for optimizing plain recursion; it breaks down problems into simpler subproblems and utilizes the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems.
    
5. How to use lower_bound to find the index of any number in a vector?
   You can use the following code to get the index of an element in a vector. The code will give the first index of element if the element is present or the index of element which is just greater than the current element.
   lower= lower_bound(v.begin(), v.end(), key)- v.begin();

Key Takeaways

In this article, we have extensively discussed the efficient approach and algorithm for the problem ‘minimum number of removals to make mountain array.’ We also saw its implementation and discussed time and space complexity.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available; take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Learning!