Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Steps of Algorithm
3.
Implementation in C++
3.1.
Complexity Analysis
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

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

Author Ayush Tiwari
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

In this article, we will discuss a very good problem: 'Minimum number of removals to make a mountain array.'  

Mountain array is an array where,

There exists some index i with 0 < i < arr.size - 1 where,

arr[0] < arr[1] < ... < arr[i - 1] < arr[i]

arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Problem Statement

Given an integer array arr, return the minimum number of elements to remove to make arr​​​ a mountain array.
Constraints:

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

Sample Examples

Example 1:

Input: arr = [1, 3, 1]
Output: 0

Explanation: we do not need to remove any elements because the array itself is a mountain array.

 

Example 2:

Input: arr = [2,1,1,5,6,2,3,1]
Output: 0

Explanation: Remove the elements at indices 0, 1, and 5, making the array arr = [1,5,6,3,1].

Approach

The basic idea to solve this problem will be to find the longest mountain subsequence first then remove it from the total number of elements of an array.

Therefore the number of removals = Total length of given array-  (longest mountain subsequence).  

To calculate the longest mountain subsequence, first, calculate the longest increasing subsequence from left for each index and store it in an array(say, dpleft). Similarly, calculate the longest increasing subsequence from left for each index and store it in an array(say, dpright). In this efficient approach, dpleft and dpright can be filled in better time complexity (nlogn). You can also see N^2 approach of the given problem.

Now consider each 0<i<n to be the middle of a mountain subsequence with the length of subsequence as dpleft[i]+dright[i]-1 (we subtract 1 to not double count the middle element).

However, we will check for i only if dpleft[i]>1 and dpright[i]>1 because the sequence is not a mountain sequence, and removing conditions can give inconsistent results if either dpleft[i] or dpright[i] = 1, then it means that the sequence is either strictly increasing or decreasing.

Steps of Algorithm

  1. Take all the inputs in the given format.
  2. Declare two arrays dpleft and dpright to store LIS from left and right, respectively.
  3. Declare a temporary vector lis, which will help in filling dpleft and dpright.
  4. Fill dpleft LIS for each index, and this can be done with the DP solution of LIS.
  5. While filling the dpleft we will use a lower_bound()/binary search function to search for elements in the lis vector and then update the vector accordingly.
  6. If the element is not present in lis vector and greater than the last element, insert it at the end.
  7. Else use lower bound/binary search for the element then update the element in lis, which is just greater or equal to the current element of the array.
  8. Reverse the original array.
  9. Fill dpright using the same logic.
  10. Then traverse each index of the array, and check the length of the maximum mountain array for each index.
  11. Length of each mountain array will be,  dpleft[i]+dright[i]-1 , after checking condition only if dpleft[i]>1 and dpright[i]>1. 
  12. Store max_length in variable and keep updating it accordingly.
  13. Output N - max_length that will be the required result.

Must Read Lower Bound in C++

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

 

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!

Previous article
Minimum Number of Removals to Make a Mountain Array
Next article
Minimum number of operation required to convert number x into y
Live masterclass