Min Stack

This question is part of NeetCode150 series.

PROBLEM 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.

leetcode

SOLUTION

Instead of pushing just the values, we will keep a track of the currentMin and push it along with the value to be added to the stack!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class MinStack {

    private Stack<int[]> stack = new Stack<>();

    public MinStack() {
        
    }

    public void push(int val) {
        
        if(stack.isEmpty()){
            stack.push(new int[]{val, val});
            return;
        }
        
        int currentMin = Math.min(val, stack.peek()[1]);
        stack.push(new int[]{val, currentMin});
    }

    public void pop() {
        stack.pop();
    }

    public int top() {
        return stack.peek()[0];
    }

    public int getMin() {
        return stack.peek()[1];
    }
}