Given an array arr[] of length N, the task is to remove the minimum number of elements from the array to make it a mountain array and then print it.
Note: A mountain array is an array where there is an index i such that arr[0] < arr[1] < . . .< arr[i-1] < arr[i] > arr[i+1] > . . . > arr[N-1]. Also a mountain array must have a length greater than or equal to 3 to satisfy the above condition.
Examples:
Input: arr[] = {9, 8, 1, 7, 6, 5, 4, 3, 2, 1}
Output: 1 7 6 5 4 3 2 1
Explanation: Remove the elements 9, 8. The resultant array is the mountain array.
It is the minimum number of removals possible.Input: arr[] = {1, 1, 1};
Output: -1
Explanation: This array cannot be transformed into a mountain array
Approach: Follow the steps below to solve this problem:
- Create two arrays left and right.
- For every index i, left[i] will store the longest increasing subsequence that ends at i and right[i] will store the longest decreasing subsequence that starts from i.
- Now, find the maximum length of mountain subsequence assuming each index as the peak of the mountain.
Length of mountain subsequence having peak at i = left[i]+right[i]-1
- Find the maximum length of mountain subsequence, say max and keep track of the peak for which the maximum length is achieved.
- So, the minimum number of deletions is (N – max).
- Now print the longest increasing subsequence from starting to i and the longest decreasing subsequence from i to end of the array.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the mountain array// after minimum removalsvoid mountArray(vector<int>& arr){ int N = arr.size(); vector<int> left(N, 1), right(N, 1); for (int i = 0; i < N; ++i) { for (int j = 0; j <= i; ++j) { if (arr[j] < arr[i]) { // This means the // previous number is // smaller than the number left[i] = max(left[j] + 1, left[i]); } } } // Find the longest decreasing sequence for (int i = N - 1; i >= 0; --i) { for (int j = i; j <= N - 1; ++j) { if (arr[j] < arr[i]) { right[i] = max(right[j] + 1, right[i]); } } } int max = 0; int index = 0; for (int i = 1; i < N - 1; ++i) { if (left[i] != 1 && right[i] != 1) { if (max < (left[i] + right[i]) - 1) { index = i; max = (left[i] + right[i]) - 1; } } } // Print the longest continuous // subsequence from 0 to ith // and ith to N index vector<int> left1; left1.push_back(arr[index]); for (int i = index; i >= 0; --i) { if (arr[i] < arr[index]) { // There is possibility // either the index is // used or not if (left[i] + 1 == left[index]) { left1.push_back(arr[i]); left[index] -= 1; } } } vector<int> right1; // Starting the right for (int i = index; i < right.size(); ++i) { if (arr[index] > arr[i]) { if (right[i] + 1 == right[index]) { right1.push_back(arr[i]); right[index] -= 1; } } } if (max < 3) { cout << (-1) << "\n"; } else { // Print the first left1 array // then the right array for (int i = left1.size() - 1; i >= 0; --i) { cout << left1[i] << " "; } for (int i = 0; i < right1.size(); ++i) { cout << right1[i] << " "; } }}// Driver codeint main(){ vector<int> arr = { 9, 8, 1, 7, 6, 5, 4, 3, 2, 1 }; mountArray(arr);}// This code is contributed by Taranpreet |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to print the mountain array // after minimum removals public static void mountArray(int arr[]) { int N = arr.length; int left[] = new int[N]; int right[] = new int[N]; Arrays.fill(left, 1); Arrays.fill(right, 1); for (int i = 0; i < N; ++i) { for (int j = 0; j <= i; ++j) { if (arr[j] < arr[i]) { // This means the // previous number is // smaller than the number left[i] = Math.max(left[j] + 1, left[i]); } } } // Find the longest decreasing sequence for (int i = N - 1; i >= 0; --i) { for (int j = i; j <= N - 1; ++j) { if (arr[j] < arr[i]) { right[i] = Math.max(right[j] + 1, right[i]); } } } int max = 0; int index = 0; for (int i = 1; i < N - 1; ++i) { if (left[i] != 1 && right[i] != 1) { if (max < (left[i] + right[i]) - 1) { index = i; max = (left[i] + right[i]) - 1; } } } // Print the longest continuous // subsequence from 0 to ith // and ith to N index ArrayList<Integer> left1 = new ArrayList<Integer>(); left1.add(arr[index]); for (int i = index; i >= 0; --i) { if (arr[i] < arr[index]) { // There is possibility // either the index is // used or not if (left[i] + 1 == left[index]) { left1.add(arr[i]); left[index] -= 1; } } } ArrayList<Integer> right1 = new ArrayList<>(); // Starting the right for (int i = index; i < right.length; ++i) { if (arr[index] > arr[i]) { if (right[i] + 1 == right[index]) { right1.add(arr[i]); right[index] -= 1; } } } if (max < 3) { System.out.println(-1); } else { // Print the first left1 array // then the right array for (int i = left1.size() - 1; i >= 0; --i) { System.out.print(left1.get(i) + " "); } for (int i = 0; i < right1.size(); ++i) { System.out.print(right1.get(i) + " "); } } } // Driver code public static void main(String[] args) { int arr[] = { 9, 8, 1, 7, 6, 5, 4, 3, 2, 1 }; mountArray(arr); }} |
Python3
# python3 program for the above approach# Function to print the mountain array# after minimum removalsdef mountArray(arr): N = len(arr) left, right = [1 for _ in range(N)], [1 for _ in range(N)] for i in range(0, N): for j in range(0, i+1): if (arr[j] < arr[i]): # This means the # previous number is # smaller than the number left[i] = max(left[j] + 1, left[i]) # Find the longest decreasing sequence for i in range(N-1, -1, -1): for j in range(i, N): if (arr[j] < arr[i]): right[i] = max(right[j] + 1, right[i]) maxi = 0 index = 0 for i in range(1, N-1): if (left[i] != 1 and right[i] != 1): if (maxi < (left[i] + right[i]) - 1): index = i maxi = (left[i] + right[i]) - 1 # Print the longest continuous # subsequence from 0 to ith # and ith to N index left1 = [] left1.append(arr[index]) for i in range(index, -1, -1): if (arr[i] < arr[index]): # There is possibility # either the index is # used or not if (left[i] + 1 == left[index]): left1.append(arr[i]) left[index] -= 1 right1 = [] # Starting the right for i in range(index, len(right)): if (arr[index] > arr[i]): if (right[i] + 1 == right[index]): right1.append(arr[i]) right[index] -= 1 if (maxi < 3): print("-1") else: # Print the first left1 array # then the right array for i in range(len(left1) - 1, -1, -1): print(left1[i], end=" ") for i in range(0, len(right1)): print(right1[i], end=" ")# Driver codeif __name__ == "__main__": arr = [9, 8, 1, 7, 6, 5, 4, 3, 2, 1] mountArray(arr) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections;class GFG { // Function to print the mountain array // after minimum removals static void mountArray(int []arr) { int N = arr.Length; int []left = new int[N]; int []right = new int[N]; for(int i = 0; i < N; i++) { left[i] = 1; right[i] = 1; } for (int i = 0; i < N; ++i) { for (int j = 0; j <= i; ++j) { if (arr[j] < arr[i]) { // This means the // previous number is // smaller than the number left[i] = Math.Max(left[j] + 1, left[i]); } } } // Find the longest decreasing sequence for (int i = N - 1; i >= 0; --i) { for (int j = i; j <= N - 1; ++j) { if (arr[j] < arr[i]) { right[i] = Math.Max(right[j] + 1, right[i]); } } } int max = 0; int index = 0; for (int i = 1; i < N - 1; ++i) { if (left[i] != 1 && right[i] != 1) { if (max < (left[i] + right[i]) - 1) { index = i; max = (left[i] + right[i]) - 1; } } } // Print the longest continuous // subsequence from 0 to ith // and ith to N index ArrayList left1 = new ArrayList(); left1.Add(arr[index]); for (int i = index; i >= 0; --i) { if (arr[i] < arr[index]) { // There is possibility // either the index is // used or not if (left[i] + 1 == left[index]) { left1.Add(arr[i]); left[index] -= 1; } } } ArrayList right1 = new ArrayList(); // Starting the right for (int i = index; i < right.Length; ++i) { if (arr[index] > arr[i]) { if (right[i] + 1 == right[index]) { right1.Add(arr[i]); right[index] -= 1; } } } if (max < 3) { Console.Write(-1); } else { // Print the first left1 array // then the right array for (int i = left1.Count - 1; i >= 0; --i) { Console.Write(left1[i] + " "); } for (int i = 0; i < right1.Count; ++i) { Console.Write(right1[i] + " "); } } } // Driver code public static void Main() { int []arr = { 9, 8, 1, 7, 6, 5, 4, 3, 2, 1 }; mountArray(arr); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to print the mountain array // after minimum removals function mountArray(arr) { let N = arr.length; let left = new Array(N).fill(1); let right = new Array(N).fill(1); for (let i = 0; i < N; ++i) { for (let j = 0; j <= i; ++j) { if (arr[j] < arr[i]) { // This means the // previous number is // smaller than the number left[i] = Math.max(left[j] + 1, left[i]); } } } // Find the longest decreasing sequence for (let i = N - 1; i >= 0; --i) { for (let j = i; j <= N - 1; ++j) { if (arr[j] < arr[i]) { right[i] = Math.max(right[j] + 1, right[i]); } } } let max = 0; let index = 0; for (let i = 1; i < N - 1; ++i) { if (left[i] != 1 && right[i] != 1) { if (max < (left[i] + right[i]) - 1) { index = i; max = (left[i] + right[i]) - 1; } } } // Print the longest continuous // subsequence from 0 to ith // and ith to N index let left1 = []; left1.push(arr[index]); for (let i = index; i >= 0; --i) { if (arr[i] < arr[index]) { // There is possibility // either the index is // used or not if (left[i] + 1 == left[index]) { left1.push(arr[i]); left[index] -= 1; } } } let right1 = [] // Starting the right for (let i = index; i < right.length; ++i) { if (arr[index] > arr[i]) { if (right[i] + 1 == right[index]) { right1.push(arr[i]); right[index] -= 1; } } } if (max < 3) { document.write(-1); } else { // Print the first left1 array // then the right array for (let i = left1.length - 1; i >= 0; --i) { document.write(left1[i] + " "); } for (let i = 0; i < right1.length; ++i) { document.write(right1[i] + " "); } } } // Driver code let arr = [9, 8, 1, 7, 6, 5, 4, 3, 2, 1]; mountArray(arr); // This code is contributed by Potta Lokesh </script> |
Output
1 7 6 5 4 3 2 1
Time Complexity: O(N2)
Auxiliary Space: O(N)
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!
