155. Min stack

155_solution1_two_arrays.c

#include <stdlib.h>

typedef struct {
    int *v;
    int *mins;
    int size;
    int cap;
} MinStack;

MinStack *minStackCreate() {
    MinStack *s = malloc(sizeof(MinStack));
    s->cap = 16;
    s->size = 0;
    s->v = malloc(s->cap * sizeof(int));
    s->mins = malloc(s->cap * sizeof(int));
    return s;
}

void minStackPush(MinStack *s, int value) {
    if (s->size == s->cap) {
        s->cap *= 2;
        s->v = realloc(s->v, s->cap * sizeof(int));
        s->mins = realloc(s->mins, s->cap * sizeof(int));
    }
    s->v[s->size] = value;

    int curMin = value;
    if (s->size > 0 && s->mins[s->size - 1] < value)
        curMin = s->mins[s->size - 1];
    s->mins[s->size] = curMin;
    s->size++;
}

void minStackPop(MinStack *s) { s->size--; }

int minStackTop(MinStack *s) { return s->v[s->size - 1]; }

int minStackGetMin(MinStack *s) { return s->mins[s->size - 1]; }

void minStackFree(MinStack *s) {
    free(s->v);
    free(s->mins);
    free(s);
}

155_solution2_vector_pair.c

#include <stdlib.h>

typedef struct {
    int value;
    int minSoFar; // minimum of everything up to and including value
} Entry;

typedef struct {
    Entry *st;
    int size;
    int cap;
} MinStack;

MinStack *minStackCreate() {
    MinStack *s = malloc(sizeof(MinStack));
    s->cap = 16;
    s->size = 0;
    s->st = malloc(s->cap * sizeof(Entry));
    return s;
}

void minStackPush(MinStack *s, int value) {
    if (s->size == s->cap) {
        s->cap *= 2;
        s->st = realloc(s->st, s->cap * sizeof(Entry));
    }
    int curMin = value;
    if (s->size > 0 && s->st[s->size - 1].minSoFar < value)
        curMin = s->st[s->size - 1].minSoFar;
    s->st[s->size++] = (Entry){value, curMin};
}

void minStackPop(MinStack *s) { s->size--; }

int minStackTop(MinStack *s) { return s->st[s->size - 1].value; }

int minStackGetMin(MinStack *s) { return s->st[s->size - 1].minSoFar; }

void minStackFree(MinStack *s) {
    free(s->st);
    free(s);
}

155_solution1_two_arrays.cpp

#include <vector>
using namespace std;

class MinStack {
private:
  vector<int> v;
  vector<int> mins;

public:
  MinStack() {}

  void push(int value) {
    v.push_back(value);

    int curmin = mins.empty() ? value : min(mins.back(), value);
    mins.push_back(curmin);
  }

  void pop() {
    v.pop_back();
    mins.pop_back();
  }

  int top() { return v.back(); }

  int getMin() { return mins.back(); }
};

155_solution2_vector_pair.cpp

#include <vector>
using namespace std;

class MinStack {
private:
  vector<pair<int, int>>
      st; // {value, minimum of everything up to and including it}

public:
  MinStack() {}

  void push(int value) {
    int curMin = st.empty() ? value : min(st.back().second, value);
    st.push_back({value, curMin});
  }

  void pop() { st.pop_back(); }

  int top() { return st.back().first; }

  int getMin() { return st.back().second; }
};

155_solution3_two_stacks.cpp

#include <stack>
using namespace std;

class MinStack {
private:
  stack<int> minst;
  stack<int> st;

public:
  MinStack() {}

  void push(int value) {
    st.push(value);
    int mn = minst.empty() ? value : min(minst.top(), value);
    minst.push(mn);
  }

  void pop() {
    st.pop();
    minst.pop();
  }

  int top() { return st.top(); }

  int getMin() { return minst.top(); }
};

155_solution1_two_arrays.go

package main

type MinStack struct {
    v    []int
    mins []int
}

func Constructor() MinStack {
    return MinStack{}
}

func (s *MinStack) Push(value int) {
    s.v = append(s.v, value)

    curMin := value
    if n := len(s.mins); n > 0 && s.mins[n-1] < value {
        curMin = s.mins[n-1]
    }
    s.mins = append(s.mins, curMin)
}

func (s *MinStack) Pop() {
    s.v = s.v[:len(s.v)-1]
    s.mins = s.mins[:len(s.mins)-1]
}

func (s *MinStack) Top() int {
    return s.v[len(s.v)-1]
}

func (s *MinStack) GetMin() int {
    return s.mins[len(s.mins)-1]
}

155_solution2_vector_pair.go

package main

type entry struct {
    value    int
    minSoFar int // minimum of everything up to and including value
}

type MinStack struct {
    st []entry
}

func Constructor() MinStack {
    return MinStack{}
}

func (s *MinStack) Push(value int) {
    curMin := value
    if n := len(s.st); n > 0 && s.st[n-1].minSoFar < value {
        curMin = s.st[n-1].minSoFar
    }
    s.st = append(s.st, entry{value, curMin})
}

func (s *MinStack) Pop() {
    s.st = s.st[:len(s.st)-1]
}

func (s *MinStack) Top() int {
    return s.st[len(s.st)-1].value
}

func (s *MinStack) GetMin() int {
    return s.st[len(s.st)-1].minSoFar
}

155_solution1_two_arrays.java

import java.util.ArrayDeque;
import java.util.Deque;

class MinStack {
    private final Deque<Integer> v = new ArrayDeque<>();
    private final Deque<Integer> mins = new ArrayDeque<>();

    public MinStack() {}

    public void push(int value) {
        v.push(value);

        int curMin = mins.isEmpty() ? value : Math.min(mins.peek(), value);
        mins.push(curMin);
    }

    public void pop() {
        v.pop();
        mins.pop();
    }

    public int top() {
        return v.peek();
    }

    public int getMin() {
        return mins.peek();
    }
}

155_solution2_vector_pair.java

import java.util.ArrayDeque;
import java.util.Deque;

class MinStack {
    // {value, minimum of everything up to and including it}
    private final Deque<int[]> st = new ArrayDeque<>();

    public MinStack() {}

    public void push(int value) {
        int curMin = st.isEmpty() ? value : Math.min(st.peek()[1], value);
        st.push(new int[] {value, curMin});
    }

    public void pop() {
        st.pop();
    }

    public int top() {
        return st.peek()[0];
    }

    public int getMin() {
        return st.peek()[1];
    }
}

155_solution1_two_arrays.js

class MinStack {
  constructor() {
    this.v = [];
    this.mins = [];
  }

  push(value) {
    this.v.push(value);
    const curMin = this.mins.length ? Math.min(this.mins.at(-1), value) : value;
    this.mins.push(curMin);
  }

  pop() {
    this.v.pop();
    this.mins.pop();
  }

  top() {
    return this.v.at(-1);
  }

  getMin() {
    return this.mins.at(-1);
  }
}

155_solution2_vector_pair.js

class MinStack {
  constructor() {
    this.st = []; // [value, minimum of everything up to and including it]
  }

  push(value) {
    const curMin = this.st.length ? Math.min(this.st.at(-1)[1], value) : value;
    this.st.push([value, curMin]);
  }

  pop() {
    this.st.pop();
  }

  top() {
    return this.st.at(-1)[0];
  }

  getMin() {
    return this.st.at(-1)[1];
  }
}

155_solution1_two_arrays.py

class MinStack:
    def __init__(self):
        self.v = []
        self.mins = []

    def push(self, value: int) -> None:
        self.v.append(value)
        self.mins.append(min(self.mins[-1], value) if self.mins else value)

    def pop(self) -> None:
        self.v.pop()
        self.mins.pop()

    def top(self) -> int:
        return self.v[-1]

    def getMin(self) -> int:
        return self.mins[-1]

155_solution2_vector_pair.py

class MinStack:
    def __init__(self):
        self.st = []  # (value, minimum of everything up to and including it)

    def push(self, value: int) -> None:
        cur_min = min(self.st[-1][1], value) if self.st else value
        self.st.append((value, cur_min))

    def pop(self) -> None:
        self.st.pop()

    def top(self) -> int:
        return self.st[-1][0]

    def getMin(self) -> int:
        return self.st[-1][1]

155_solution1_two_arrays.rs

struct MinStack {
    v: Vec<i32>,
    mins: Vec<i32>,
}

impl MinStack {
    fn new() -> Self {
        MinStack { v: Vec::new(), mins: Vec::new() }
    }

    fn push(&mut self, value: i32) {
        self.v.push(value);

        let cur_min = self.mins.last().map_or(value, |&m| m.min(value));
        self.mins.push(cur_min);
    }

    fn pop(&mut self) {
        self.v.pop();
        self.mins.pop();
    }

    fn top(&self) -> i32 {
        *self.v.last().unwrap()
    }

    fn get_min(&self) -> i32 {
        *self.mins.last().unwrap()
    }
}

155_solution2_vector_pair.rs

struct MinStack {
    st: Vec<(i32, i32)>, // (value, minimum of everything up to and including it)
}

impl MinStack {
    fn new() -> Self {
        MinStack { st: Vec::new() }
    }

    fn push(&mut self, value: i32) {
        let cur_min = self.st.last().map_or(value, |&(_, m)| m.min(value));
        self.st.push((value, cur_min));
    }

    fn pop(&mut self) {
        self.st.pop();
    }

    fn top(&self) -> i32 {
        self.st.last().unwrap().0
    }

    fn get_min(&self) -> i32 {
        self.st.last().unwrap().1
    }
}