# A stack with minimum element

Question 3.2 of Cracking the Coding Interview:

How would you design a stack which, in addition to `push` and `pop`, also has a function `min` which returns the minimum element? `push`, `pop` and `min` should all operate in O(1) time.

Without the requirement that `min` should operate in O(1) time, we could use a normal stack, with a `min` operation that searches the entire stack.

To make `min` O(1), we need to always have the pre-calculated minimum to hand. How about just in a variable `min`? We can update this when a new value `x` is pushed, with `min = x < min ? x : min`.

But unfortunately, `pop` doesn’t work: when popping off the `min` value, we need to know the new `min` value, but can’t search the entire stack while still providing an O(1) `pop`. We not only need to have the pre-calculated `min`, but all the previous `min`s too!

A simple way to implement this is to store the `min` at each node, alongside the value. Here’s an implementation in C:

``````#include <stdlib.h>
#include <assert.h>

typedef struct Node {
int val;
int min;
struct Node * next;
} Node;

Node* new_node(int val, int min, Node* next) {
Node* node = malloc(sizeof(Node));
node->val = val;
node->min = min;
node->next = next;
return node;
}

int minimum(int a, int b) {
return (a < b ? a : b);
}

// ----------------------------------------------------
// ------------------- STACK API ----------------------

typedef struct Stack {
Node* top;
} Stack;

int pop(Stack* stack) {
Node* top = stack->top;
if (top == NULL) return -1;
stack->top = top->next;
int x = top->val;
free(top);
return x;
}

void push(Stack* stack, int x) {
int new_min = stack->top != NULL ?
minimum(stack->top->min, x) :
x;
stack->top = new_node(x, new_min, stack->top);
}

int min(Stack* stack) {
return stack->top == NULL ? -1 : stack->top->min;
}

Stack* new_stack() {
return calloc(1, sizeof(struct Stack));
}

void destroy_stack(Stack* stack) {
while(pop(stack) != -1);
free(stack);
}

// ----------------------------------------------------
// --------------------- TESTS ------------------------

int main(int argc, char** argv) {
Stack* stack = new_stack();
assert(pop(stack) == -1);
assert(min(stack) == -1);
push(stack, 1);
assert(min(stack) == 1);
assert(pop(stack) == 1);
assert(min(stack) == -1);
assert(pop(stack) == -1);
assert(min(stack) == -1);
push(stack, 1);
assert(min(stack) == 1);
push(stack, 2);
assert(min(stack) == 1);
push(stack, 3);
assert(min(stack) == 1);
push(stack, -10);
assert(min(stack) == -10);
assert(pop(stack) == -10);
assert(min(stack) == 1);
assert(pop(stack) == 3);
assert(min(stack) == 1);
assert(pop(stack) == 2);
assert(min(stack) == 1);
assert(pop(stack) == 1);
assert(min(stack) == -1);
assert(pop(stack) == -1);
assert(pop(stack) == -1);
assert(min(stack) == -1);
destroy_stack(stack);
}
``````

A cleverer implementation recognizes that the `min` doesn’t change often, so we can compress the representation. The way I thought to do this was to run-length encode the stack of `min`s: keep a stack of `(min, counter)` tuples. Instead of pushing the same `min`, you increment the counter.

Again, here’s an implementation in C:

``````#include <stdlib.h>
#include <assert.h>

// ----------------------------------------------------
// -------------------- LIST API ----------------------

typedef struct Node {
int val;
struct Node * next;
} Node;

Node* new_node(int val, Node* next) {
Node* node = malloc(sizeof(Node));
node->val = val;
node->next = next;
return node;
}

int minimum(int a, int b) {
return (a < b ? a : b);
}

// ----------------------------------------------------
// ------------------- STACK API ----------------------

typedef struct Stack {
Node* top;
} Stack;

Stack* new_stack() {
return calloc(1, sizeof(struct Stack));
}

int stack_pop(Stack* stack) {
Node* top = stack->top;
if (top == NULL) return -1;
stack->top = top->next;
int x = top->val;
free(top);
return x;
}

void stack_push(Stack* stack, int x) {
stack->top = new_node(x, stack->top);
}

void destroy_stack(Stack* stack) {
while(stack_pop(stack) != -1);
free(stack);
}

// ----------------------------------------------------
// ----------------- MINSTACK API ---------------------

typedef struct MinStack {
Stack* values;
Stack* mins;
Stack* counters;
} MinStack;

MinStack* new_minstack() {
MinStack* ret = calloc(1, sizeof(struct MinStack));
ret->values = new_stack();
ret->mins = new_stack();
ret->counters = new_stack();
return ret;
}

void minstack_push(MinStack* min_stack, int x) {
stack_push(min_stack->values, x);
if (
min_stack->mins->top == NULL ||
x < min_stack->mins->top->val
) {
stack_push(min_stack->mins, x);
stack_push(min_stack->counters, 1);
} else {
min_stack->counters->top->val++;
}
}

int minstack_pop(MinStack* min_stack) {
int ret = stack_pop(min_stack->values);
if (ret != -1) {
if (min_stack->counters->top->val == 1) {
stack_pop(min_stack->mins);
stack_pop(min_stack->counters);
} else {
min_stack->counters->top->val--;
}
}
return ret;
}

int minstack_min(MinStack* min_stack) {
if (min_stack->mins->top == NULL) return -1;
return min_stack->mins->top->val;
}

void destroy_minstack(MinStack* min_stack) {
destroy_stack(min_stack->values);
destroy_stack(min_stack->mins);
destroy_stack(min_stack->counters);
}

// ----------------------------------------------------
// --------------------- TESTS ------------------------

int main(int argc, char** argv) {
MinStack* stack = new_minstack();
assert(minstack_pop(stack) == -1);
assert(minstack_min(stack) == -1);
minstack_push(stack, 1);
assert(minstack_min(stack) == 1);
assert(minstack_pop(stack) == 1);
assert(minstack_min(stack) == -1);
assert(minstack_pop(stack) == -1);
assert(minstack_min(stack) == -1);
minstack_push(stack, 1);
assert(minstack_min(stack) == 1);
minstack_push(stack, 2);
assert(minstack_min(stack) == 1);
minstack_push(stack, 3);
assert(minstack_min(stack) == 1);
minstack_push(stack, -10);
assert(minstack_min(stack) == -10);
assert(minstack_pop(stack) == -10);
assert(minstack_min(stack) == 1);
assert(minstack_pop(stack) == 3);
assert(minstack_min(stack) == 1);
assert(minstack_pop(stack) == 2);
assert(minstack_min(stack) == 1);
assert(minstack_pop(stack) == 1);
assert(minstack_min(stack) == -1);
assert(minstack_pop(stack) == -1);
assert(minstack_pop(stack) == -1);
assert(minstack_min(stack) == -1);
destroy_minstack(stack);
}
``````

The book has a different optimization method. It also keeps a separate stack for the `min`s, and pushes a value to the `min` stack if the value is less than or equal to the current `min`. This method has an annoying worst-case, though: when the `min` is pushed repeatedly onto the stack, it’s stored every time instead of just incrementing a counter.

What can computers do? What are the limits of mathematics? And just how busy can a busy beaver be? This year, I’m writing Busy Beavers, a unique interactive book on computability theory. You and I will take a practical and modern approach to answering these questions — or at least learning why some questions are unanswerable!

It’s only \$19, and you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

After months of secret toil, I and Andrew Carr released Everyday Data Science, a unique interactive online course! You’ll make the perfect glass of lemonade using Thompson sampling. You’ll lose weight with differential equations. And you might just qualify for the Olympics with a bit of statistics!

It’s \$29, but you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

### More by Jim

Tagged #ctci, #programming, #c. All content copyright James Fisher 2020. This post is not associated with my employer.