</>EmbeddedInterview

Implement a min stack (getMin in O(1)).

Medium"Coding: Linked Lists, Stacks & Queues"
#include <stdbool.h>

#define MS_CAP 32
typedef struct { int val[MS_CAP], min[MS_CAP]; int top; } minstack_t;

bool ms_push(minstack_t *s, int v)
{
    if (s->top == MS_CAP) return false;
    s->val[s->top] = v;
    s->min[s->top] = (s->top == 0 || v < s->min[s->top - 1]) ? v : s->min[s->top - 1];
    s->top++;
    return true;
}
bool ms_pop(minstack_t *s, int *v) { if (s->top == 0) return false; *v = s->val[--s->top]; return true; }
bool ms_min(const minstack_t *s, int *m) { if (s->top == 0) return false; *m = s->min[s->top - 1]; return true; }

Points: store, for each level, the minimum of everything at or below it; then the minimum is always at the top, O(1) for all operations at the cost of a second array. Space can be reduced by pushing to the min stack only when a new minimum (or equal) arrives.