MinStack Design

This problem requires designing a stack data structure with the additional functionality of retrieving the minimum element in O(1) time complexity.

1. Naive Approach

A straightforward approach is to use a standard stack to store the elements and, when getMin() is called, iterate through the entire stack to find the minimum element. This approach is simple to implement but doesn't meet the O(1) time complexity requirement for getMin().

Code (Python)

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

    def push(self, val: int) -> None:
        self.stack.append(val)

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        if not self.stack:
            return None  # Or handle empty case appropriately
        return min(self.stack)

Time and Space Complexity

• Time Complexity:
  • push(): O(1)
  • pop(): O(1)
  • top(): O(1)
  • getMin(): O(n), where n is the number of elements in the stack.
• Space Complexity: O(n), where n is the number of elements in the stack.

2. Optimal Approach: Using an Auxiliary Stack

To achieve O(1) time complexity for getMin(), we can use an auxiliary stack to keep track of the minimum elements. This auxiliary stack will store the minimum element seen so far whenever a new element is pushed onto the main stack.

Algorithm

1. push(val):
   • Push the val onto the main stack.
   • If the auxiliary stack is empty or val is less than or equal to the current minimum (top of the auxiliary stack), push val onto the auxiliary stack.
2. pop():
   • If the top element of the main stack is equal to the top element of the auxiliary stack, pop from the auxiliary stack.
   • Pop from the main stack.
3. top():
   • Return the top element of the main stack.
4. getMin():
   • Return the top element of the auxiliary stack.

Code (Python)

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        if self.stack[-1] == self.min_stack[-1]:
            self.min_stack.pop()
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

Time and Space Complexity

• Time Complexity:
  • push(): O(1)
  • pop(): O(1)
  • top(): O(1)
  • getMin(): O(1)
• Space Complexity: O(n), where n is the number of elements in the stack. In the worst-case scenario (e.g., monotonically decreasing sequence), the auxiliary stack will store all the elements.

3. Edge Cases

• Empty Stack:
  • When the stack is empty and getMin() or top() is called, you can either return None or raise an exception, as stated in the problem description, these methods will always be called on non-empty stacks.
• Duplicate Minimum Values:
  • The auxiliary stack handles duplicate minimum values correctly because we push a new minimum value onto the auxiliary stack only if the current value is less than or equal to the current minimum.

4. Optimized Space Complexity

Instead of using an auxiliary stack that could take O(N) space, we could track the minimum value and store the difference between the current value and the minimum value.

Algorithm

1. push(val):
   • If the stack is empty, then the minimum value is equal to val.
   • Append the difference between val and min_val.
2. pop():
   • If the difference is negative, then the minimum value needs to be updated to min_val - difference.
   • Pop the top element.
3. top():
   • If the difference is positive, then return min_val + the difference, else return the min_val
4. getMin():
   • Return the minimum value.

Code (Python)

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_val = None

    def push(self, val: int) -> None:
        if not self.stack:
            self.min_val = val
            self.stack.append(0)
        else:
            diff = val - self.min_val
            self.stack.append(diff)
            if diff < 0:
                self.min_val = val

    def pop(self) -> None:
        diff = self.stack.pop()
        if diff < 0:
            self.min_val = self.min_val - diff

    def top(self) -> int:
        diff = self.stack[-1]
        if diff > 0:
            return self.min_val + diff
        else:
            return self.min_val

    def getMin(self) -> int:
        return self.min_val

Time and Space Complexity

• Time Complexity:
  • push(): O(1)
  • pop(): O(1)
  • top(): O(1)
  • getMin(): O(1)
• Space Complexity: O(n), where n is the number of elements in the stack.