NUHMAN.com

Introduction

LeetCode 155 is a popular problem that asks us to design a stack that supports the following operations:

1. push(x) – Pushes an element x onto the stack.
2. pop() – Removes the element on the top of the stack.
3. top() – Retrieves the top element of the stack.
4. getMin() – Retrieves the minimum element in the stack.

The challenge is to design the stack in such a way that each operation (push, pop, top, and getMin) runs in O(1) time complexity.

Problem Statement

Implement a MinStack class that supports the above four operations efficiently.

Function Signature:

go

type MinStack struct {
    stack []int
    minStack []int
}

func Constructor() MinStack {
    return MinStack{
        stack:    []int{},
        minStack: []int{},
    }
}

func (this *MinStack) Push(x int) {
    this.stack = append(this.stack, x)
    if len(this.minStack) == 0 || x <= this.minStack[len(this.minStack)-1] {
        this.minStack = append(this.minStack, x)
    }
}

func (this *MinStack) Pop() {
    if len(this.stack) > 0 {
        top := this.stack[len(this.stack)-1]
        this.stack = this.stack[:len(this.stack)-1]
        if top == this.minStack[len(this.minStack)-1] {
            this.minStack = this.minStack[:len(this.minStack)-1]
        }
    }
}

func (this *MinStack) Top() int {
    if len(this.stack) > 0 {
        return this.stack[len(this.stack)-1]
    }
    return -1 // or any appropriate error value
}

func (this *MinStack) GetMin() int {
    if len(this.minStack) > 0 {
        return this.minStack[len(this.minStack)-1]
    }
    return -1 // or any appropriate error value
}

Approach

Key Idea:

We need to ensure that the getMin() operation can be performed in O(1) time. To do this, we use an additional stack (minStack) that stores the current minimum value of the stack.

• Main Stack (stack): This stack stores the elements of the main stack.
• Minimum Stack (minStack): This stack keeps track of the minimum element at each level. The top of the minStack always holds the minimum value of the elements in the stack.

Steps:

1. Push Operation:

• When an element x is pushed onto the stack, we also compare it with the current minimum (top of the minStack).
• If x is smaller than or equal to the current minimum, we also push it onto the minStack.

1. Pop Operation:

• When an element is popped from the stack, we check if the element is equal to the current minimum (top of the minStack). If it is, we also pop from the minStack.

1. Top Operation:

• We simply return the top element of the stack.

1. GetMin Operation:

• The top element of the minStack represents the current minimum value in the stack.

Go Implementation

go

package main

import "fmt"

type MinStack struct {
    stack    []int
    minStack []int
}

// Constructor initializes the MinStack.
func Constructor() MinStack {
    return MinStack{
        stack:    []int{},
        minStack: []int{},
    }
}

// Push adds an element to the stack and updates the minStack.
func (this *MinStack) Push(x int) {
    this.stack = append(this.stack, x)
    if len(this.minStack) == 0 || x <= this.minStack[len(this.minStack)-1] {
        this.minStack = append(this.minStack, x)
    }
}

// Pop removes the top element from the stack and updates the minStack.
func (this *MinStack) Pop() {
    if len(this.stack) > 0 {
        top := this.stack[len(this.stack)-1]
        this.stack = this.stack[:len(this.stack)-1]
        if top == this.minStack[len(this.minStack)-1] {
            this.minStack = this.minStack[:len(this.minStack)-1]
        }
    }
}

// Top retrieves the top element of the stack.
func (this *MinStack) Top() int {
    if len(this.stack) > 0 {
        return this.stack[len(this.stack)-1]
    }
    return -1 // or any appropriate error value
}

// GetMin retrieves the minimum element in the stack.
func (this *MinStack) GetMin() int {
    if len(this.minStack) > 0 {
        return this.minStack[len(this.minStack)-1]
    }
    return -1 // or any appropriate error value
}

func main() {
    // Example usage:
    obj := Constructor()
    obj.Push(1)
    obj.Push(2)
    obj.Push(-1)
    fmt.Println("Top element:", obj.Top())      // Output: -1
    fmt.Println("Minimum element:", obj.GetMin()) // Output: -1
    obj.Pop()
    fmt.Println("Top element:", obj.Top())      // Output: 2
    fmt.Println("Minimum element:", obj.GetMin()) // Output: 1
}

Explanation of the Code:

1. Constructor:

• We initialize two empty slices: stack (the main stack to store elements) and minStack (to store the minimum element at each level of the stack).

1. Push:

• When we push an element x, we first add it to the stack. Then, if x is smaller than or equal to the current minimum (top of minStack), we also add x to minStack.

1. Pop:

• We pop the top element from the stack. If the popped element is equal to the current minimum (top of minStack), we also pop from minStack.

1. Top:

• We return the top element of the stack.

1. GetMin:

• We return the top element of the minStack, which always holds the minimum value of the stack.

Time and Space Complexity

OperationComplexityPushO(1)PopO(1)TopO(1)GetMinO(1)

• Time Complexity:
• All operations (push, pop, top, and getMin) run in constant time O(1) because we perform only one action (either append or pop) on the stacks for each operation.
• Space Complexity:
• The space complexity is O(n), where n is the number of elements in the stack. This is because we are maintaining two stacks, both of which can grow up to n elements.

Example

Input:

go

obj := Constructor()
obj.Push(1)
obj.Push(2)
obj.Push(-1)
fmt.Println("Top element:", obj.Top())      // Output: -1
fmt.Println("Minimum element:", obj.GetMin()) // Output: -1
obj.Pop()
fmt.Println("Top element:", obj.Top())      // Output: 2
fmt.Println("Minimum element:", obj.GetMin()) // Output: 1

Output:

yaml

Top element: -1
Minimum element: -1
Top element: 2
Minimum element: 1

Explanation:

• After pushing 1, 2, and -1 onto the stack, Top() returns -1 and GetMin() also returns -1.
• After popping the top element (-1), Top() returns 2, and GetMin() now returns 1 since 1 is the minimum element in the stack.

Conclusion

LeetCode 155 asks us to implement a stack that efficiently supports operations to find the minimum element. By using an auxiliary stack (minStack) to track the minimum element at each level, we can ensure that all operations—push, pop, top, and getMin—are performed in constant time O(1). This approach efficiently handles the problem constraints and is optimal for solving this task.