Given an array arr[] consisting of N integers???, the task is to find the minimum number of array elements required to be removed to make the given array a mountain array.
A mountain array has the following properties:
- Length of the array ? 3.
- There exists some index i (0-based indexing) with 0 < i < N – 1 such that:
- arr[0] < arr[1] < … < arr[i – 1] < arr[i]
- arr[i] > arr[i + 1] > … > arr[arr.length – 1].
Examples:
Input: arr[] = {1, 3, 1}
Output: 0
Explanation: The array itself is a mountain array. Therefore, no removal is required.Input: arr[] = {2, 1, 1, 5, 6, 2, 3, 1}
Output: 3
Explanation: Removing arr[0], arr[1] and arr[5] modifies arr[] to {1, 5, 6, 3, 1}, which is a mountain array.
Approach 1:
The idea is to solve this problem using the Bottom-Up Dynamic Programming approach. Follow the steps below to solve the problem:
- If the length of the given array is less than 3, then the array cannot be converted to a mountain array.
- Otherwise, traverse the array and for every ith element (0 < i < N), find the length of increasing subsequence in the subarrays {arr[0], …, arr[i – 1]} and store it in an array, say leftIncreasing[].
- Similarly, find the length of the increasing subsequence in the subarray {arr[i+1], …., arr[N-1]} for every ith element (0 < i < N), and store it in an array, say rightIncreasing[].
- Find the index i (0 < i < N) which satisfies the following conditions:
- The first compulsory condition is the peak condition, which is leftIncreasing[i] > 0 and rightIncreasing[i] > 0.
- Among all indices, If leftIncreasing[i] + rightIncreasing[i] is the maximum, that index is the peak of the mountain array, say X.
- Return the result as N – (X + 1), adding one to bring the array index to length.
Illustration:
Consider the array arr[] = {4, 3, 6, 4, 5}
Therefore, leftIncreasing[] = {0, 0, 1, 1, 2} & rightIncreasing[] = {2, 1, 1, 0, 0}.
There is only one index i = 2 (0-based indexing), for which leftIncreasing[2] > 0 and rightIncreasing[2] > 0.
Therefore, X = leftIncreasing[2] + rightIncreasing[2] = 2.
Therefore, the required answer = N – (X + 1) = 5 – (2 + 3)= 2.
One of the possible solutions could be {4, 6, 5} i.e. removing 3 (arr[1]) and 4(arr[3]).
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Utility function to count array// elements required to be removed// to make array a mountain arrayint minRemovalsUtil(int arr[], int n){ int result = 0; if (n < 3) { return -1; } // Stores length of increasing // subsequence from [0, i-1] int leftIncreasing[n] = {0}; // Stores length of increasing // subsequence from [i + 1, n - 1] int rightIncreasing[n] = {0}; // Iterate for each position up to // N - 1 to find the length of subsequence for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { // If j is less than i, then // i-th position has leftIncreasing[j] // + 1 lesser elements including itself if (arr[j] < arr[i]) { // Check if it is the maximum // obtained so far leftIncreasing[i] = max(leftIncreasing[i], leftIncreasing[j] + 1); } } } // Search for increasing subsequence from right for (int i = n - 2; i >= 0; i--) { for (int j = n - 1; j > i; j--) { if (arr[j] < arr[i]) { rightIncreasing[i] = max(rightIncreasing[i], rightIncreasing[j] + 1); } } } // Find the position following the peak // condition and have maximum leftIncreasing[i] // + rightIncreasing[i] for (int i = 0; i < n; i++) { if (leftIncreasing[i] != 0 && rightIncreasing[i] != 0) { result = max(result, leftIncreasing[i] + rightIncreasing[i]); } } return n - (result + 1);}// Function to count elements to be// removed to make array a mountain arrayvoid minRemovals(int arr[], int n){ int ans = minRemovalsUtil(arr, n); // Print the answer cout << ans;}// Driver Codeint main(){ // Given array int arr[] = { 2, 1, 1, 5, 6, 2, 3, 1 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call minRemovals(arr, n); return 0;}// This code is contributed by Dharanendra L V |
Java
// Java program of the above approachimport java.io.*;import java.util.*;class GFG { // Utility function to count array // elements required to be removed // to make array a mountain array public static int minRemovalsUtil( int[] arr) { int result = 0; if (arr.length < 3) { return -1; } // Stores length of increasing // subsequence from [0, i-1] int[] leftIncreasing = new int[arr.length]; // Stores length of increasing // subsequence from [i + 1, n - 1] int[] rightIncreasing = new int[arr.length]; // Iterate for each position up to // N - 1 to find the length of subsequence for (int i = 1; i < arr.length; i++) { for (int j = 0; j < i; j++) { // If j is less than i, then // i-th position has leftIncreasing[j] // + 1 lesser elements including itself if (arr[j] < arr[i]) { // Check if it is the maximum // obtained so far leftIncreasing[i] = Math.max( leftIncreasing[i], leftIncreasing[j] + 1); } } } // Search for increasing subsequence from right for (int i = arr.length - 2; i >= 0; i--) { for (int j = arr.length - 1; j > i; j--) { if (arr[j] < arr[i]) { rightIncreasing[i] = Math.max(rightIncreasing[i], rightIncreasing[j] + 1); } } } // Find the position following the peak // condition and have maximum leftIncreasing[i] // + rightIncreasing[i] for (int i = 0; i < arr.length; i++) { if (leftIncreasing[i] != 0 && rightIncreasing[i] != 0) { result = Math.max( result, leftIncreasing[i] + rightIncreasing[i]); } } return arr.length - (result + 1); } // Function to count elements to be // removed to make array a mountain array public static void minRemovals(int[] arr) { int ans = minRemovalsUtil(arr); // Print the answer System.out.println(ans); } // Driver Code public static void main(String[] args) { // Given array int[] arr = { 2, 1, 1, 5, 6, 2, 3, 1 }; // Function Call minRemovals(arr); }} |
Python3
# Python3 program of the above approach# Utility function to count array# elements required to be removed# to make array a mountain arraydef minRemovalsUtil(arr): result = 0 if (len(arr) < 3): return -1 # Stores length of increasing # subsequence from [0, i-1] leftIncreasing = [0] * len(arr) # Stores length of increasing # subsequence from [i + 1, n - 1] rightIncreasing = [0] * len(arr) # Iterate for each position up to # N - 1 to find the length of subsequence for i in range(1, len(arr)): for j in range(i): # If j is less than i, then # i-th position has leftIncreasing[j] # + 1 lesser elements including itself if (arr[j] < arr[i]): # Check if it is the maximum # obtained so far leftIncreasing[i] = max(leftIncreasing[i], leftIncreasing[j] + 1); # Search for increasing subsequence from right for i in range(len(arr) - 2 , -1, -1): j = len(arr) - 1 while j > i: if (arr[j] < arr[i]) : rightIncreasing[i] = max(rightIncreasing[i], rightIncreasing[j] + 1) j -= 1 # Find the position following the peak # condition and have maximum leftIncreasing[i] # + rightIncreasing[i] for i in range(len(arr)): if (leftIncreasing[i] != 0 and rightIncreasing[i] != 0): result = max(result, leftIncreasing[i] + rightIncreasing[i]); return len(arr) - (result + 1)# Function to count elements to be# removed to make array a mountain arraydef minRemovals(arr): ans = minRemovalsUtil(arr) # Print the answer print(ans)# Driver Codeif __name__ == "__main__" : # Given array arr = [ 2, 1, 1, 5, 6, 2, 3, 1 ] # Function Call minRemovals(arr) # This code is contributed by AnkThon |
C#
// C# program of the above approachusing System;class GFG{ // Utility function to count array // elements required to be removed // to make array a mountain array public static int minRemovalsUtil(int[] arr) { int result = 0; if (arr.Length < 3) { return -1; } // Stores length of increasing // subsequence from [0, i-1] int[] leftIncreasing = new int[arr.Length]; // Stores length of increasing // subsequence from [i + 1, n - 1] int[] rightIncreasing = new int[arr.Length]; // Iterate for each position up to // N - 1 to find the length of subsequence for (int i = 1; i < arr.Length; i++) { for (int j = 0; j < i; j++) { // If j is less than i, then // i-th position has leftIncreasing[j] // + 1 lesser elements including itself if (arr[j] < arr[i]) { // Check if it is the maximum // obtained so far leftIncreasing[i] = Math.Max( leftIncreasing[i], leftIncreasing[j] + 1); } } } // Search for increasing subsequence from right for (int i = arr.Length - 2; i >= 0; i--) { for (int j = arr.Length - 1; j > i; j--) { if (arr[j] < arr[i]) { rightIncreasing[i] = Math.Max(rightIncreasing[i], rightIncreasing[j] + 1); } } } // Find the position following the peak // condition and have maximum leftIncreasing[i] // + rightIncreasing[i] for (int i = 0; i < arr.Length; i++) { if (leftIncreasing[i] != 0 && rightIncreasing[i] != 0) { result = Math.Max(result, leftIncreasing[i] + rightIncreasing[i]); } } return arr.Length - (result + 1); } // Function to count elements to be // removed to make array a mountain array public static void minRemovals(int[] arr) { int ans = minRemovalsUtil(arr); // Print the answer Console.WriteLine(ans); } // Driver Code public static void Main(String[] args) { // Given array int[] arr = {2, 1, 1, 5, 6, 2, 3, 1}; // Function Call minRemovals(arr); }} // This code is contributed by shikhasingrajput. |
Javascript
<script>// Javascript program of the above approach// Utility function to count array// elements required to be removed// to make array a mountain arrayfunction minRemovalsUtil(arr, n){ var result = 0; if (n < 3) { return -1; } // Stores length of increasing // subsequence from [0, i-1] var leftIncreasing = Array(n).fill(0); // Stores length of increasing // subsequence from [i + 1, n - 1] var rightIncreasing = Array(n).fill(0); // Iterate for each position up to // N - 1 to find the length of subsequence for (var i = 1; i < n; i++) { for (var j = 0; j < i; j++) { // If j is less than i, then // i-th position has leftIncreasing[j] // + 1 lesser elements including itself if (arr[j] < arr[i]) { // Check if it is the maximum // obtained so far leftIncreasing[i] = Math.max(leftIncreasing[i], leftIncreasing[j] + 1); } } } // Search for increasing subsequence from right for (var i = n - 2; i >= 0; i--) { for (var j = n - 1; j > i; j--) { if (arr[j] < arr[i]) { rightIncreasing[i] = Math.max(rightIncreasing[i], rightIncreasing[j] + 1); } } } // Find the position following the peak // condition and have maximum leftIncreasing[i] // + rightIncreasing[i] for (var i = 0; i < n; i++) { if (leftIncreasing[i] != 0 && rightIncreasing[i] != 0) { result = Math.max(result, leftIncreasing[i] + rightIncreasing[i]); } } return n - (result + 1);}// Function to count elements to be// removed to make array a mountain arrayfunction minRemovals(arr, n){ var ans = minRemovalsUtil(arr, n); // Print the answer document.write( ans);}// Driver Code// Given arrayvar arr = [2, 1, 1, 5, 6, 2, 3, 1];var n = arr.length; // Function CallminRemovals(arr, n);</script> |
Output
3
Time Complexity: O(N2), where N is the number of elements in the array
In the worst case every time we have to compare with all previous elements again.
Auxiliary Space: O(N)
For the left and right increasing array
Approach 2 : (Efficient Code)
The idea is same but by doing a slight change in the previous code we can reduce the redundant work.
The algorithm is basically works on finding the largest bitonic subsequence and after finding it subtract from the total length of the array. That will be the required answer. Below explanation is for the following.
We were making the left increasing and right increasing subsequence array and for each we are doing the same work twice. That can be done by a single function and reverse the result to our need., i.e. a slight observation upon the current scenario is, we basically need a longest increasing subsequence (LIS) and longest decreasing subsequence (LDS). And taking both of them in right direction.
For understanding it, if given array is [2 1 1 5 6 2 3 1] then the LIS array would look something like, [1 1 1 2 3 2 3 1] and if we would find the LDS array that would look like [2 1 1 3 3 2 2 1]. It can be easily achieved by the LIS function by passing the reversed array.
Below is the implementation of the algorithm :
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// The LIS function will return the LIS of passed arrayvector<int> giveLIS(vector<int>& nums){ int n = nums.size(); vector<int> lis(n, 1); for (int i = 1; i < n; i++) { int canAns = 1; for (int j = i - 1; j >= 0; j--) { if (nums[j] < nums[i]) canAns = max(canAns, lis[j] + 1); } lis[i] = canAns; } return lis;}void minRemovals(vector<int>& nums, int n){ vector<int> lis = giveLIS(nums); // find the lds using lis by just reversing reverse(nums.begin(), nums.end()); vector<int> lds = giveLIS(nums); reverse(lds.begin(), lds.end()); int maxi = 0; // ignoring the edge elements for (int i = 0; i < n; i++) { // it can't be taken as we don't want the mountain // to have a steep if (lis[i] == 1 or lds[i] == 1) continue; maxi = max(maxi, lis[i] + lds[i] - 1); } // maxi is holding the length of largest bitonic subseq // i.e. that the largest length of mountain possible is // 'maxi' so the minimum number of points removal is // "length - maxi" int ans = (n - maxi); // Print the answer cout << ans;}int main(){ // Given array vector<int> arr = { 2, 1, 1, 5, 6, 2, 3, 1 }; int n = arr.size(); // Function call minRemovals(arr, n); return 0;} |
Java
import java.util.*;import java.io.*;// Java program for the above approachclass GFG{ // The LIS function will return the LIS of passed array static ArrayList<Integer> giveLIS(ArrayList<Integer> nums) { int n = nums.size(); ArrayList<Integer> lis = new ArrayList<Integer>(); for(int i = 0 ; i < n ; i++){ lis.add(1); } for (int i = 1 ; i < n ; i++) { int canAns = 1; for (int j = i - 1 ; j >= 0 ; j--) { if (nums.get(j) < nums.get(i)) canAns = Math.max(canAns, lis.get(j) + 1); } lis.set(i, canAns); } return lis; } static void minRemovals(ArrayList<Integer> nums, int n) { ArrayList<Integer> lis = giveLIS(nums); // find the lds using lis by just reversing Collections.reverse(nums); ArrayList<Integer> lds = giveLIS(nums); Collections.reverse(lds); int maxi = 0; // ignoring the edge elements for (int i = 0 ; i < n ; i++) { // it can't be taken as we don't want the mountain // to have a steep if (lis.get(i) == 1 || lds.get(i) == 1) continue; maxi = Math.max(maxi, lis.get(i) + lds.get(i) - 1); } // maxi is holding the length of largest bitonic subseq // i.e. that the largest length of mountain possible is // 'maxi' so the minimum number of points removal is // "length - maxi" int ans = (n - maxi); // Print the answer System.out.println(ans); } public static void main(String args[]) { // Given array ArrayList<Integer> arr = new ArrayList<Integer>( List.of( 2, 1, 1, 5, 6, 2, 3, 1 ) ); int n = arr.size(); // Function call minRemovals(arr, n); }}// This code is contributed by subhamgoyal2014. |
Python3
# Python3 code for the above approachfrom typing import List# The LIS function will return the LIS of passed arraydef giveLIS(nums: List[int]) -> List[int]: n = len(nums) lis = [1] * n # iterating through the array for i in range(1, n): canAns = 1 # iterating through the array in reverse for j in range(i - 1, -1, -1): if nums[j] < nums[i]: canAns = max(canAns, lis[j] + 1) lis[i] = canAns return lisdef minRemovals(nums: List[int], n: int): # find the LIS lis = giveLIS(nums) # find the LDS by reversing the array and calling the LIS function nums.reverse() lds = giveLIS(nums) nums.reverse() lds.reverse() maxi = 0 # ignoring the edge elements for i in range(n): # it can't be taken as we don't want the mountain # to have a steep if lis[i] == 1 or lds[i] == 1: continue maxi = max(maxi, lis[i] + lds[i] - 1) # maxi is holding the length of largest bitonic subseq # i.e. that the largest length of mountain possible is # 'maxi' so the minimum number of points removal is # "length - maxi" ans = (n - maxi) # Print the answer print(ans)# Given arrayarr = [2, 1, 1, 5, 6, 2, 3, 1]n = len(arr)# Function callminRemovals(arr, n)# This code is contributed by lokeshpotta20. |
C#
// C# program to implement above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{ // The LIS function will return the LIS of passed array static List<int> giveLIS(List<int> nums) { int n = nums.Count; List<int> lis = new List<int>(); for(int i = 0 ; i < n ; i++){ lis.Add(1); } for (int i = 1 ; i < n ; i++) { int canAns = 1; for (int j = i - 1 ; j >= 0 ; j--) { if (nums[j] < nums[i]) canAns = Math.Max(canAns, lis[j] + 1); } lis[i] = canAns; } return lis; } static void minRemovals(List<int> nums, int n) { List<int> lis = giveLIS(nums); // find the lds using lis by just reversing nums.Reverse(); List<int> lds = giveLIS(nums); lds.Reverse(); int maxi = 0; // ignoring the edge elements for (int i = 0 ; i < n ; i++) { // it can't be taken as we don't want the mountain // to have a steep if (lis[i] == 1 || lds[i] == 1) continue; maxi = Math.Max(maxi, lis[i] + lds[i] - 1); } // maxi is holding the length of largest bitonic subseq // i.e. that the largest length of mountain possible is // 'maxi' so the minimum number of points removal is // "length - maxi" int ans = (n - maxi); // Print the answer Console.WriteLine(ans); } // Driver code public static void Main(string[] args){ // Given array List<int> arr = new List<int>{2, 1, 1, 5, 6, 2, 3, 1}; int n = arr.Count; // Function call minRemovals(arr, n); }}// This code is contributed by entertain2022. |
Javascript
// Javascript code for the above approachfunction giveLIS(nums) { let n = nums.length; let lis = new Array(n).fill(1); for (let i = 1; i < n; i++) { let canAns = 1; for (let j = i - 1; j >= 0; j--) { if (nums[j] < nums[i]) canAns = Math.max(canAns, lis[j] + 1); } lis[i] = canAns; } return lis;}function minRemovals(nums) { let lis = giveLIS(nums); // find the lds using lis by just reversing nums.reverse(); let lds = giveLIS(nums); lds.reverse(); let maxi = 0; // ignoring the edge elements for (let i = 0; i < nums.length; i++) { // it can't be taken as we don't want the mountain // to have a steep if (lis[i] === 1 || lds[i] === 1) continue; maxi = Math.max(maxi, lis[i] + lds[i] - 1); } // maxi is holding the length of largest bitonic subseq // i.e. that the largest length of mountain possible is // 'maxi' so the minimum number of points removal is // "length - maxi" let ans = (nums.length - maxi); // Print the answer document.write(ans);}let arr = [ 2, 1, 1, 5, 6, 2, 3, 1 ];minRemovals(arr);// This code is contributed by ik_9 |
Output
3
Time Complexity: O(N^2), where N is the number of elements in the array
In the worst case every time we have to compare with all previous elements again.
Auxiliary Space: O(N)
For the LIS and LDS array we are making to calculate
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
