# 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 `append`function 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 variable`last`, 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.