Delete Array Elements Which Are Smaller Than Next Or Become Smaller

Last Updated on October 3, 2022 by Ria Pathak

Problem statement

Given an array of integers of size n . You have to delete every element which is smaller than the next element or become smaller than the next element because of deletion .

More formally , we have to delete arr[i] if arr[i] < arr[i+1] , we keep deleting elements recursively everytime above condition is found i.e after deletion if two adjacent elements meet the above condition then we do the deletion again .

Examples :

Sample input : [ 12 , 23 , 11 , 3 ,10 ]
Sample output : [23 , 11 , 10 ]

Explanation : 12 is smaller than 23 , so it is deleted . similarly 3 is deleted because 3 is smaller than 10 . No elements can be deleted further , so we will stop the deletion .

Sample input : [ 45 , 15 , 13 , 10 , 15 , 10 ]
Sample output: [ 45 , 15 , 15 , 10 ]

Explanation :
[ 45 , 15 , 13 , 10 , 15 , 10 ] => [ 45 , 15 , 13 , 15 , 10 ] => [ 45 , 15 , 15 , 10 ]

10 is smaller than 15 , so it is deleted . After deletion 13 and 15 become adjacent , and 13 is smaller than 15 so is also deleted . Now 15 and 15 become adjacent , but we will not delete it because we are deleting only smaller numbers , not the equal ones .

Approach

If we try to understand the problem statement and look at the examples carefully we can see that our final array will be sorted in non-increasing order ( i.e arr[i] >= arr[i+1] ) . So to solve this problem we can use the concept of monotonic decreasing stack , where the top element will be less than or equal to bottom elements . we will build this stack from the given array, the final stack will store the elements that are left after deletion .

A monotonic stack is a stack whose elements are monotonically increasing or decreasing. If the top elements of the stack are less than bottom elements , then it is called decreasing stack , else If the top elements of the stack is greater than the bottom elements , then it is called increasing stack.

Algorithm

1. Create a monotonic stack which is decreasing
2. Traverse from left to right in array , at every index pop all the elements which are smaller than current element from the stack and then push the current number
3. At the end of traversal , we will have our monotonically decreasing stack .
4. Pop all elements from the stack and store it into an array from right to left
5. This is our required final array

Dry run for the above algorithm

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

void deleteSmallerElements(int arr[],int n){
	stack<int> st;
	for(int i=0;i<n;i++){
		while(!st.empty() && st.top() < arr[i]){
			st.pop();
		}
		st.push(arr[i]);
	}
	
	int m=st.size();
	int ans[m];
	int i=m-1;
	while(!st.empty()){
		ans[i] = st.top();
		st.pop();
		i--;
	}
	cout<<"Elements after deletion : ";
	for(int i=0;i<m;i++){
		cout<<ans[i]<<" ";
	}
	cout<<endl;
}

int main() {
	int arr[]={45,15,13,10,15,10};
	int n=6;
	cout<<"Input elements : ";
	for(int i=0;i<n;i++){
		cout<<arr[i]<<" ";
	}
	cout<<endl;
	
	deleteSmallerElements(arr,n);
	
	
	return 0;
}

Time complexity : O(n)
Space complexity: O(n)

This article tried to discuss How to Delete array elements which are smaller than next or become smaller. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.