Stack: Sort a stack using recursion

Coding Interview Questions

1 min read

Problem Statement:

Sort a stack using recursion.

Solution Explanation:

Remove the top element, recursively sort the remaining elements.

Take a temp stack to store the elements greater than the popped element.

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

Code Solution

#include <iostream>
#include <stack>
using namespace std;

void solution(stack<int> &st) 
{
    
    if (st.empty()) return;
    
    int top = st.top();
    st.pop();
    
    solution(st);
    
    stack<int> tmp;
    
    while (!st.empty() && st.top()>top) 
    {
        tmp.push(st.top());
        st.pop();
    }
    
    st.push(top);
    
    while (!tmp.empty()) 
    {
        st.push(tmp.top());
        tmp.pop();
    }
}

int main(void) 
{
    stack<int> st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
    st.push(1);
    solution(st);
    
    while (!st.empty()) 
    {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;
    
    return 0;
}