Min Stack

Clarify the problem:

• The problem requires us to design a stack that supports push, pop, top, and getMin operations.
• The push operation adds an element to the top of the stack.
• The pop operation removes the top element from the stack.
• The top operation returns the top element without removing it.
• The getMin operation returns the minimum element in the stack.
• All operations must be performed in constant time.
• We need to implement a class called MinStack that supports these operations.

Analyze the problem:

• Input: None for initialization, integers for push and pop operations.
• Output: None for push, pop, and top operations, integer for getMin operation.
• Constraints:
  • The total number of operations will be at most 10^4.
  • Values in the stack will be valid 32-bit signed integers.

Design an algorithm:

• We can solve this problem by using two stacks: one stack to store the elements and another stack to keep track of the minimum values.
• Initialize two empty stacks: one for elements and another for minimum values.
• For the push operation:
  • Append the element to the elements stack.
  • If the minimum values stack is empty or the element is smaller than or equal to the top element of the minimum values stack, append the element to the minimum values stack.
• For the pop operation:
  • Pop the top element from the elements stack.
  • If the popped element is equal to the top element of the minimum values stack, pop the top element from the minimum values stack as well.
• For the top operation:
  • Return the top element of the elements stack.
• For the getMin operation:
  • Return the top element of the minimum values stack.

Explain your approach:

• We will implement the MinStack class that supports the required operations using two stacks: one for elements and another for minimum values.
• In the push operation, we append the element to the elements stack and update the minimum values stack if necessary.
• In the pop operation, we pop the top element from the elements stack and check if it matches the top element of the minimum values stack to maintain the minimum values accurately.
• In the top operation, we return the top element of the elements stack.
• In the getMin operation, we return the top element of the minimum values stack, which represents the minimum value in the stack.

Write clean and readable code:

python

class MinStack:
    def __init__(self):
        self.elements = []
        self.min_values = []

    def push(self, val):
        self.elements.append(val)
        if not self.min_values or val <= self.min_values[-1]:
            self.min_values.append(val)

    def pop(self):
        popped = self.elements.pop()
        if popped == self.min_values[-1]:
            self.min_values.pop()

    def top(self):
        return self.elements[-1]

    def getMin(self):
        return self.min_values[-1]

# Test the MinStack implementation
minStack = MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
print(minStack.getMin())  # Output: -3
minStack.pop()
print(minStack.top())  # Output: 0
print(minStack.getMin())  # Output: -2

Test your code:

• We test the code with the following cases:
  1. Push three elements (-2, 0, -3), and check the minimum value using the getMin operation.
  2. Pop the top element, check the new top element, and check the minimum value using the getMin operation.
  3. Check the new top element and the minimum value using the getMin operation.
• We chose these test cases to cover the basic functionality of the MinStack class and verify that it correctly handles push, pop, top, and getMin operations.

Optimize if necessary:

• The provided solution has a time complexity of O(1) for all operations: push, pop, top, and getMin.
• The space complexity is O(N), where N is the number of elements pushed into the stack.
• The solution does not require further optimization.

Handle error cases:

• The code assumes that the input values for push and pop operations are valid integers.
• If pop or top operations are called on an empty stack, the code will throw an error. However, in LeetCode, this case is not expected to occur.

Discuss complexity analysis:

• Let N be the number of elements pushed into the stack.
• The time complexity for all operations (push, pop, top, and getMin) is O(1).
• The space complexity is O(N) to store the elements and the minimum values in separate stacks.
• The solution is efficient and performs well for a stack with a large number of elements.