Delete array elements which are smaller than next or become smaller

Given an array arr[] and a number k. The task is to delete k elements which are smaller than next element (i.e., we delete arr[i] if arr[i] < arr[i+1]) or become smaller than next because next element is deleted.

Examples:

Input       : arr[] = { 3, 100, 1 }
k = 1
Output      : 100, 1
Explanation : arr < arr means 3 is less than
100, so delete 3

Input       : arr[] = {20, 10, 25, 30, 40}
k = 2
Output      : 25 30 40
Explanation : First we delete 10 because it follows
arr[i] < arr[i+1]. Then we delete 20
because 25 is moved next to it and it
also starts following the condition.

Input       : arr[] = { 23, 45, 11, 77, 18}
k = 3
Output      : 77, 18
Explanation : We delete 23, 45 and 11 as they follow
the condition arr[i] < arr[i+1]

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: Stack is used to solving this problem. First we push arr in stack S and then initialize count as 0, then after traverse a loop from 1 to n and then we check that s.top() > arr[i] if condition is true then we pop the element from stack and increase the count if count == k then we stop the loop and then store the value of stack in another array and then print that array.

C++

 // C++ program to delete elements from array. #include using namespace std;    // Function for deleting k elements void deleteElements(int arr[], int n, int k) {      // Create a stack and push arr     stack s;     s.push(arr);        int count = 0;            // traversing a loop from i = 1 to n     for (int i=1; i v(m); // Size of vector is m     while (!s.empty()) {                    // push element from stack to vector v         v[--m] = s.top();         s.pop();     }            // printing result     for (auto x : v)         cout << x << " ";                cout << endl; }    // Driver code int main() {     int n = 5, k = 2;     int arr[] = {20, 10, 25, 30, 40};      deleteElements(arr, n, k);     return 0; }

Java

 import java.util.*;    //Java program to delete elements from array. class GFG {    // Function for deleting k elements     static void deleteElements(int arr[], int n, int k) {         // Create a stack and push arr         Stack s = new Stack<>();         s.push(arr);            int count = 0;            // traversing a loop from i = 1 to n         for (int i = 1; i < n; i++) {                // condition for deleting an element             while (!s.empty() && s.peek() < arr[i]                     && count < k) {                 s.pop();                 count++;             }                s.push(arr[i]);         }            // Putting elements of stack in a vector         // from end to begin.         int m = s.size();         Integer[] v = new Integer[m]; // Size of vector is m         while (!s.empty()) {                // push element from stack to vector v             v[--m] = s.peek();             s.pop();         }            // printing result         for (Integer x : v) {             System.out.print(x + " ");         };            System.out.println("");     }    // Driver code     public static void main(String[] args) {         int n = 5, k = 2;         int arr[] = {20, 10, 25, 30, 40};         deleteElements(arr, n, k);     } } // This code is contributed by PrinciRaj1992

Python3

 # Function to delete elements def deleteElements(arr, n, k):            # create an empty stack st     st = []     st.append(arr)            # index to mantain the top      # of the stack     top = 0     count = 0        for i in range(1, n):                    # pop till the present element          # is greater than stack's top         # element         while(len(st) != 0 and count < k                    and st[top] < arr[i]):             st.pop()             count += 1             top -= 1            st.append(arr[i])         top += 1        # print the remaining elements     for i in range(0, len(st)):         print(st[i], " ", end="")    # Driver code k = 2 arr = [20, 10, 25, 30, 40]  deleteElements(arr, len(arr), k)    # This code is contributed by himan085.

/div>

C#

 // C# program to delete elements from array. using System; using System.Collections.Generic;    class GFG {        // Function for deleting k elements     static void deleteElements(int []arr, int n, int k)      {         // Create a stack and push arr         Stack s = new Stack();         s.Push(arr);            int count = 0;            // traversing a loop from i = 1 to n         for (int i = 1; i < n; i++)         {                // condition for deleting an element             while (s.Count != 0 && s.Peek() < arr[i]                     && count < k)              {                 s.Pop();                 count++;             }                s.Push(arr[i]);         }            // Putting elements of stack in a vector         // from end to begin.         int m = s.Count;         int[] v = new int[m]; // Size of vector is m         while (s.Count != 0)          {                // push element from stack to vector v             v[--m] = s.Peek();             s.Pop();         }            // printing result         foreach (int x in v)          {             Console.Write(x + " ");         };            Console.Write("");     }        // Driver code     public static void Main()      {         int n = 5, k = 2;         int []arr = {20, 10, 25, 30, 40};         deleteElements(arr, n, k);     } }    // This code is contributed by 29AjayKumar

Output:

25 30 40