Stack Sorting

Sort a stack in ascending order (with biggest terms on top).

You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure (e.g. array).

Example:

Given stack = [4, 2, 3, 1

return: [4, 3, 2, 1

Challenge:

O(n^2)

Solution:

We can create an additional stack and transfer data from original stack to the additional one. During this process, we could find the minimum value, and we push it back to original stack before pushing other data back. The solution is similar to insertion sort. O(n^2) Space: O(n)

Code:

public class Solution {
    public void stackSorting(Stack<Integer> stack) {
        if (stack == null || stack.size() == 0) {
            return;
        }
        Stack<Integer> st = new Stack<>();
        int n = stack.size();
        for (int i = 0; i < n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = i; j < n; j++) {
                int num = stack.pop();
                min = Math.min(min, num);
                st.push(num);
            }
            stack.push(min);
            boolean skipped = false;
            for (int j = i; j < n; j++) {
                int num = st.pop();
                if (!skipped && min == num) {
                    skipped = true;
                    continue;
                }
                stack.push(num);
            }
        }
    }
}