Implement N stacks in an Array

The problem, simply

You get one array with n boxes. Build k stacks inside it. You need push(s, x), pop(s) and peek(s) for any stack number s.

The rule: no stack may say "full" while there is still an empty box anywhere in the array. One busy stack should be able to use almost the whole array if the others are small.

A story to remember it

Picture it

Examples

Way 1: the simple way

Cut the array into k equal blocks of n/k boxes. Stack s lives in boxes s * n/k to (s + 1) * n/k - 1 and works like a normal array stack inside its block.

1. Keep tops[s], starting at s * size - 1 (one before the block).
2. Push: if tops[s] is at the end of the block, overflow. Else arr[++tops[s]] = x.
3. Pop: if tops[s] is before the block, underflow. Else return arr[tops[s]--].

class KStacksBlocks {
    private final int[] arr, tops;
    private final int size;                 // boxes per stack

    KStacksBlocks(int n, int k) {
        arr = new int[n];
        tops = new int[k];
        size = n / k;
        for (int s = 0; s < k; s++) tops[s] = s * size - 1;
    }

    void push(int s, int x) {
        if (tops[s] == (s + 1) * size - 1) throw new RuntimeException("stack " + s + " overflow");
        arr[++tops[s]] = x;
    }

    int pop(int s) {
        if (tops[s] < s * size) throw new RuntimeException("stack " + s + " underflow");
        return arr[tops[s]--];
    }
}

How long it takes: O(1) per action. Extra room: the array plus k tops, O(n + k). But a stack overflows after n/k items even when the rest of the array is empty.

Way 2: the clever way

Treat each box like a locker with a sticky note. Use three arrays:

• arr[i]: the value in box i.
• next[i]: for a used box, the box under it in the same stack. For an empty box, the next empty box.
• top[s]: the box on top of stack s, or -1 if it is empty.

And one number, free, the first empty box. At the start every box is empty and they are chained 0, 1, 2, ....

1. push(s, x): if free == -1, overflow. Else take box i = free, move free = next[i], write arr[i] = x, set next[i] = top[s], then top[s] = i.
2. pop(s): if top[s] == -1, underflow. Else take i = top[s], set top[s] = next[i], then put box i back at the front of the empty chain: next[i] = free, free = i. Return arr[i].

The empty boxes form a stack of their own. Push moves a box from the free stack to stack s, and pop moves it back.

class KStacks {
    private final int[] arr, next, top;
    private int free;                       // first empty box, -1 if none

    KStacks(int n, int k) {
        arr = new int[n];
        next = new int[n];
        top = new int[k];
        Arrays.fill(top, -1);
        for (int i = 0; i < n - 1; i++) next[i] = i + 1;  // chain all empty boxes
        next[n - 1] = -1;
        free = 0;
    }

    void push(int s, int x) {
        if (free == -1) throw new RuntimeException("overflow");
        int i = free;
        free = next[i];         // take box i off the empty chain
        arr[i] = x;
        next[i] = top[s];       // the old top is now under box i
        top[s] = i;
    }

    int pop(int s) {
        if (top[s] == -1) throw new RuntimeException("stack " + s + " underflow");
        int i = top[s];
        top[s] = next[i];       // the box under becomes the top
        next[i] = free;         // box i goes back on the empty chain
        free = i;
        return arr[i];
    }

    int peek(int s) {
        if (top[s] == -1) throw new RuntimeException("stack " + s + " is empty");
        return arr[top[s]];
    }

    boolean isEmpty(int s) { return top[s] == -1; }

    boolean isFull() { return free == -1; }
}

How long it takes: every action changes a few numbers, O(1). Extra room: arr and next of size n, plus top of size k, so O(n + k). Any stack can grow until the whole array is used.

Watch out for

• In push, read free = next[i] before writing next[i] = top[s], for the same reason.
• The next array means two things: "box under me" for used boxes and "next empty box" for empty ones. A box is only ever on one chain, so that is safe.
• Check free == -1 before pushing, and top[s] == -1 before popping.
• The old value stays in arr after a pop. That is fine, because nothing points to it.

What interviewers ask next

• Do the same for k queues. Keep front[q] and rear[q], and link each new box after rear[q]. The free chain works the same way.
• Why not use k separate ArrayLists? In real code you would. This problem is about memory tricks for systems with one fixed block of memory, like an embedded device or an allocator.
• What is the free chain called? A free list. Memory allocators and object pools use it to hand out and take back fixed size blocks in O(1).
• Can you give the size of each stack in O(1)? Keep a count[s] array and update it in push and pop.

Remember this

Grown-up words: the lockers are array slots, the sticky notes are the next array (an index based linked list), the list of empty lockers is a free list, and top[s] is the head of stack s.