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.

--

--

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

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Kirill Shevchenko

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