[Leetcode] Min Stack Problem in Golang

Photo by James Harrison on Unsplash

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Here is the code to solve this problem.

package main

type MinStack struct {
 stack []int
 min []int
}

func NewMinStack() *MinStack {
 return &MinStack{stack: []int{}, min: []int{}}
}

// Push element x onto stack.
func (s *MinStack) Push(x int) {
 s.stack = append(s.stack, x)
 if len(s.min) == 0 || x <= s.min[len(s.min)-1] {
  s.min = append(s.min, x)
 }
}

// Pop removes the element on top of the stack.
func (s *MinStack) Pop() {
 if len(s.stack) == 0 {
  return
 }
 if s.stack[len(s.stack)-1] == s.min[len(s.min)-1] {
  s.min = s.min[:len(s.min)-1]
 }
 s.stack = s.stack[:len(s.stack)-1]
}

// get top
func (s *MinStack) Top() int {
 return s.stack[len(s.stack)-1]
}

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

Explanation

In this problem, we use two stacks. The first stack stack []int is used to store the value in a FIFO order.

The second stack min []int is used to store the minimum value in the first stack in order, that means any time we push a value into the first stack, we need to compare it with the top value of the second stack, if it is smaller than the top value of the second stack, we push it into the second stack, otherwise, we do nothing.

This is a classic monotonic stack problem and the complexity is O(1) for all the operations.

I hope you enjoyed this post :) Thanks for reading.