Implement Min Stack

Intuition:

In a usual stack data structure, there is no method to get the minimum element present in the stack in constant time. This can be overcome, if all the numbers are stored in pairs with their current minimum element. This way, the stack will not only able to perform the previous methods in constant time, but also perform the getMin() method in constant time.

Note: The stack will store the following pair: {element, current minimum}

Approach:

A stack of pairs is used. Each pair contains the element itself and the minimum element at the time the element was pushed onto the stack. The MinStack class is initialized with an empty stack.
- Push Operation: When a new element is pushed, it is compared with the current minimum. The new element and the updated minimum are stored as a pair and pushed onto the stack.
- Pop Operation: The top element (which is a pair) is removed from the stack.
- Top Operation: The top element of the stack is accessed to get the actual value (first component) stored.
- GetMin Operation: The second value of the pair at the top of the stack, which represents the minimum element at that point, is accessed.

Dry Run:

1 / 9

Solution:

#include <bits/stdc++.h>
using namespace std;

// Class to implement Minimum Stack
class MinStack {
private:
    // Initialize a stack
    stack <pair<int,int>> st;
    
public:
    
    // Empty Constructor
    MinStack() {
    }
    
    // Method to push a value in stack
    void push(int value) {
        
        // If stack is empty
        if(st.empty()) {
            
            // Push current value as minimum
            st.push( {value, value} );
            return;
        }
        
        // Update the current minimum 
        int mini = min(getMin(), value);
        
        // Add the pair to the stack
        st.push({value, mini});
    }
    
    // Method to pop a value from stack
    void pop() {
        // Using in-built pop method
        st.pop(); 
    }
    
    // Method to get the top of stack
    int top() {
        // Return the top value
        return st.top().first;
    }
    
    // Method to get the minimum in stack
    int getMin() {
        // Return the minimum
        return st.top().second;
    }
};

int main() {
    MinStack s;
    
    // Function calls
    s.push(-2);
    s.push(0);
    s.push(-3);
    cout << s.getMin() << " ";
    s.pop();
    cout << s.top() << " ";
    s.pop();
    cout << s.getMin();
    
    return 0;
}
import java.util.*;

// Class to implement Minimum Stack
class MinStack {
    // Initialize a stack
    private Stack<int[]> st;

    // Empty Constructor
    public MinStack() {
        st = new Stack<>();
    }

    // Method to push a value in stack
    public void push(int value) {
        // If stack is empty
        if (st.isEmpty()) {
            // Push current value as minimum
            st.push(new int[]{value, value});
            return;
        }

        // Update the current minimum
        int mini = Math.min(getMin(), value);

        // Add the pair to the stack
        st.push(new int[]{value, mini});
    }

    // Method to pop a value from stack
    public void pop() {
        // Using in-built pop method
        st.pop();
    }

    // Method to get the top of stack
    public int top() {
        // Return the top value
        return st.peek()[0];
    }

    // Method to get the minimum in stack
    public int getMin() {
        // Return the minimum
        return st.peek()[1];
    }
}

public class Main {
    public static void main(String[] args) {
        MinStack s = new MinStack();

        // Function calls
        s.push(-2);
        s.push(0);
        s.push(-3);
        System.out.print(s.getMin() + " ");
        s.pop();
        System.out.print(s.top() + " ");
        s.pop();
        System.out.print(s.getMin());
    }
}
class MinStack:
    # Empty Constructor
    def __init__(self):
        # Initialize a stack
        self.st = []

    # Method to push a value in stack
    def push(self, value):
        # If stack is empty
        if not self.st:
            # Push current value as minimum
            self.st.append((value, value))
            return

        # Update the current minimum
        mini = min(self.getMin(), value)

        # Add the pair to the stack
        self.st.append((value, mini))

    # Method to pop a value from stack
    def pop(self):
        # Using in-built pop method
        self.st.pop()

    # Method to get the top of stack
    def top(self):
        # Return the top value
        return self.st[-1][0]

    # Method to get the minimum in stack
    def getMin(self):
        # Return the minimum
        return self.st[-1][1]

if __name__ == "__main__":
    s = MinStack()
    
    # Function calls
    s.push(-2)
    s.push(0)
    s.push(-3)
    print(s.getMin(), end=" ")
    s.pop()
    print(s.top(), end=" ")
    s.pop()
    print(s.getMin())
// Class to implement Minimum Stack
class MinStack {
    // Initialize a stack
    constructor() {
        this.st = [];
    }

    // Method to push a value in stack
    push(value) {
        // If stack is empty
        if (this.st.length === 0) {
            // Push current value as minimum
            this.st.push([value, value]);
            return;
        }

        // Update the current minimum
        const mini = Math.min(this.getMin(), value);

        // Add the pair to the stack
        this.st.push([value, mini]);
    }

    // Method to pop a value from stack
    pop() {
        // Using in-built pop method
        this.st.pop();
    }

    // Method to get the top of stack
    top() {
        // Return the top value
        return this.st[this.st.length - 1][0];
    }

    // Method to get the minimum in stack
    getMin() {
        // Return the minimum
        return this.st[this.st.length - 1][1];
    }
}

// Main function to demonstrate the MinStack functionality
const s = new MinStack();

// Function calls
s.push(-2);
s.push(0);
s.push(-3);
console.log(s.getMin() + " ");
s.pop();
console.log(s.top() + " ");
s.pop();
console.log(s.getMin());

Complexity Analysis:

Time Complexity: O(1) All the operations take constant time.

Space Complexity: O(2*N) (where N is the total number of calls made for push operation)
All the numbers are stored in pairs leading to a stack space of O(2*N).

Intuition:

To efficiently keep track of the minimum element in the stack at all times while maintaining constant time complexity for each operation, a clever approach is needed. This can be achieved by modifying the values stored in the stack when a new minimum is encountered. Instead of storing pairs or auxiliary stacks, we store a specially calculated value that allows us to track the minimum.

Approach:

Use a stack to store elements. Maintain a variable to keep track of the current minimum value.
Push Operation:
- If the stack is empty, push the value and set it as the current minimum.
- If the value is greater than or equal to the current minimum, push the value.
- If the value is less than the current minimum, push a modified value calculated using the new value and update the current minimum.
Pop Operation:
- If the stack is empty, do nothing. Otherwise, Retrieve and pop the top value.
- If the popped value indicates it was used to store a new minimum, update the current minimum using the retrieved value.
Top Operation:
- If the stack is empty, return -1 indicating the stack is empty.
- Retrieve the top value. If the top value is greater than or equal to the current minimum, return it.
- If the top value indicates it was used to store a new minimum, return the current minimum.
GetMin Operation: Simply return the current minimum.

Dry Run:

1 / 9

Solution:

#include <bits/stdc++.h>
using namespace std;

// Class to implement Minimum Stack
class MinStack {
private:
    // Initialize a stack
    stack <int> st;
    // To store the minimum value 
    int mini;
    
public:
    
    // Empty Constructor
    MinStack() {
    }
    
    // Method to push a value in stack
    void push(int value) {
        
        // If stack is empty
        if(st.empty()) {
            //Update the minimum value
            mini = value;
            
            // Push current value as minimum
            st.push( value );
            return;
        }
        
        // If the value is greater than the minimum
        if(value > mini) {
            st.push(value);
        }
        else {
            // Add the modified value to stack
            st.push(2 * value - mini);
            // Update the minimum
            mini = value;
        }
    }
    
    // Method to pop a value from stack
    void pop() {
        // Base case
        if(st.empty()) return;
        
        // Get the top
        int x = st.top();
        st.pop(); // Pop operation
        
        // If the modified value was added to stack
        if(x < mini) {
            // Update the minimum
            mini = 2 * mini - x;
        }
    }
    
    // Method to get the top of stack
    int top() {
        // Base case
        if(st.empty()) return -1;
        
        // Get the top
        int x = st.top();
        
        // Returnn top if minimum is less than the top
        if(mini < x) return x;
        
        //Otherwise return mini
        return mini;
    }
    
    // Method to get the minimum in stack
    int getMin() {
        // Return the minimum
        return mini;
    }
};

int main() {
    MinStack s;
    
    // Function calls
    s.push(-2);
    s.push(0);
    s.push(-3);
    cout << s.getMin() << " ";
    s.pop();
    cout << s.top() << " ";
    s.pop();
    cout << s.getMin();
    
    return 0;
}
import java.util.Stack;

// Class to implement Minimum Stack
class MinStack {
    private Stack<Integer> st;
    private int mini;

    // Empty Constructor
    public MinStack() {
        st = new Stack<>();
    }

    // Method to push a value in stack
    public void push(int value) {
        // If stack is empty
        if (st.isEmpty()) {
            // Update the minimum value
            mini = value;

            // Push current value as minimum
            st.push(value);
            return;
        }

        // If the value is greater than the minimum
        if (value > mini) {
            st.push(value);
        } else {
            // Add the modified value to stack
            st.push(2 * value - mini);
            // Update the minimum
            mini = value;
        }
    }

    // Method to pop a value from stack
    public void pop() {
        // Base case
        if (st.isEmpty()) return;

        // Get the top
        int x = st.pop();

        // If the modified value was added to stack
        if (x < mini) {
            // Update the minimum
            mini = 2 * mini - x;
        }
    }

    // Method to get the top of stack
    public int top() {
        // Base case
        if (st.isEmpty()) return -1;

        // Get the top
        int x = st.peek();

        // Return top if minimum is less than the top
        if (mini < x) return x;

        // Otherwise return mini
        return mini;
    }

    // Method to get the minimum in stack
    public int getMin() {
        // Return the minimum
        return mini;
    }
}

public class Main {
    public static void main(String[] args) {
        MinStack s = new MinStack();

        // Function calls
        s.push(-2);
        s.push(0);
        s.push(-3);
        System.out.print(s.getMin() + " ");
        s.pop();
        System.out.print(s.top() + " ");
        s.pop();
        System.out.print(s.getMin());
    }
}
class MinStack:
    def __init__(self):
        # Initialize a stack
        self.st = []
        # To store the minimum value
        self.mini = None

    # Method to push a value in stack
    def push(self, value):
        # If stack is empty
        if not self.st:
            # Update the minimum value
            self.mini = value

            # Push current value as minimum
            self.st.append(value)
            return

        # If the value is greater than the minimum
        if value > self.mini:
            self.st.append(value)
        else:
            # Add the modified value to stack
            self.st.append(2 * value - self.mini)
            # Update the minimum
            self.mini = value

    # Method to pop a value from stack
    def pop(self):
        # Base case
        if not self.st:
            return

        # Get the top
        x = self.st.pop()

        # If the modified value was added to stack
        if x < self.mini:
            # Update the minimum
            self.mini = 2 * self.mini - x

    # Method to get the top of stack
    def top(self):
        # Base case
        if not self.st:
            return -1

        # Get the top
        x = self.st[-1]

        # Return top if minimum is less than the top
        if self.mini < x:
            return x

        # Otherwise return mini
        return self.mini

    # Method to get the minimum in stack
    def getMin(self):
        # Return the minimum
        return self.mini


if __name__ == "__main__":
    s = MinStack()

    # Function calls
    s.push(-2)
    s.push(0)
    s.push(-3)
    print(s.getMin(), end=" ")
    s.pop()
    print(s.top(), end=" ")
    s.pop()
    print(s.getMin())
class MinStack {
    constructor() {
        // Initialize a stack
        this.st = [];
        // To store the minimum value
        this.mini = null;
    }

    // Method to push a value in stack
    push(value) {
        // If stack is empty
        if (this.st.length === 0) {
            // Update the minimum value
            this.mini = value;

            // Push current value as minimum
            this.st.push(value);
            return;
        }

        // If the value is greater than the minimum
        if (value > this.mini) {
            this.st.push(value);
        } else {
            // Add the modified value to stack
            this.st.push(2 * value - this.mini);
            // Update the minimum
            this.mini = value;
        }
    }

    // Method to pop a value from stack
    pop() {
        // Base case
        if (this.st.length === 0) return;

        // Get the top
        let x = this.st.pop();

        // If the modified value was added to stack
        if (x < this.mini) {
            // Update the minimum
            this.mini = 2 * this.mini - x;
        }
    }

    // Method to get the top of stack
    top() {
        // Base case
        if (this.st.length === 0) return -1;

        // Get the top
        let x = this.st[this.st.length - 1];

        // Return top if minimum is less than the top
        if (this.mini < x) return x;

        // Otherwise return mini
        return this.mini;
    }

    // Method to get the minimum in stack
    getMin() {
        // Return the minimum
        return this.mini;
    }
}

// Example usage
let s = new MinStack();

// Function calls
s.push(-2);
s.push(0);
s.push(-3);
console.log(s.getMin(), " ");
s.pop();
console.log(s.top(), " ");
s.pop();
console.log(s.getMin());

Complexity Analysis:

Time Complexity: O(1) All the operations take constant time.

Space Complexity: O(N) (where N is the total number of calls made for push operation)
As only one value per element is stored in the stack.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code