Min Stack

Medium

The problem

Build a MinStack: a stack of numbers that can also tell you its smallest number at any moment. Push(val) puts a number on top, Pop() removes the top number, Top() returns the top number without removing it, and GetMin() returns the smallest number currently in the stack. Every method must run in constant time.

Example 1
Input: s := Constructor() s.Push(5) s.Push(2) s.Push(7) s.GetMin() // 2 s.Pop() s.Top() // 2 s.Pop() s.GetMin() // 5
Output: GetMin() gives 2, then Top() gives 2, then GetMin() gives 5
The stack holds 5, 2, 7 so its smallest is 2. Pop removes 7, so the top is 2. Pop removes 2, which leaves only 5.

Limits

Pop, Top and GetMin are only called when the stack is not empty
Up to 30,000 calls in total
-2,147,483,648 ≤ val ≤ 2,147,483,647

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

When you pop, the minimum might change. What extra information should each element carry?

The idea

Store pairs (value, minimum-so-far) or keep a second stack of minimums, so getMin is always the top of it.

Target: O(1) per operation

Go function shape

type MinStack struct{}
func Constructor() MinStack
func (m *MinStack) Push(val int)
func (m *MinStack) Pop()
func (m *MinStack) Top() int
func (m *MinStack) GetMin() int

Reference solution

Tested with go test. Try it yourself first, then compare.

// MinStack: every element remembers the minimum at the time it was pushed,
// so after a pop the previous minimum is simply the new top.
type MinStack struct{ items []struct{ val, min int } }

func (m *MinStack) Push(v int) {
	lo := v
	if n := len(m.items); n > 0 && m.items[n-1].min < lo {
		lo = m.items[n-1].min
	}
	m.items = append(m.items, struct{ val, min int }{v, lo})
}
func (m *MinStack) Pop()        { m.items = m.items[:len(m.items)-1] }
func (m *MinStack) Top() int    { return m.items[len(m.items)-1].val }
func (m *MinStack) GetMin() int { return m.items[len(m.items)-1].min }

Read the lesson: Stack Basics