{"id":9627,"date":"2022-09-12T07:02:33","date_gmt":"2022-09-12T07:02:33","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9627"},"modified":"2022-10-03T04:01:41","modified_gmt":"2022-10-03T04:01:41","slug":"delete-array-elements-which-are-smaller-than-next-or-become-smaller","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/delete-array-elements-which-are-smaller-than-next-or-become-smaller\/","title":{"rendered":"Delete Array Elements Which Are Smaller Than Next Or Become Smaller"},"content":{"rendered":"

\"\"<\/p>\n

Problem statement<\/h3>\n

Given an array<\/a> 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 . <\/p>\n

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 . <\/p>\n

Examples :<\/strong><\/p>\n

Sample input :<\/strong> [ 12 , 23 , 11 , 3 ,10 ]
\nSample output :<\/strong> [23 , 11 , 10 ]<\/p>\n

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 .<\/p>\n

Sample input : [ 45 , 15 , 13 , 10 , 15 , 10 ]
\nSample output: [ 45 , 15 , 15 , 10 ]<\/p>\n

Explanation :
\n[ 45 , 15 , 13 , 10 , 15 , 10 ] => [ 45 , 15 , 13 , 15 , 10 ] => [ 45 , 15 , 15 , 10 ]<\/p>\n

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 .<\/p>\n

Approach<\/h3>\n

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 . <\/p>\n

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.<\/p>\n

\"\"<\/p>\n

Algorithm<\/h3>\n
    \n
  1. Create a monotonic stack which is decreasing <\/li>\n
  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 <\/li>\n
  3. At the end of traversal , we will have our monotonically decreasing stack . <\/li>\n
  4. Pop all elements from the stack and store it into an array from right to left <\/li>\n
  5. This is our required final array <\/li>\n<\/ol>\n

    Dry run for the above algorithm<\/h3>\n

    \"\"<\/p>\n

    C++ Implementation<\/h3>\n\t\t\t\t\t\t