Sorting: Given an array, you need to remove the elements to make the array as sorted.

Problem Statement:

You are given an array, you need to remove the elements form the array to make the array as sorted.

Example:

Input: arr = {1, 2, 4, 3, 6, 5, 8}
Output: arr = {1, 2, 4, 6, 8}

Solution Explanation:

Simple solution is to traverse the array and check for every element.

If the element is greater or equal to the previous element, add this element into the array, else skip this element and move to next element.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


void solution(int arr[], int n)
{


    int temp[n];
    int count = 1;

    temp[0] = arr[0];

    for (int i = 1; i < n; i++) 
    {
        if (temp[count - 1] <= arr[i]) 
        {
            temp[count] = arr[i];
            count++;
        }
    }

    for (int i = 0; i < count; i++)
        cout << temp[i] << " ";
}

int main()
{
    int arr[] = { 1, 2, 4, 3, 6, 5, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    solution(arr, n);

    return 0;
}

Output

1 2 4 6 8