Find the middle element of a stack

The problem, simply

Build a stack with the usual push and pop, plus two extra actions:

• findMiddle(): give back the middle item.
• deleteMiddle(): remove the middle item.

All four must take O(1) time. For n items, the middle is item number (n + 1) / 2 counted from the bottom, starting at 1. With 5 items that is the 3rd. With 4 items it is the 2nd, the lower of the two middle ones.

A story to remember it

Picture it

Examples

Way 1: the simple way

Use a normal stack. To find the middle, pop the top half into a second stack, look at the next item, then pour the half back.

1. Let k = n / 2. That is how many books sit above the middle.
2. Pop k items into a helper stack.
3. The top of the main stack is now the middle. Read it, or pop it to delete it.
4. Pour the helper stack back, so the order is the same as before.

import java.util.ArrayDeque;
import java.util.Deque;

class MiddleStackSimple {
    private final Deque<Integer> main = new ArrayDeque<>();

    void push(int x) { main.push(x); }

    int pop() {
        if (main.isEmpty()) throw new RuntimeException("stack is empty");
        return main.pop();
    }

    int findMiddle() { return reachMiddle(false); }

    int deleteMiddle() { return reachMiddle(true); }

    private int reachMiddle(boolean remove) {
        if (main.isEmpty()) throw new RuntimeException("stack is empty");
        Deque<Integer> helper = new ArrayDeque<>();
        int above = main.size() / 2;           // books above the middle
        for (int i = 0; i < above; i++) helper.push(main.pop());
        int mid = remove ? main.pop() : main.peek();
        while (!helper.isEmpty()) main.push(helper.pop());  // pour back
        return mid;
    }
}

How long it takes: push and pop are O(1), but each middle action moves half the pile twice, O(n). Extra room: the helper stack, O(n).

Way 2: the clever way

Build the stack as a chain where each box points both up and down, a doubly linked list. top is the head. Keep a bookmark mid on the middle box and a counter count. The bookmark only needs one small nudge after each change.

1. push(x): add the box on top. If count was even before the push, move mid one box up (mid = mid.prev). If the pile was empty, mid is the new box.
2. pop(): take the top box off. If count was odd before the pop, move mid one box down (mid = mid.next).
3. findMiddle(): read mid.
4. deleteMiddle(): if count is odd, the new middle is the box below; if even, the box above. Move mid there, then unhook the old middle by joining its two neighbors.

Why does parity decide? The middle is box number (n + 1) / 2 from the bottom. That number goes up by one only when n goes from even to odd.

class MiddleStack {
    private static class Node {
        int val;
        Node prev, next;               // prev is the box above, next the box below
        Node(int val) { this.val = val; }
    }

    private Node top, mid;
    private int count;

    void push(int x) {
        Node box = new Node(x);
        box.next = top;
        if (top != null) top.prev = box;
        top = box;
        if (count == 0) mid = box;
        else if (count % 2 == 0) mid = mid.prev;   // even before: middle goes up
        count++;
    }

    int pop() {
        if (count == 0) throw new RuntimeException("stack is empty");
        int val = top.val;
        if (count % 2 == 1) mid = mid.next;        // odd before: middle goes down
        top = top.next;
        if (top != null) top.prev = null;
        count--;
        return val;
    }

    int findMiddle() {
        if (count == 0) throw new RuntimeException("stack is empty");
        return mid.val;
    }

    int deleteMiddle() {
        if (count == 0) throw new RuntimeException("stack is empty");
        Node old = mid;
        if (count == 1) {
            top = mid = null;
            count = 0;
            return old.val;
        }
        mid = (count % 2 == 1) ? old.next : old.prev;  // pick the new middle
        if (old.prev != null) old.prev.next = old.next; // join the neighbors
        if (old.next != null) old.next.prev = old.prev;
        count--;
        return old.val;
    }

    int size() { return count; }
}

How long it takes: every action changes a few arrows and maybe nudges mid by one box, O(1). Extra room: one box per item, O(n).

Watch out for

• A singly linked list is not enough. mid must step toward the top on push and toward the bottom on pop, so each box needs both arrows.
• Deleting the middle when there is one item must also clear top.
• Agree on which middle to return for an even size before you code. The parity rules flip if you pick the upper one.
• An array does not help with deleteMiddle, because removing from the middle of an array shifts everything after it.

What interviewers ask next

• Can you do it with two deques? Yes. Keep the bottom half in one deque and the top half in another, and rebalance so their sizes differ by at most one. The middle is at an end of one of them.
• Delete the middle of a plain stack using only recursion. Pop down to the middle with a counter, skip it, and push the others back as the calls return. That is O(n) time and O(n) call stack.
• What if you also need getMin()? Store, in each box, the smallest value from that box to the bottom.
• Can you find the k-th item from the top in O(1)? Not with a chain. You would use an array, which then makes deleteMiddle slow. Every design trades one action for another.

Remember this

Grown-up words: the pile of books is a stack, the chain with arrows both ways is a doubly linked list, the bookmark is the middle pointer, and even or odd is the parity of the size.