Given an array A of N non-negative integers, the task is to compute the minimum number of elements to be deleted so, that the following conditions hold:
- The elements are in non-decreasing order. (Formally, for each i (1 ≤ i ≤ N-1), the condition Ai+1 >= Ai should hold.)
- The difference between adjacent elements should be in non-decreasing order. (Formally, for each i (2 ≤ i ≤ N-1), the condition Ai-Ai-1 ≤ Ai+1-Ai should hold.)
Examples:
Input: A = {1, 4, 5, 7, 20, 21}
Output:
2
Explanation: By deleting 5 and 21, the array {1, 4, 7, 20} is obtained. Here the elements are in non-decreasing order and the difference between adjacent elements are 3, 3, 13 which are in non-decreasing order.Input: A = {3, 2}
Output:
1
Explanation: The original array doesn’t satisfy the first condition. Hence, either of the elements can be deleted to get an array with a single element.
Naive Approach: The naive approach is to generate all subsets of the given array and check whether any of the subsets satisfies the condition. If it does, check how many elements have been deleted to get that subset and, then, take the minimum.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function for finding minimum deletions so that the array// becomes non decreasing and the difference between adjacent// elements also becomes non decreasingint minimumDeletions(int A[], int N){ // initialize answer to a large value int ans = INT_MAX; // generating all subsets for (int i = 1; i < (1 << N); i++) { vector<int> temp; for (int j = 0; j < N; j++) { if ((i & (1 << j)) != 0) { temp.push_back(A[j]); } } int flag = 0; // checking the first condition for (int j = 1; j < temp.size(); j++) if (temp[j] < temp[j - 1]) flag = 1; // checking the second condition for (int j = 1; j < temp.size() - 1; j++) if (temp[j] - temp[j - 1] > temp[j + 1] - temp[j]) flag = 1; // if both conditions are satisfied consider the // answer for minimum if (flag == 0) { ans = min(ans, N - (int)temp.size()); } } return ans;}// Driver codeint main(){ // Input int A[] = { 1, 4, 5, 7, 20, 21 }; int N = sizeof(A) / sizeof(A[0]); // Function call cout << minimumDeletions(A, N) << endl; return 0;} |
Java
// Java program for the above approachimport java.util.ArrayList;class GFG{// Function for finding minimum deletions so that the array// becomes non decreasing and the difference between adjacent// elements also becomes non decreasingpublic static int minimumDeletions(int A[], int N){ // initialize answer to a large value int ans = Integer.MAX_VALUE; // generating all subsets for (int i = 1; i < (1 << N); i++) { ArrayList<Integer> temp = new ArrayList<Integer>(); for (int j = 0; j < N; j++) { if ((i & (1 << j)) != 0) { temp.add(A[j]); } } int flag = 0; // checking the first condition for (int j = 1; j < temp.size(); j++) if (temp.get(j) < temp.get(j - 1)) flag = 1; // checking the second condition for (int j = 1; j < temp.size() - 1; j++) if (temp.get(j) - temp.get(j - 1) > temp.get(j + 1) - temp.get(j)) flag = 1; // if both conditions are satisfied consider the // answer for minimum if (flag == 0) { ans = Math.min(ans, N - (int)temp.size()); } } return ans;}// Driver codepublic static void main(String args[]){ // Input int A[] = { 1, 4, 5, 7, 20, 21 }; int N = A.length; // Function call System.out.println(minimumDeletions(A, N));}}// This code is contributed by saurabh_jaiswal. |
Python3
# Python program for the above approach# Function for finding minimum deletions so that the array# becomes non decreasing and the difference between adjacent# elements also becomes non decreasingdef minimumDeletions(A, N): # initialize answer to a large value ans = 10**8 # generating all subsets for i in range(1,(1<<N)): temp = [] for j in range(N): if ((i & (1 << j)) != 0): temp.append(A[j]) flag = 0 # checking the first condition for j in range(1,len(temp)): if (temp[j] < temp[j - 1]): flag = 1 # checking the second condition for j in range(1,len(temp)-1): if (temp[j] - temp[j - 1]> temp[j + 1] - temp[j]): flag = 1 # if both conditions are satisfied consider the # answer for minimum if (flag == 0): ans = min(ans, N - len(temp)) return ans # Driver codeif __name__ == '__main__': # Input A= [1, 4, 5, 7, 20, 21] N = len(A) # Function call print (minimumDeletions(A, N))# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function for finding minimum deletions so that the array// becomes non decreasing and the difference between adjacent// elements also becomes non decreasingstatic int minimumDeletions(int []A, int N){ // initialize answer to a large value int ans = Int32.MaxValue; // generating all subsets for (int i = 1; i < (1 << N); i++) { List<int> temp = new List<int>(); for (int j = 0; j < N; j++) { if ((i & (1 << j)) != 0) { temp.Add(A[j]); } } int flag = 0; // checking the first condition for (int j = 1; j < temp.Count; j++) if (temp[j] < temp[j - 1]) flag = 1; // checking the second condition for (int j = 1; j < temp.Count - 1; j++) if (temp[j] - temp[j - 1] > temp[j + 1] - temp[j]) flag = 1; // if both conditions are satisfied consider the // answer for minimum if (flag == 0) { ans = Math.Min(ans, N - temp.Count); } } return ans;}// Driver codepublic static void Main(){ // Input int []A = { 1, 4, 5, 7, 20, 21 }; int N = A.Length; // Function call Console.Write(minimumDeletions(A, N));}}// This code is contributed by ipg2016107. |
Javascript
<script>// JavaScript program for the above approach// Function for finding minimum deletions so that the array// becomes non decreasing and the difference between adjacent// elements also becomes non decreasingfunction minimumDeletions(A, N) { // initialize answer to a large value let ans = Number.MAX_SAFE_INTEGER; // generating all subsets for (let i = 1; i < (1 << N); i++) { let temp = []; for (let j = 0; j < N; j++) { if ((i & (1 << j)) != 0) { temp.push(A[j]); } } let flag = 0; // checking the first condition for (let j = 1; j < temp.length; j++) if (temp[j] < temp[j - 1]) flag = 1; // checking the second condition for (let j = 1; j < temp.length - 1; j++) if (temp[j] - temp[j - 1] > temp[j + 1] - temp[j]) flag = 1; // if both conditions are satisfied consider the // answer for minimum if (flag == 0) { ans = Math.min(ans, N - temp.length); } } return ans;}// Driver code// Inputlet A = [1, 4, 5, 7, 20, 21];let N = A.length;// Function calldocument.write(minimumDeletions(A, N) + "<br>");</script> |
Output
2
Time Complexity: O(N*2N)
Auxiliary Space: O(N)
Efficient Approach using Dynamic programming: Instead of finding the minimum number of deletions, the problem can be solved by finding the maximum size of the subset, for which the conditions hold. Follow the steps below to solve the problem:
- Create a 2D array dp, where dp[i][j] stores the minimum number of elements to be deleted from index 1 to i, that satisfy the condition:
- A[i]-A[i-1]=A[j]
- Iterate from 0 to N-1 using i, and do the following:
- Store 1 in dp[i][0] as the size will be 1.
- Iterate from i-1 to 0 using j and do the following:
- Check if A[i] is greater than A[j]. If it is greater, do the following:
- Store A[i]-A[j] in a variable, say diff.
- Iterate from 0 to diff using k, and do the following:
- Store in dp[i] the maximum between dp[i] and dp[j][k]+1.
- Thus, the transition is:
- dp[i]=max(dp[i], dp[j][k]+1)
- Check if A[i] is greater than A[j]. If it is greater, do the following:
- Iterate from 0 to MAX using i, and store the maximum value of dp[N-1][i] in a variable, say maxSetSize.
- The answer would be N-maxSetSize.
Below is the code to implement the approach
C++
#include <bits/stdc++.h>using namespace std;// the maximum value of A[i]#define MAX 100001// Function for finding minimum deletions// so that the array becomes non-decreasing// and the difference between adjacent// elements is also non-decreasingint minimumDeletions(int A[], int N){ // initializing the dp table // and setting all values to 0 int dp[N][MAX]; for (int i = 0; i < N; i++) for (int j = 0; j < MAX; j++) dp[i][j] = 0; // Find the maximum size valid set // that can be taken and then subtract // its size from N to get // minimum number of deletions for (int i = 0; i < N; i++) { // when selecting only current element // and deleting all elements // from 0 to i-1 inclusive dp[i][0] = 1; for (int j = i - 1; j >= 0; j--) { // if this is true moving from // index j to i is possible if (A[i] >= A[j]) { int diff = A[i] - A[j]; // iterate over all elements from 0 // to diff and find the max for (int k = 0; k <= diff; k++) { dp[i] = max(dp[i], dp[j][k] + 1); } } } } // take the max set size // from dp[N-1][0] to dp[N-1][MAX] int maxSetSize = -1; for (int i = 0; i < MAX; i++) maxSetSize = max(maxSetSize, dp[N - 1][i]); return N - maxSetSize;}// Driver codeint main(){ // Input int A[] = { 1, 4, 5, 7, 20, 21 }; int N = sizeof(A) / sizeof(A[0]); // Function call cout << minimumDeletions(A, N) << endl; return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG {// the maximum value of A[i]static int MAX = 100001;// Function for finding minimum deletions// so that the array becomes non-decreasing// and the difference between adjacent// elements is also non-decreasingstatic int minimumDeletions(int A[], int N){ // initializing the dp table // and setting all values to 0 int[][] dp = new int[N][MAX]; for (int i = 0; i < N; i++) for (int j = 0; j < MAX; j++) dp[i][j] = 0; // Find the maximum size valid set // that can be taken and then subtract // its size from N to get // minimum number of deletions for (int i = 0; i < N; i++) { // when selecting only current element // and deleting all elements // from 0 to i-1 inclusive dp[i][0] = 1; for (int j = i - 1; j >= 0; j--) { // if this is true moving from // index j to i is possible if (A[i] >= A[j]) { int diff = A[i] - A[j]; // iterate over all elements from 0 // to diff and find the max for (int k = 0; k <= diff; k++) { dp[i] = Math.max(dp[i], dp[j][k] + 1); } } } } // take the max set size // from dp[N-1][0] to dp[N-1][MAX] int maxSetSize = -1; for (int i = 0; i < MAX; i++) maxSetSize = Math.max(maxSetSize, dp[N - 1][i]); return N - maxSetSize;}// Driver Codepublic static void main(String[] args){ int A[] = { 1, 4, 5, 7, 20, 21 }; int N = A.length; // Function call System.out.println(minimumDeletions(A, N));}}// This code is contributed by code_hunt. |
Python3
# The maximum value of A[i]MAX = 100001# Function for finding minimum deletions# so that the array becomes non-decreasing# and the difference between adjacent# elements is also non-decreasingdef minimumDeletions(A, N): global max # Initializing the dp table # and setting all values to 0 dp = [[0 for col in range(MAX)] for row in range(N)] for i in range(N): for j in range(MAX): dp[i][j] = 0 # Find the maximum size valid set # that can be taken and then subtract # its size from N to get # minimum number of deletions for i in range(N): # When selecting only current element # and deleting all elements # from 0 to i-1 inclusive dp[i][0] = 1 for j in range(i - 1,-1,-1): # If this is true moving from # index j to i is possible if (A[i] >= A[j]): diff = A[i] - A[j] # Iterate over all elements from 0 # to diff and find the max for k in range(diff+1): dp[i] = max(dp[i],dp[j][k] + 1) # Take the max set size # from dp[N-1][0] to dp[N-1][MAX] maxSetSize = -1 for i in range(MAX): maxSetSize = max(maxSetSize, dp[N - 1][i]) return N - maxSetSize# Driver code# InputA = [ 1, 4, 5, 7, 20, 21 ]N = len(A)# Function callprint(minimumDeletions(A, N))# This code is contributed by shinjanpatra |
C#
// C# program for the above approachusing System;class GFG{// The maximum value of A[i]static int MAX = 100001;// Function for finding minimum deletions// so that the array becomes non-decreasing// and the difference between adjacent// elements is also non-decreasingstatic int minimumDeletions(int[] A, int N){ // Initializing the dp table // and setting all values to 0 int[,] dp = new int[N, MAX]; for(int i = 0; i < N; i++) for(int j = 0; j < MAX; j++) dp[i, j] = 0; // Find the maximum size valid set // that can be taken and then subtract // its size from N to get // minimum number of deletions for(int i = 0; i < N; i++) { // When selecting only current element // and deleting all elements // from 0 to i-1 inclusive dp[i, 0] = 1; for(int j = i - 1; j >= 0; j--) { // If this is true moving from // index j to i is possible if (A[i] >= A[j]) { int diff = A[i] - A[j]; // Iterate over all elements from 0 // to diff and find the max for(int k = 0; k <= diff; k++) { dp[i, diff] = Math.Max(dp[i, diff], dp[j, k] + 1); } } } } // Take the max set size // from dp[N-1][0] to dp[N-1][MAX] int maxSetSize = -1; for(int i = 0; i < MAX; i++) maxSetSize = Math.Max(maxSetSize, dp[N - 1, i]); return N - maxSetSize;}// Driver Codepublic static void Main(){ int[] A = { 1, 4, 5, 7, 20, 21 }; int N = A.Length; // Function call Console.Write(minimumDeletions(A, N));}}// This code is contributed by sanjoy_62 |
Javascript
<script>// The maximum value of A[i]let MAX = 100001// Function for finding minimum deletions// so that the array becomes non-decreasing// and the difference between adjacent// elements is also non-decreasingfunction minimumDeletions(A, N) { // Initializing the dp table // and setting all values to 0 let dp = new Array(N).fill(0).map( () => new Array(MAX)); for(let i = 0; i < N; i++) for(let j = 0; j < MAX; j++) dp[i][j] = 0; // Find the maximum size valid set // that can be taken and then subtract // its size from N to get // minimum number of deletions for(let i = 0; i < N; i++) { // When selecting only current element // and deleting all elements // from 0 to i-1 inclusive dp[i][0] = 1; for(let j = i - 1; j >= 0; j--) { // If this is true moving from // index j to i is possible if (A[i] >= A[j]) { let diff = A[i] - A[j]; // Iterate over all elements from 0 // to diff and find the max for(let k = 0; k <= diff; k++) { dp[i] = Math.max(dp[i], dp[j][k] + 1); } } } } // Take the max set size // from dp[N-1][0] to dp[N-1][MAX] let maxSetSize = -1; for(let i = 0; i < MAX; i++) maxSetSize = Math.max(maxSetSize, dp[N - 1][i]); return N - maxSetSize;}// Driver code// Inputlet A = [ 1, 4, 5, 7, 20, 21 ];let N = A.length;// Function calldocument.write(minimumDeletions(A, N) + "<br>");// This code is contributed by gfgking</script> |
Output
2
Time complexity: O(N2*M), where M is the maximum element in A,
Auxiliary Space: O(N*M)
Efficient Approach using optimized Dynamic programming: In the above approach, the minimum from 0 to diff for each k is calculated repeatedly. To avoid this, a 2D prefix maximum array pref can be maintained where pref[i][j] stores the maximum of the size of subsets such that from 1 to i, the following condition holds:
- A[i]-A[i-1]=A[j]
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// the maximum value of A[i]#define MAX 100001// Function for finding minimum deletions// so that the array becomes non-decreasing// and the difference between adjacent// elements is also non-decreasingint minimumDeletions(int A[], int N){ // initialize the dp table // and set all values to 0 // pref[i][j] will contain min(dp[i][0], // dp[i][1], ...dp[i][j]) int dp[N][MAX]; int pref[N][MAX]; for (int i = 0; i < N; i++) { for (int j = 0; j < MAX; j++) { dp[i][j] = 0; pref[i][j] = 0; } } // find the maximum sized valid set // possible and then subtract its // size from N to get // minimum number of deletions for (int i = 0; i < N; i++) { // when selecting only the current element and // deleting all elements from 0 to i-1 inclusive dp[i][0] = 1; for (int j = i - 1; j >= 0; j--) { // if this is true, // moving from index j to i is possible if (A[i] >= A[j]) { int diff = A[i] - A[j]; // we can get min(dp[j][0], .. dp[j]) // from pref array; dp[i] = max(dp[i], pref[j] + 1); } } // construct the prefix array for this element pref[i][0] = dp[i][0]; for (int j = 1; j < MAX; j++) pref[i][j] = max(dp[i][j], pref[i][j - 1]); } // take the max set size from dp[N-1][0] to dp[N-1][MAX] int maxSetSize = -1; for (int i = 0; i < MAX; i++) maxSetSize = max(maxSetSize, dp[N - 1][i]); return N - maxSetSize;}// Driver codeint main(){ int A[] = { 1, 4, 5, 7, 20, 21 }; int N = sizeof(A) / sizeof(A[0]); // Function call cout << minimumDeletions(A, N) << endl; return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG {// the maximum value of A[i]static int MAX = 100001;// Function for finding minimum deletions// so that the array becomes non-decreasing// and the difference between adjacent// elements is also non-decreasingstatic int minimumDeletions(int A[], int N){ // initialize the dp table // and set all values to 0 // pref[i][j] will contain min(dp[i][0], // dp[i][1], ...dp[i][j]) int[][] dp = new int[N][MAX]; int[][] pref = new int[N][MAX]; for (int i = 0; i < N; i++) { for (int j = 0; j < MAX; j++) { dp[i][j] = 0; pref[i][j] = 0; } } // find the maximum sized valid set // possible and then subtract its // size from N to get // minimum number of deletions for (int i = 0; i < N; i++) { // when selecting only the current element and // deleting all elements from 0 to i-1 inclusive dp[i][0] = 1; for (int j = i - 1; j >= 0; j--) { // if this is true, // moving from index j to i is possible if (A[i] >= A[j]) { int diff = A[i] - A[j]; // we can get min(dp[j][0], .. dp[j]) // from pref array; dp[i] = Math.max(dp[i], pref[j] + 1); } } // construct the prefix array for this element pref[i][0] = dp[i][0]; for (int j = 1; j < MAX; j++) pref[i][j] = Math.max(dp[i][j], pref[i][j - 1]); } // take the max set size from dp[N-1][0] to dp[N-1][MAX] int maxSetSize = -1; for (int i = 0; i < MAX; i++) maxSetSize = Math.max(maxSetSize, dp[N - 1][i]); return N - maxSetSize;}// Driver Codepublic static void main(String[] args){ int A[] = { 1, 4, 5, 7, 20, 21 }; int N = A.length; // Function call System.out.println(minimumDeletions(A, N));}}// This code is contributed by target_2. |
Python3
# Python program for the above approach# the maximum value of A[i]MAX = 100001# Function for finding minimum deletions# so that the array becomes non-decreasing# and the difference between adjacent# elements is also non-decreasingdef minimumDeletions(A, N): # initialize the dp table # and set all values to 0 # pref[i][j] will contain min(dp[i][0], # dp[i][1], ...dp[i][j]) dp =[[0 for i in range(MAX)]for j in range(N)] pref =[[0 for i in range(MAX)]for j in range(N)] # find the maximum sized valid set # possible and then subtract its # size from N to get # minimum number of deletions for i in range(N): # when selecting only the current element and # deleting all elements from 0 to i-1 inclusive dp[i][0] = 1 for j in range(i - 1,-1,-1): # if this is true, # moving from index j to i is possible if (A[i] >= A[j]): diff = A[i] - A[j] # we can get min(dp[j][0], .. dp[j]) # from pref array; dp[i] = max(dp[i], pref[j] + 1) # construct the prefix array for this element pref[i][0] = dp[i][0] for j in range(1,MAX): pref[i][j] = max(dp[i][j], pref[i][j - 1]) # take the max set size from dp[N-1][0] to dp[N-1][MAX] maxSetSize = -1 for i in range(MAX): maxSetSize = max(maxSetSize, dp[N - 1][i]) return N - maxSetSize# Driver CodeA = [ 1, 4, 5, 7, 20, 21 ]N = len(A)# Function callprint(minimumDeletions(A, N))# This code is contributed by shinjanpatra |
C#
// C# program for the above approachusing System;class GFG {// the maximum value of A[i]static int MAX = 100001;// Function for finding minimum deletions// so that the array becomes non-decreasing// and the difference between adjacent// elements is also non-decreasingstatic int minimumDeletions(int []A, int N){ // initialize the dp table // and set all values to 0 // pref[i][j] will contain min(dp[i][0], // dp[i][1], ...dp[i][j]) int[,] dp = new int[N,MAX]; int[,] pref = new int[N,MAX]; for (int i = 0; i < N; i++) { for (int j = 0; j < MAX; j++) { dp[i,j] = 0; pref[i,j] = 0; } } // find the maximum sized valid set // possible and then subtract its // size from N to get // minimum number of deletions for (int i = 0; i < N; i++) { // when selecting only the current element and // deleting all elements from 0 to i-1 inclusive dp[i,0] = 1; for (int j = i - 1; j >= 0; j--) { // if this is true, // moving from index j to i is possible if (A[i] >= A[j]) { int diff = A[i] - A[j]; // we can get min(dp[j][0], .. dp[j]) // from pref array; dp[i,diff] = Math.Max(dp[i,diff], pref[j,diff] + 1); } } // construct the prefix array for this element pref[i,0] = dp[i,0]; for (int j = 1; j < MAX; j++) pref[i,j] = Math.Max(dp[i,j], pref[i,j - 1]); } // take the max set size from dp[N-1][0] to dp[N-1][MAX] int maxSetSize = -1; for (int i = 0; i < MAX; i++) maxSetSize = Math.Max(maxSetSize, dp[N - 1,i]); return N - maxSetSize;}// Driver Code public static void Main(String[] args){ int []A = { 1, 4, 5, 7, 20, 21 }; int N = A.Length; // Function call Console.Write(minimumDeletions(A, N));}}// This code is contributed by shivanisinghss2110 |
Javascript
<script>// JavaScript program for the above approach// the maximum value of A[i]var MAX = 100001;// Function for finding minimum deletions// so that the array becomes non-decreasing// and the difference between adjacent// elements is also non-decreasingfunction minimumDeletions(A, N){ // initialize the dp table // and set all values to 0 // pref[i][j] will contain min(dp[i][0], // dp[i][1], ...dp[i][j]) var dp = new Array(N,MAX); var pref = new Array(N,MAX); for (var i = 0; i < N; i++) { for (var j = 0; j < MAX; j++) { dp[i,j] = 0; pref[i,j] = 0; } } // find the maximum sized valid set // possible and then subtract its // size from N to get // minimum number of deletions for (var i = 0; i < N; i++) { // when selecting only the current element and // deleting all elements from 0 to i-1 inclusive dp[i,0] = 1; for (var j = i - 1; j >= 0; j--) { // if this is true, // moving from index j to i is possible if (A[i] >= A[j]) { var diff = A[i] - A[j]; // we can get min(dp[j][0], .. dp[j]) // from pref array; dp[i] = Math.max(dp[i,diff], pref[j,diff] + 1); } } // construct the prefix array for this element pref[i,0] = dp[i,0]; for (var j = 1; j < MAX; j++) pref[i,j] = Math.max(dp[i,j], pref[i,j - 1]); } // take the max set size from dp[N-1][0] to dp[N-1][MAX] var maxSetSize = -1; for (var i = 0; i < MAX; i++) maxSetSize = Math.max(maxSetSize, dp[N - 1,i]); return N - maxSetSize;}// Driver Code var A = [ 1, 4, 5, 7, 20, 21 ]; var N = A.length; // Function call document.write(minimumDeletions(A, N));// This code is contributed by shivanisinghss2110</script> |
Output
2
Time complexity: O(N*M+N2), where M is the maximum element in A,
Auxiliary Space: O(N*M)
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!
