Min Stack | DSA Journal

Question

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the following operations:

push(x) — Push element x onto stack
pop() — Removes the element on the top of the stack
top() — Get the top element
getMin() — Retrieve the minimum element in the stack

Example

Input:

[MinStack, push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()]

Output: [null, null, null, null, -3, null, 0, -2]

Explanation:

The minimum was -3, after popping, top is 0 and new min is -2.

My Notes

Use a custom struct or object that stores both value and current min.
Each time a new value is pushed, compare with the current min and store the new min.
pop simply removes the top of the stack.
top and getMin just return values from the last item in the stack.
Time complexity for all operations is O(1).

package main

import (
    "fmt"
)

type Node struct {
    value int
    min   int
}

type MinStack struct {
    items []Node
}

func Constructor() MinStack {
    stack := MinStack{}
    return stack
}

func (this *MinStack) Push(val int) {

    min := val
    if len(this.items) > 0 {
        if this.items[len(this.items)-1].min < val {
            min = this.items[len(this.items)-1].min
        }
    }
  
    this.items = append(this.items, Node{value: val, min: min})

}

func (this *MinStack) Pop() {
    this.items = this.items[:len(this.items)-1]
}

func (this *MinStack) Top() int {
    return this.items[len(this.items)-1].value
}

func (this *MinStack) GetMin() int {
    return this.items[len(this.items)-1].min
}

func main() {
    operations := []string{"MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"}
    args := [][]int{{}, {-2}, {0}, {-3}, {}, {}, {}, {}}
  
    var stack MinStack
    var output []interface{}
  
    for i, op := range operations {
        switch op {
        case "MinStack":
            stack = Constructor()
            output = append(output, nil)
        case "push":
            stack.Push(args[i][0])
            output = append(output, nil)
        case "pop":
            stack.Pop()
            output = append(output, nil)
        case "top":
            val := stack.Top()
            output = append(output, val)
        case "getMin":
            min := stack.GetMin()
            output = append(output, min)
        }
    }
  
    fmt.Println(output)
}