# 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

`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

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

## Pop

`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

`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.

--

--

## More from Kirill Shevchenko

Software Engineer. Interested in Microservices, Distributed Systems and Cloud Services.