Learn more about Russian war crimes in Ukraine.

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 mins 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 mins: 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 mins, 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. Found an error? Edit this page.