Table of contents
1.
Introduction
1.1.
Problem Statement
2.
Approach
2.1.
Algorithm
3.
Implementation in C++
3.1.
Complexity Analysis
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Minimum Number of Removals to Make a Mountain Array

Author Ayush Tiwari
1 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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.

Sample Example
Example 1:

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

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

Example 2:

Input: arr = [2,1,1,5,6,2,3,1]
Output: 3
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).
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.

For an efficient approach, you can refer to Minimum Number of Removals to Make Mountain Array - Part 2.

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. Fill dpleft and dpright with LIS for each index, and this can be done with the DP solution of LIS.
  4. Traverse each index of the array, and check the length of the maximum mountain array for each index.
  5. Length of each mountain array will be,  dpleft[i]+dright[i]-1 , after checking condition only if dpleft[i]>1 and dpright[i]>1. 
  6. Store max_length in variable and keep updating it accordingly.
  7. Output N - max_length, that we required result.

Implementation in C++

C++ program for the above approach is given below:

#include <bits/stdc++.h>
using namespace std;
/* function  minMountainRemovals that returns minimum removals needed to make a mountain array */
int minMountainRemovals(vector<int> &a)
{
    /* Declaring two DP vectors to store the maximum result(LIS) for each indexing from left and right respectively*/
    vector<int> dpleft(a.size(), 1);
    vector<int> dpright(a.size(), 1);
    // Filling LIS for  every index from left
    for (int i = 1; i < a.size(); i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (a[i] > a[j])
            {
                dpleft[i] = max(dpleft[i], dpleft[j] + 1);
            }
        }
    }
    // Filling LIS for index from right
    for (int i = a.size() - 2; i >= 0; i--)
    {
        for (int j = a.size() - 1; j > i; j--)
        {
            if (a[i] > a[j])
            {
                dpright[i] = max(dpright[i], dpright[j] + 1);
            }
        }
    }
    int longest = 0;
    // for every index checking 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);
        }
    }
    return a.size() - longest;
}

int main()
{
    int n;
    cin >> n;
    // taking 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(N2) here. LIS is stored for each indexing in dpleft and dpright array.

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.

Optimization: The above problem can be improved by improving the time complexity of calculating LIS. This can be done in O(Nlong(N)). For an efficient approach, refer to Minimum Number of Removals to Make Mountain Array - Part 2.

FAQs

  1. What is the difference between subsequence and subarray?
    Subarray is the contiguous sequence in an array, whereas subsequence need not be contiguous, but it maintains order.
     
  2. 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. 
     
  3. 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.

Key Takeaways

In this article, we discussed the problem 'minimum number of removals to make mountain array'. We understood the problem saw its approach and algorithm. We also discussed its implementation along with time and space complexity.

Check out this problem - Longest Subarray With Sum K 

Keep practicing more and more problems to improve your coding skill, and you can also visit Coding Ninjas Studio to practice programming problems for your complete interview preparation and land your dream job.

Happy Learning Ninjas

Live masterclass