Start learning free

LESSON 398 OF 540 · STACK

Min Stack in Go: O(1) Push, Pop, Top and GetMin

Practice O(1) Read the full explanation

A stack hands its values back in the opposite order they arrived: the last value pushed is the first one popped. Design a stack that can also say, at any moment, which value is the smallest of all the values it holds, and do every operation in constant time.

Implement the class MinStack:

  • MinStack() creates an empty stack.
  • push(val) puts the integer val on top of the stack.
  • pop() removes the value on top of the stack.
  • top() returns the value on top of the stack, without removing it.
  • getMin() returns the smallest value in the stack, without removing anything.

The input is a list of operations, applied in order to one new MinStack. The output lists what the top and getMin calls return, in order. The starter code spells these names the way your language does.

 

Example 1:

Input:
    push(-2)
    push(0)
    push(-3)
    getMin()
    pop()
    top()
    getMin()
Output: -3 0 -2
Explanation:
After the three pushes the stack holds -2, 0 and -3, with -3 on top, so the smallest value is -3.
pop() removes -3. Now 0 is on top, and the smallest value is -2 again: when the minimum leaves,
the minimum from before it arrived comes back.

Example 2:

Input:
    push(5)
    push(5)
    push(7)
    getMin()
    pop()
    pop()
    getMin()
    top()
Output: 5 5 5
Explanation: 5 is pushed twice. The two pops remove 7 and one of the 5s, but the other 5 is still in the stack, so the smallest value is still 5.

Example 3:

Input:
    push(3)
    top()
    getMin()
    push(1)
    push(2)
    top()
    getMin()
    pop()
    pop()
    getMin()
Output: 3 3 2 1 3
Explanation: The value on top (2) and the smallest value (1) can be different values. Once 2 and 1 are popped, only 3 is left, and it is the smallest again.

 

Constraints:

  • -231 <= val <= 231 - 1
  • pop, top and getMin are only called when the stack is not empty.
  • At most 2 * 105 calls in total are made to push, pop, top and getMin.

Note:

Each operation should run in O(1) time. Looking through the whole stack for its smallest value in getMin would take O(n) time per call, where n is the number of values in the stack.

STEP 1 OF 10
    Ctrl + Enter to check

    GO · STACK

    Min Stack in Go, explained

    Problem overview

    A stack gives values back in reverse order: the last value pushed is the first one popped. This lesson asks for a MinStack, a stack that can also report the smallest value it currently holds. Every operation must take constant time: Push, Pop, Top and GetMin. In Go the names are capitalised, and Constructor creates an empty stack.

    Take the first example. After Push(-2), Push(0) and Push(-3) the stack holds -2, 0 and -3, with -3 on top, so GetMin() returns -3. After Pop() the top is 0, and GetMin() returns -2 again. The minimum that left the stack takes its effect with it, and the earlier minimum comes back.

    The calls to Pop, Top and GetMin only happen on a non-empty stack, so the code doesn't need to handle an empty one.

    Approach: remember the minimum at every depth

    A plain slice already gives O(1) push, pop and top. The only slow operation is GetMin: scanning the whole stack for its smallest value costs O(n) per call.

    The way out comes from one observation. A value leaves the stack only after every value above it has left, so the values below it never change while it is there. The minimum of "this value and everything under it" is therefore fixed at the moment the value is pushed. It can be computed once, from one comparison, and stored.

    So the stack keeps two slices of the same length. stack holds the values. minStack holds, at each depth, the smallest value from the bottom up to that depth. The last entry of minStack always describes the whole stack as it is now, which is exactly what GetMin must return.

    Running the third example gives this picture. After Push(3), Push(1) and Push(2), stack is [3 1 2] and minStack is [3 1 1]. The top value is 2 and the smallest is 1, which shows that the two answers can differ. After two pops only 3 remains, and GetMin returns 3.

    Step by step

    1. Add the stack field to the struct as a []int. The end of the slice is the top of the stack, because append and reslicing both work at the end.
    2. Add the minStack field, also a []int. Its entry at each depth is the smallest of the value at that depth and all values below it.
    3. Return an empty MinStack{} from Constructor. Both slices start as nil, and append and len work on a nil slice.
    4. In Push, append the value to this.stack and store the result back, since append returns the longer slice and leaves the one you gave it alone.
    5. Start currentMin at val. If the stack was empty, the new value is its only value, so it is also the smallest.
    6. If minStack isn't empty, lower currentMin to the smaller of itself and the last entry of minStack. That entry is already the minimum of everything below the new value, so one comparison is enough.
    7. Append currentMin to minStack. Now both slices have the same length. Equal values are pushed too, so a minimum that was pushed twice is remembered twice.
    8. In Pop, cut the last element off both slices with s[:len(s)-1]. Removing the last entry of minStack uncovers the minimum the stack had before that value arrived.
    9. In Top, return the last element of stack. Reading it removes nothing.
    10. In GetMin, return the last element of minStack. That is O(1), like every other operation.

    The solution in Go

    type MinStack struct {
    stack []int
    minStack []int
}
func Constructor() MinStack {
    return MinStack{}
}
func (this *MinStack) Push(val int) {
    this.stack = append(this.stack, val)
    currentMin := val
    if len(this.minStack) > 0 {
        currentMin = min(currentMin, this.minStack[len(this.minStack)-1])
    }
    this.minStack = append(this.minStack, currentMin)
}
func (this *MinStack) Pop() {
    this.stack = this.stack[:len(this.stack)-1]
    this.minStack = this.minStack[:len(this.minStack)-1]
}
func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1]
}
func (this *MinStack) GetMin() int {
    return this.minStack[len(this.minStack)-1]
}

    The Go details worth a closer look:

    • Pointer receivers. Push and Pop assign to this.stack, so they need the receiver *MinStack. With a value receiver they would change a copy and the caller's stack would stay the same. Go lets you call these methods on an addressable variable such as s := Constructor() with plain s.Push(4).
    • this is only a name. Go has no special this keyword. It is an ordinary receiver name, and the lesson uses it to match the usual shape of this problem.
    • The zero value works. A struct whose fields are nil slices is a valid empty stack. Even var e MinStack followed by e.Push(4) works, and e.Top() then returns 4.
    • append must be assigned back. Writing append(this.stack, val) alone would discard the result, and the stack would not grow.
    • Reslicing doesn't free memory. s[:len(s)-1] shortens the length but keeps the same backing array. That is fine here: the next append reuses the slot. It's the reason popping is O(1) with no copying.
    • Built-in min. Since Go 1.21, min is built in, so no import is needed. It works on int directly.

    Complexity

    Time: O(1) per operation. Push does one comparison and two appends (amortised O(1): an append occasionally grows the backing array, but the cost spreads over many pushes). Pop, Top and GetMin each do a single index or reslice.

    Space: O(n) for n values currently in the stack. The second slice doubles the memory but doesn't change the order of growth.

    Edge cases and common mistakes

    • Keeping one running min variable. It breaks on the first pop of the minimum: after popping -3 in the first example, a single variable still says -3, and it has no way to know the answer should be -2.
    • Not pushing equal values onto minStack. In the second example 5 is pushed twice. If only the first 5 were recorded in minStack, the two slices would have different lengths, and the pops would remove the wrong minimum or run off the end of minStack. Recording an entry per value keeps them aligned.
    • Popping only one slice. The slices must stay the same length. If Pop trims only stack, GetMin keeps returning an old minimum.
    • Dropping the assignment on append. The slice you pass is unchanged, so the value is lost.
    • Calling Pop on an empty stack. It panics with slice bounds out of range [:-1]. The lesson's tests never do this, but a stack you reuse elsewhere might want a check.
    • Values at the edges. The constraints allow -2147483648 to 2147483647, and Go's int is 64 bits, so nothing overflows. Even -9223372036854775808 works as a stored value.

    Testing

    Running the lesson's examples on the code gives these answers.

    • Push -2, 0, -3, then GetMin() returns -3. After Pop(), stack is [-2 0], minStack is [-2 -2], Top() returns 0 and GetMin() returns -2.
    • Push 5, 5, 7, then GetMin() returns 5. After two pops stack is [5], and both GetMin() and Top() return 5.
    • Push 3, 1, 2: Top() returns 2 and GetMin() returns 1, with minStack equal to [3 1 1]. After two pops, GetMin() returns 3.
    Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free