# 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.

I just released Vidrio, a free app for macOS and Windows to make your screen-sharing awesomely holographic. Vidrio shows your webcam video on your screen, just like a mirror. Then you just share or record your screen with Zoom, QuickTime, or any other app. Vidrio makes your presentations effortlessly engaging, showing your gestures, gazes, and expressions. #1 on Product Hunt. Available for macOS and Windows.

With Vidrio

With generic competitor

### More by Jim

Tagged #ctci, #programming, #c. All content copyright James Fisher 2020. This post is not associated with my employer. Found an error? Edit this page.