🟢 Data Structures: Implement a Min Stack

[stemaway]

Data Structures: Implement a Min Stack

Difficulty: Easy

---

Problem Statement

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• push(val) pushes the element val onto the stack.
• pop() removes the element on the top of the stack.
• top() gets the top element.
• get_min() retrieves the minimum element in the stack.

---

Implementation Details

Implement the following class:

class MinStack:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        pass  # Your implementation here

    def push(self, val: int) -> None:
        """
        Push element val onto stack.
        """
        pass  # Your implementation here

    def pop(self) -> None:
        """
        Removes the element on top of the stack.
        """
        pass  # Your implementation here

    def top(self) -> int:
        """
        Get the top element.
        """
        pass  # Your implementation here

    def get_min(self) -> int:
        """
        Retrieve the minimum element in the stack.
        """
        pass  # Your implementation here

Constraints

• Values Pushed: All integer values are in the range ([-10^5, 10^5]).
• Operations: A total of up to (10^4) operations will be performed.
• No Underflow: Pop and top operations will not be called on an empty stack.

---

Example Usage

min_stack = MinStack()
min_stack.push(-2)
min_stack.push(0)
min_stack.push(-3)
print(min_stack.get_min())  # Expected Output: -3
min_stack.pop()
print(min_stack.top())      # Expected Output: 0
print(min_stack.get_min())  # Expected Output: -2

---

Test Cases

def test_min_stack():
    # Test Case 1: Basic functionality
    min_stack = MinStack()
    min_stack.push(1)
    min_stack.push(2)
    min_stack.push(-1)
    assert min_stack.get_min() == -1
    min_stack.pop()
    assert min_stack.get_min() == 1

    # Test Case 2: All elements are the same
    min_stack = MinStack()
    min_stack.push(0)
    min_stack.push(0)
    min_stack.push(0)
    assert min_stack.get_min() == 0
    min_stack.pop()
    assert min_stack.get_min() == 0

    # Test Case 3: Increasing order
    min_stack = MinStack()
    min_stack.push(1)
    min_stack.push(2)
    min_stack.push(3)
    assert min_stack.get_min() == 1

    # Test Case 4: Decreasing order
    min_stack = MinStack()
    min_stack.push(3)
    min_stack.push(2)
    min_stack.push(1)
    assert min_stack.get_min() == 1
    min_stack.pop()
    assert min_stack.get_min() == 2

    # Test Case 5: Single element
    min_stack = MinStack()
    min_stack.push(-1)
    assert min_stack.top() == -1
    assert min_stack.get_min() == -1

    print("All test cases pass!")

---

Expected Solution Approach

To support retrieving the minimum element in constant time, we need to maintain the current minimum as we perform push and pop operations.

Algorithm Steps

1. Use Two Stacks:

   • Main Stack: Stores all the pushed values.
   • Min Stack: Keeps track of the minimum values.

2. Push Operation:

   • Push the value onto the main stack.
   • If the min stack is empty or the new value is less than or equal to the current minimum, push it onto the min stack.

3. Pop Operation:

   • Pop the value from the main stack.
   • If the popped value is equal to the current minimum, pop it from the min stack as well.

4. Top Operation:

   • Return the top value from the main stack.

5. Get Min Operation:

   • Return the top value from the min stack.

Time Complexity

• Time Complexity: (O(1)) per operation.
• Space Complexity: (O(N)), where (N) is the number of elements pushed onto the stack.

---

Implementation Hint

Here’s a skeleton to help you start:

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:
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()

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

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

---

Learning Objectives

1. Understand Stack Data Structures:

   • Implement basic stack operations.
   • Utilize additional stacks to maintain supplementary information.

2. Optimize for Constant Time Operations:

   • Design algorithms that perform required operations in (O(1)) time.
   • Balance time and space complexity.

3. Handle Edge Cases:

   • Consider scenarios where multiple minimum values exist.
   • Ensure correct behavior when elements are pushed or popped.

4. Apply Object-Oriented Programming:

   • Encapsulate data and behavior within a class.
   • Understand class methods and instance variables.

---

Real-World Applications

• Browser History Management: Backtracking through previous pages with quick access to the earliest page.
• Undo Mechanisms: Reversing actions in software applications.
• Expression Evaluation: Computing values of arithmetic expressions.
• Algorithm Design: Designing data structures that maintain additional properties (e.g., min, max) efficiently.

---