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