Implement a method to insert an element at its bottom without using any other data structure

The problem, simply

You get a stack and a value x. Put x at the very bottom of the stack. Everything else must stay in the same order above it.

The catch: you may not use any other data structure, no second stack, no array, no list. You may only use the stack's own push, pop, peek and isEmpty, and recursion.

A story to remember it

Picture it

Examples

Way 1: the simple way

If the rules allowed a second stack, you would pour everything into it, push x, and pour it all back.

1. Pop every item from the stack into a helper stack. The helper now holds them upside down.
2. Push x onto the empty stack.
3. Pop every item from the helper back onto the stack. They land in the original order.

class Solution {
    public void insertAtBottom(Deque<Integer> stack, int x) {
        Deque<Integer> helper = new ArrayDeque<>();   // not allowed by the rules
        while (!stack.isEmpty()) helper.push(stack.pop());
        stack.push(x);
        while (!helper.isEmpty()) stack.push(helper.pop());
    }
}

How long it takes: every item is moved twice, O(n). Extra room: a helper stack of n items, O(n). It works, but it breaks the rule.

Way 2: the clever way

Let recursion be the helper. Each call holds one item in a local variable, like a friend holding one block. The waiting calls form a hidden stack, the call stack.

1. If the stack is empty, push x and return. This is the floor.
2. Otherwise pop the top item into a local variable top.
3. Call insertAtBottom(stack, x) on the smaller stack.
4. When that call returns, push top back.

class Solution {
    public void insertAtBottom(Deque<Integer> stack, int x) {
        if (stack.isEmpty()) {          // the floor: x goes here
            stack.push(x);
            return;
        }
        int top = stack.pop();          // this call holds one block
        insertAtBottom(stack, x);       // the rest of the work
        stack.push(top);                // put the block back on the way out
    }
}

How long it takes: each item is popped once and pushed once, O(n). Extra room: n + 1 calls wait on the call stack, O(n). The rule only bans data structures you build yourself; the call stack is how the language runs functions.

Watch out for

• Pushing top back before the recursive call puts it under x, which breaks the order. Recurse first, push after.
• A very tall stack can overflow the call stack. In Java that is a StackOverflowError at a depth of a few thousand to tens of thousands, depending on settings.
• The method changes the stack in place. It does not need to return anything.

What interviewers ask next

• Reverse a stack using only recursion. Pop the top, reverse the rest, then insert the popped item at the bottom with this method. That is O(n^2) time.
• Sort a stack using only recursion. Pop the top, sort the rest, then insert the item in its sorted place with a method shaped like this one, stopping when the top is not bigger.
• Insert at position k from the bottom. Same idea, but stop popping when the stack size is k instead of zero.
• Can you do it without recursion and without extra storage? Not with only push and pop. Something has to remember the popped items, and the call stack is that something.
• Is the space really "no extra data structure"? It is O(n) hidden memory. Saying that clearly is part of a good answer.

Remember this

Grown-up words: the friends holding blocks are recursive calls on the call stack, the floor is the base case, and putting blocks back on the way out is the unwinding of the recursion.