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.

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