42-Sort-Stack-Recursively.md

Sort Stack Recursively

Problem Link

Practice Problem

---

Pattern

• Stack
• Recursion

---

Approach

Pop one element recursively, sort the rest, then insert the popped element in sorted position.

---

Time Complexity

O(n^2)

Space Complexity

O(n)

---

Java Solution

import java.util.*;
class Solution {
    public void sortStack(Stack<Integer> stack) {
        if (stack.isEmpty()) return;
        int top = stack.pop();
        sortStack(stack);
        insertSorted(stack, top);
    }

    private void insertSorted(Stack<Integer> stack, int val) {
        if (stack.isEmpty() || stack.peek() <= val) {
            stack.push(val);
            return;
        }
        int top = stack.pop();
        insertSorted(stack, val);
        stack.push(top);
    }
}