Question

Java

PROBLEM STATEMENT: In today’s Lab we will explore ways to design a Stack with O(1) lookup time of the Minimum element. You will solve the problem as stated below:

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.

• push(int val) pushes the element val onto the stack.

• pop() removes the element on the top of the stack.

• top() gets the top element of the stack.

• getMin() retrieves the minimum element in the stack.

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

Please include comments and details about time complexity!

Answer 1

To implement a MinStack with O(1) operations in Java, two stacks are utilized: one for all elements and one for tracking minimum values. The push and pop operations manage both stacks to ensure the minimum is always accessible at the top of the min stack, providing constant time retrieval.

Step-by-step explanation:

Designing a MinStack in Java

To create a MinStack with O(1) time complexity for each operation, you need to utilize two stacks: one for storing all elements (the main stack) and one to keep track of the minimum elements (the min stack). Each time you push a new value onto the main stack, compare it with the top of the min stack and push the lower of the two onto the min stack. When popping from the main stack, also pop from the min stack to keep both in sync.

// MinStack class design

public class MinStack {
private Stack stack = new Stack<>();
private Stack minStack = new Stack<>();

public MinStack() {}

public void push(int val) {
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
stack.push(val);
}

public void pop() {
if (stack.peek().equals(minStack.peek())) {
minStack.pop();
}
stack.pop();
}

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

public int getMin() {
return minStack.peek();
}
}

The push and pop operations adjust the min stack alongside the main stack to maintain the minimum at the top. The top function simply returns the top element of the main stack without modification, whereas getMin returns the top of the min stack, which is the minimum element of the main stack.