Given an array arr[] of size N, the task is to find the minimum number of array elements required to be removed from the array such that the given array is converted to a bitonic array.
Examples:
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 }
Since the array elements follow an increasing order followed by a decreasing order, the required output is 3.Input: arr[] = { 1, 3, 1 }
Output: 0
Explanation:
The given array is already a bitonic array. Therefore, the required output is 3.
Approach: The problem can be solved based on the concept of the longest increasing subsequence problem. Follow the steps below to solve the problem:
- Initialize a variable, say left[], such that left[i] stores the length of the longest increasing subsequence up to the ith index.
- Initialize a variable, say right[], such that right[i] stores the length of the longest decreasing subsequence over the range [i, N].
- Traverse left[] and right[] array using variable i and find the maximum value of (left[i] + right[i] – 1) and store it in a variable, say maxLen.
- Finally, print the value of N – maxLen.
Below is the implementation of the above approach:
C++14
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to count minimum array elements// required to be removed to make an array bitonicvoid min_element_removal(int arr[], int N){ // left[i]: Stores the length // of LIS up to i-th index vector<int> left(N, 1); // right[i]: Stores the length // of decreasing subsequence // over the range [i, N] vector<int> right(N, 1); // Calculate the length of LIS // up to i-th index for (int i = 1; i < N; i++) { // Traverse the array // upto i-th index for (int j = 0; j < i; j++) { // If arr[j] is less than arr[i] if (arr[j] < arr[i]) { // Update left[i] left[i] = max(left[i], left[j] + 1); } } } // Calculate the length of decreasing // subsequence over the range [i, N] for (int i = N - 2; i >= 0; i--) { // Traverse right[] array for (int j = N - 1; j > i; j--) { // If arr[i] is greater // than arr[j] if (arr[i] > arr[j]) { // Update right[i] right[i] = max(right[i], right[j] + 1); } } } // Stores length of the // longest bitonic array int maxLen = 0; // Traverse left[] and right[] array for (int i = 1; i < N - 1; i++) { // Update maxLen maxLen = max(maxLen, left[i] + right[i] - 1); } cout << (N - maxLen) << "\n";}// Function to print minimum removals// required to make given array bitonicvoid makeBitonic(int arr[], int N){ if (N == 1) { cout << "0" << endl; return; } if (N == 2) { if (arr[0] != arr[1]) cout << "0" << endl; else cout << "1" << endl; return; } min_element_removal(arr, N);}// Driver Codeint main(){ int arr[] = { 2, 1, 1, 5, 6, 2, 3, 1 }; int N = sizeof(arr) / sizeof(arr[0]); makeBitonic(arr, N); return 0;} |
C
// C program to implement// the above approach#include <stdio.h>#define max(a,b) ((a) > (b) ? (a) : (b)) //defining max// Function to count minimum array elements// required to be removed to make an array bitonicvoid min_element_removal(int arr[], int N){ // left[i]: Stores the length // of LIS up to i-th index int left[N]; for (int i = 0; i < N; i++) left[i] = 1; // right[i]: Stores the length // of decreasing subsequence // over the range [i, N] int right[N]; for (int i = 0; i < N; i++) right[i] = 1; // Calculate the length of LIS // up to i-th index for (int i = 1; i < N; i++) { // Traverse the array // upto i-th index for (int j = 0; j < i; j++) { // If arr[j] is less than arr[i] if (arr[j] < arr[i]) { // Update left[i] left[i] = max(left[i], left[j] + 1); } } } // Calculate the length of decreasing // subsequence over the range [i, N] for (int i = N - 2; i >= 0; i--) { // Traverse right[] array for (int j = N - 1; j > i; j--) { // If arr[i] is greater // than arr[j] if (arr[i] > arr[j]) { // Update right[i] right[i] = max(right[i], right[j] + 1); } } } // Stores length of the // longest bitonic array int maxLen = 0; // Traverse left[] and right[] array for (int i = 1; i < N - 1; i++) { // Update maxLen maxLen = max(maxLen, left[i] + right[i] - 1); } printf("%d\n", (N - maxLen));}// Function to print minimum removals// required to make given array bitonicvoid makeBitonic(int arr[], int N){ if (N == 1) { printf("0\n"); return; } if (N == 2) { if (arr[0] != arr[1]) printf("0\n"); else printf("1\n"); return; } min_element_removal(arr, N);}// Driver Codeint main(){ int arr[] = { 2, 1, 1, 5, 6, 2, 3, 1 }; int N = sizeof(arr) / sizeof(arr[0]); makeBitonic(arr, N); return 0;}// This code is contributed by phalashi. |
Java
// Java program to implement// the above approachclass GFG { // Function to count minimum array elements // required to be removed to make an array bitonic static void min_element_removal(int arr[], int N) { // left[i]: Stores the length // of LIS up to i-th index int left[] = new int[N]; for(int i = 0; i < N; i++) left[i] = 1; // right[i]: Stores the length // of decreasing subsequence // over the range [i, N] int right[] = new int[N]; for(int i = 0; i < N; i++) right[i] = 1; // Calculate the length of LIS // up to i-th index for (int i = 1; i < N; i++) { // Traverse the array // upto i-th index for (int j = 0; j < i; j++) { // If arr[j] is less than arr[i] if (arr[j] < arr[i]) { // Update left[i] left[i] = Math.max(left[i], left[j] + 1); } } } // Calculate the length of decreasing // subsequence over the range [i, N] for (int i = N - 2; i >= 0; i--) { // Traverse right[] array for (int j = N - 1; j > i; j--) { // If arr[i] is greater // than arr[j] if (arr[i] > arr[j]) { // Update right[i] right[i] = Math.max(right[i], right[j] + 1); } } } // Stores length of the // longest bitonic array int maxLen = 0; // Traverse left[] and right[] array for (int i = 1; i < N - 1; i++) { // Update maxLen maxLen = Math.max(maxLen, left[i] + right[i] - 1); } System.out.println(N - maxLen); } // Function to print minimum removals // required to make given array bitonic static void makeBitonic(int arr[], int N) { if (N == 1) { System.out.println("0"); return; } if (N == 2) { if (arr[0] != arr[1]) System.out.println("0"); else System.out.println("1"); return; } min_element_removal(arr, N); } // Driver Code public static void main (String[] args) { int arr[] = { 2, 1, 1, 5, 6, 2, 3, 1 }; int N = arr.length; makeBitonic(arr, N); }}// This code is contributed by AnkitRai01 |
Python3
# Python3 program to implement# the above approach# Function to count minimum array elements# required to be removed to make an array bitonicdef min_element_removal(arr, N): # left[i]: Stores the length # of LIS up to i-th index left = [1] * N # right[i]: Stores the length # of decreasing subsequence # over the range [i, N] right = [1] * (N) #Calculate the length of LIS #up to i-th index for i in range(1, N): #Traverse the array #upto i-th index for j in range(i): #If arr[j] is less than arr[i] if (arr[j] < arr[i]): #Update left[i] left[i] = max(left[i], left[j] + 1) # Calculate the length of decreasing # subsequence over the range [i, N] for i in range(N - 2, -1, -1): # Traverse right[] array for j in range(N - 1, i, -1): # If arr[i] is greater # than arr[j] if (arr[i] > arr[j]): # Update right[i] right[i] = max(right[i], right[j] + 1) # Stores length of the # longest bitonic array maxLen = 0 # Traverse left[] and right[] array for i in range(1, N - 1): # Update maxLen maxLen = max(maxLen, left[i] + right[i] - 1) print((N - maxLen))# Function to print minimum removals# required to make given array bitonicdef makeBitonic(arr, N): if (N == 1): print("0") return if (N == 2): if (arr[0] != arr[1]): print("0") else: print("1") return min_element_removal(arr, N)# Driver Codeif __name__ == '__main__': arr=[2, 1, 1, 5, 6, 2, 3, 1] N = len(arr) makeBitonic(arr, N) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to count minimum array elements// required to be removed to make an array bitonicstatic void min_element_removal(int []arr, int N){ // left[i]: Stores the length // of LIS up to i-th index int []left = new int[N]; for(int i = 0; i < N; i++) left[i] = 1; // right[i]: Stores the length // of decreasing subsequence // over the range [i, N] int []right = new int[N]; for(int i = 0; i < N; i++) right[i] = 1; // Calculate the length of LIS // up to i-th index for(int i = 1; i < N; i++) { // Traverse the array // upto i-th index for(int j = 0; j < i; j++) { // If arr[j] is less than arr[i] if (arr[j] < arr[i]) { // Update left[i] left[i] = Math.Max(left[i], left[j] + 1); } } } // Calculate the length of decreasing // subsequence over the range [i, N] for(int i = N - 2; i >= 0; i--) { // Traverse right[] array for(int j = N - 1; j > i; j--) { // If arr[i] is greater // than arr[j] if (arr[i] > arr[j]) { // Update right[i] right[i] = Math.Max(right[i], right[j] + 1); } } } // Stores length of the // longest bitonic array int maxLen = 0; // Traverse left[] and right[] array for(int i = 1; i < N - 1; i++) { // Update maxLen maxLen = Math.Max(maxLen, left[i] + right[i] - 1); } Console.WriteLine(N - maxLen);}// Function to print minimum removals// required to make given array bitonicstatic void makeBitonic(int []arr, int N){ if (N == 1) { Console.WriteLine("0"); return; } if (N == 2) { if (arr[0] != arr[1]) Console.WriteLine("0"); else Console.WriteLine("1"); return; } min_element_removal(arr, N);}// Driver Codepublic static void Main(String[] args) { int []arr = { 2, 1, 1, 5, 6, 2, 3, 1 }; int N = arr.Length; makeBitonic(arr, N);}}// This code is contributed by AnkThon |
Javascript
<script>// Javascript program to implement// the above approach// Function to count minimum array elements// required to be removed to make an array bitonicfunction min_element_removal(arr, N){ // left[i]: Stores the length // of LIS up to i-th index var left = Array(N).fill(1); // right[i]: Stores the length // of decreasing subsequence // over the range [i, N] var right = Array(N).fill(1); // Calculate the length of LIS // up to i-th index for (var i = 1; i < N; i++) { // Traverse the array // upto i-th index for (var j = 0; j < i; j++) { // If arr[j] is less than arr[i] if (arr[j] < arr[i]) { // Update left[i] left[i] = Math.max(left[i], left[j] + 1); } } } // Calculate the length of decreasing // subsequence over the range [i, N] for (var i = N - 2; i >= 0; i--) { // Traverse right[] array for (var j = N - 1; j > i; j--) { // If arr[i] is greater // than arr[j] if (arr[i] > arr[j]) { // Update right[i] right[i] = Math.max(right[i], right[j] + 1); } } } // Stores length of the // longest bitonic array var maxLen = 0; // Traverse left[] and right[] array for (var i = 1; i < N - 1; i++) { // Update maxLen maxLen = Math.max(maxLen, left[i] + right[i] - 1); } document.write((N - maxLen) + "<br>");}// Function to print minimum removals// required to make given array bitonicfunction makeBitonic(arr, N){ if (N == 1) { document.write( "0" + "<br>"); return; } if (N == 2) { if (arr[0] != arr[1]) document.write( "0" + "<br>"); else document.write( "1" + "<br>"); return; } min_element_removal(arr, N);}// Driver Codevar arr = [2, 1, 1, 5, 6, 2, 3, 1];var N = arr.length;makeBitonic(arr, N);// This code is contributed by rutvik_56.</script> |
Output:
3
Time Complexity: O(N2)
Auxiliary Space: O(N)
Optimized Approach:
This approach has a time complexity of O(n), where n is the number of elements in the array, since it takes a single pass through the array to find the local maximum and local minimum, and it performs a constant amount of work for each iteration of the loop.
C++
#include <bits/stdc++.h>using namespace std;// Function to count minimum array elements// required to be removed to make an array bitonicvoid min_element_removal(int arr[], int N){ int l = 0, r = N-1, count = 0; while(l < r) { // find the first local maximum from the left side while(l < N-1 && arr[l] <= arr[l+1]) l++; // find the first local minimum from the right side while(r > 0 && arr[r] <= arr[r-1]) r--; // if both indices have not crossed each other, // remove the elements between them if(l < r) { l++; r--; count++; } } // print the minimum number of removals cout << count << endl;}// Driver Codeint main(){ int arr[] = { 5,7,1,3,6,2,1 }; int N = sizeof(arr) / sizeof(arr[0]); min_element_removal(arr, N); return 0;} |
Java
import java.util.*;class Main { // Function to count minimum array elements // required to be removed to make an array bitonic public static void min_element_removal(int arr[], int N) { int l = 0, r = N - 1, count = 0; while (l < r) { // find the first local maximum from the left // side while (l < N - 1 && arr[l] <= arr[l + 1]) l++; // find the first local minimum from the right // side while (r > 0 && arr[r] <= arr[r - 1]) r--; // if both indices have not crossed each other, // remove the elements between them if (l < r) { l++; r--; count++; } } // print the minimum number of removals System.out.println(count); } // Driver Code public static void main(String[] args) { int arr[] = { 5, 7, 1, 3, 6, 2, 1 }; int N = arr.length; min_element_removal(arr, N); }} |
Python3
# Function to count minimum array elements# required to be removed to make an array bitonicdef min_element_removal(arr, N): l, r, count = 0, N-1, 0 while l < r: # find the first local maximum from the left side while l < N-1 and arr[l] <= arr[l+1]: l += 1 # find the first local minimum from the right side while r > 0 and arr[r] <= arr[r-1]: r -= 1 # if both indices have not crossed each other, # remove the elements between them if l < r: l += 1 r -= 1 count += 1 # print the minimum number of removals print(count)# Driver Codearr = [5, 7, 1, 3, 6, 2, 1]N = len(arr)min_element_removal(arr, N) |
Javascript
// Function to count minimum array elements// required to be removed to make an array bitonicfunction min_element_removal(arr, N) { let l = 0, r = N-1, count = 0; while (l < r) { // find the first local maximum from the left side while (l < N-1 && arr[l] <= arr[l+1]) { l++; } // find the first local minimum from the right side while (r > 0 && arr[r] <= arr[r-1]) { r--; } // if both indices have not crossed each other, // remove the elements between them if (l < r) { l++; r--; count++; } } // print the minimum number of removals console.log(count);}// Driver Codelet arr = [5, 7, 1, 3, 6, 2, 1];let N = arr.length;min_element_removal(arr, N); |
C#
using System;class Program{ static void Main(string[] args) { int[] arr = { 5, 7, 1, 3, 6, 2, 1 }; int N = arr.Length; int l = 0, r = N - 1, count = 0; while (l < r) { // find the first local maximum from the left side while (l < N - 1 && arr[l] <= arr[l + 1]) l++; // find the first local minimum from the right side while (r > 0 && arr[r] <= arr[r - 1]) r--; // if both indices have not crossed each other, // remove the elements between them if (l < r) { l++; r--; count++; } } // print the minimum number of removals Console.WriteLine(count); }} |
Output
1
Time Complexity: O(N)
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!