HomeLeetcode155. Min Stack - Leetcode Solutions
Leetcode

155. Min Stack – Leetcode Solutions

Declan Clarke

Description

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

Implement the MinStack class:

  • MinStack() initializes the stack object.
  • void push(int val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Examples:

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

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

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Solution in Python

To implement a stack that supports push, pop, top, and retrieving the minimum element in constant time, we can use an auxiliary stack to keep track of the minimum values.

  1. Main Stack: This stack will hold all the values pushed onto the stack.
  2. Min Stack: This auxiliary stack will hold the minimum values. Every time a new value is pushed onto the main stack, we compare it with the current minimum (the top of the min stack). If the new value is smaller or equal, we also push it onto the min stack. When we pop from the main stack, we also pop from the min stack if the popped value is the same as the top of the min stack.
Python
class MinStack:

    def __init__(self):
        # Initialize the main stack and the auxiliary min stack
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        # Push the value onto the main stack
        self.stack.append(val)
        # If the min stack is empty or the new value is less than or equal to the current minimum,
        # push the value onto the min stack as well
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        # Pop the value from the main stack
        if self.stack:
            val = self.stack.pop()
            # If the popped value is the same as the top of the min stack, pop it from the min stack as well
            if val == self.min_stack[-1]:
                self.min_stack.pop()

    def top(self) -> int:
        # Return the top value of the main stack
        if self.stack:
            return self.stack[-1]
        return None

    def getMin(self) -> int:
        # Return the top value of the min stack, which is the minimum value in the main stack
        if self.min_stack:
            return self.min_stack[-1]
        return None

Explanation of Methods:

  1. __init__ Method:
    • Initializes two stacks: self.stack for holding all the values and self.min_stack for tracking the minimum values.
  2. push Method:
    • Pushes the given value val onto the main stack.
    • If the min stack is empty or val is less than or equal to the current minimum (top of the min stack), it also pushes val onto the min stack.
  3. pop Method:
    • Pops the value from the main stack.
    • If the popped value is the same as the top of the min stack, it also pops from the min stack to maintain the correct minimum.
  4. top Method:
    • Returns the top value of the main stack without removing it.
  5. getMin Method:
    • Returns the top value of the min stack, which represents the minimum value in the main stack.

This design ensures that all operations (push, pop, top, getMin) run in constant time O(1).

Solution in Javascript

JavaScript
var MinStack = function() {
    // Initialize the main stack and the auxiliary min stack
    this.stack = [];
    this.minStack = [];
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
    // Push the value onto the main stack
    this.stack.push(val);
    // If the min stack is empty or the new value is less than or equal to the current minimum,
    // push the value onto the min stack as well
    if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
        this.minStack.push(val);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    // Pop the value from the main stack
    if (this.stack.length > 0) {
        let val = this.stack.pop();
        // If the popped value is the same as the top of the min stack, pop it from the min stack as well
        if (val === this.minStack[this.minStack.length - 1]) {
            this.minStack.pop();
        }
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    // Return the top value of the main stack
    if (this.stack.length > 0) {
        return this.stack[this.stack.length - 1];
    }
    return null; // Return null if the stack is empty
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    // Return the top value of the min stack, which is the minimum value in the main stack
    if (this.minStack.length > 0) {
        return this.minStack[this.minStack.length - 1];
    }
    return null; // Return null if the min stack is empty
};

Solution in Java

Java
import java.util.Stack;

class MinStack {

    // Main stack to store all values
    private Stack<Integer> stack;
    // Auxiliary stack to store minimum values
    private Stack<Integer> minStack;

    // Constructor to initialize the stacks
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    // Method to push a value onto the stack
    public void push(int val) {
        // Push the value onto the main stack
        stack.push(val);
        // If the min stack is empty or the new value is less than or equal to the current minimum,
        // push the value onto the min stack as well
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    // Method to pop the value from the stack
    public void pop() {
        // Pop the value from the main stack
        if (!stack.isEmpty()) {
            int val = stack.pop();
            // If the popped value is the same as the top of the min stack,
            // pop it from the min stack as well
            if (val == minStack.peek()) {
                minStack.pop();
            }
        }
    }

    // Method to get the top value of the stack
    public int top() {
        // Return the top value of the main stack
        if (!stack.isEmpty()) {
            return stack.peek();
        }
        return -1; // Return -1 if the stack is empty
    }

    // Method to get the minimum value in the stack
    public int getMin() {
        // Return the top value of the min stack, which is the minimum value in the main stack
        if (!minStack.isEmpty()) {
            return minStack.peek();
        }
        return -1; // Return -1 if the min stack is empty
    }
}

Solution in C#

C#
using System;
using System.Collections.Generic;

public class MinStack {

    // Main stack to store all values
    private Stack<int> stack;
    // Auxiliary stack to store minimum values
    private Stack<int> minStack;

    // Constructor to initialize the stacks
    public MinStack() {
        stack = new Stack<int>();
        minStack = new Stack<int>();
    }

    // Method to push a value onto the stack
    public void Push(int val) {
        // Push the value onto the main stack
        stack.Push(val);
        // If the min stack is empty or the new value is less than or equal to the current minimum,
        // push the value onto the min stack as well
        if (minStack.Count == 0 || val <= minStack.Peek()) {
            minStack.Push(val);
        }
    }

    // Method to pop the value from the stack
    public void Pop() {
        // Pop the value from the main stack
        if (stack.Count > 0) {
            int val = stack.Pop();
            // If the popped value is the same as the top of the min stack,
            // pop it from the min stack as well
            if (val == minStack.Peek()) {
                minStack.Pop();
            }
        }
    }

    // Method to get the top value of the stack
    public int Top() {
        // Return the top value of the main stack
        if (stack.Count > 0) {
            return stack.Peek();
        }
        return -1; // Return -1 if the stack is empty (or throw an exception based on your use case)
    }

    // Method to get the minimum value in the stack
    public int GetMin() {
        // Return the top value of the min stack, which is the minimum value in the main stack
        if (minStack.Count > 0) {
            return minStack.Peek();
        }
        return -1; // Return -1 if the min stack is empty (or throw an exception based on your use case)
    }
}

Related Post

Subscribe
Notify of

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com