How to find Min or Max value in a Stack with Go

This is a typical interview question which is going to ask you to implement a stack which can track the maximum or minimum value for the current stack. In this note, I want to show a solution on how to implement a Min stack. You might implement Max stack in the similar way.

Stack

Since the Go has no built-in structure for stack, we have to initialize it ourselves and implement the following functions: push, pop and top.

type MinStack struct {
  stack  []int
  min int
}

MinStack is a simple struct with two fields. It will represent a stack with a slice of integers and contains it’s minimum value.

The next step is to write a construct function to create the new one instance of the stack. We just have to set min to be a maximum int64.

import "math"
// ...
func NewMinStack() MinStack {
  min := math.MaxInt64
  return MinStack{min: min}
}

Push

When we push an element, it should go to the end. We can use a appendfunction for this one. As an element could be lower than the current min, we are going to check for that and adjust min if needed.

func (ms *MinStack) Push(item int) {
  ms.stack = append(ms.stack, item)
  if item < ms.min {
    ms.min = item
  }
}

Pop

Next, we have the pop function. The first part is pretty simple. Remove the last element from the stack and save its value in variablelast, because we need to make sure it's not the min value. If it's not the minimum, we can return result earlier.

func (ms *MinStack) Pop() {
  length := len(ms.stack)
  last := ms.stack[length-1]
  ms.stack = ms.stack[:length-1]
  if last != ms.min {
    return
  }
  // ...
}

If we get to the rest of pop, it means we just popped an element off that had the min value, so we need to find the minimum by iterating through the list.

func (ms *MinStack) Pop() {
  // ...
  ms.min = math.MaxInt64
  for _, x := range ms.stack {
    if x < ms.min {
      ms.min = x
    }
  }
}

Next, we need to implement GetTop and GetMin functions that are actually kind of trivial.

GetTop

func (ms *MinStack) GetTop() int {
  return ms.stack[len(ms.stack)-1]
}

GetMin

func (ms *MinStack) GetMin() int {
  return ms.min
}

Full Solution

This solution optimized for getting the min value and inserting elements. The slow part is when we remove elements, because it needs to iterate over the whole stack, which takes O(n) time.

import "math"

type MinStack struct {
  stack  []int
  min int
}
func NewMinStack() MinStack {
  return MinStack{min: math.MaxInt64}
}
func (ms *MinStack) Push(item int) {
  ms.stack = append(ms.stack, item)
  if item < ms.min {
    ms.min = item
  }
}
func (ms *MinStack) Pop() {
  length := len(ms.stack)
  last := ms.stack[length-1]
  ms.stack = ms.stack[:length-1]
  if last != ms.min {
   return
  }
  ms.min = math.MaxInt64
  for _, x := range ms.stack {
    if x < ms.min {
      ms.min = x
    }
  }
}
func (ms *MinStack) GetTop() int {
  return ms.stack[len(ms.stack)-1]
}
func (ms *MinStack) GetMin() int {
  return ms.min
}

An alternative way of handling this would be to have a second internal stack that’s sorted, which would make updating min during a pop and consume O(1) time. But it will make the push function take longer because it will require adding into a sorted list which is an O(n) operation.

So, in this alternate structure, we have an O(n) operation at every push rather than having the chance of O(n) during pop.