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

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
}
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
}
// ...
}
func (ms *MinStack) Pop() {
// ...
ms.min = math.MaxInt64
for _, x := range ms.stack {
if x < ms.min {
ms.min = x
}
}
}

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
}

--

--

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

Kirill Shevchenko

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