Minimum stack

Minimum in a Stack (Modified Stack)

A stack is a linear data structure where elements are added or removed only from the top. It supports operations like push, pop, and top. However, a traditional stack cannot efficiently track the smallest (minimum) element. To find the minimum in such a stack, you would need to scan all elements, resulting in a time complexity of (O(n)).

---

Why is Finding the Minimum Challenging in a Traditional Stack?

When using a traditional stack, removing an element causes us to lose track of the state of the stack at that point, including information about the minimum.

Example:

• Push elements: (5,3,2)
  • Minimum is (2).
• Pop (2):
  • Now, you need to rescan the stack ([5,3]) to determine the new minimum ((3)).

This rescanning process is inefficient and becomes problematic if minimum queries are frequent.

---

Modified Stack : Tracking the Minimum Efficiently

To overcome this, we can modify the stack to track the minimum element in constant time (\O(1)), while still performing push and pop operations in (O(1)).

The idea is to store additional information with each element: the smallest value in the stack at that point. Every entry in the stack is stored as a pair:

• First value: The element itself.
• Second value: The minimum of the stack from this element downwards.

This ensures that the second value of the top pair always holds the current minimum of the stack.

---

Operations

1. Push Operation (Add Element)

When adding a new element:

• Compare the new element with the current minimum (from the top pair’s second value).
• Store the smaller value as the new minimum alongside the element.

Code Example:

int new_min = st.empty() ? new_elem : min(new_elem, st.top().second);
st.push({new_elem, new_min});

2. Pop Operation (Remove Element)

When removing an element:

• Simply remove the top pair.
• The next minimum is already tracked in the second value of the new top pair.

Code Example:

st.pop();

3. Finding the Minimum

To retrieve the smallest element in the stack:

• Access the second value of the top pair.

Code Example:

int minimum = st.top().second;

---

Advantages of the Modified Stack

1. Constant-Time Minimum Queries:
   
   All operations—push, pop, and minimum—are performed in (O(1)), making this approach highly efficient.

2. Space Efficiency:
   
   The modified stack only requires storing an additional integer (minimum) with each element, ensuring minimal overhead.

---

Example Walkthrough

Here’s a step-by-step demonstration:

1. Initial Stack (Empty):

1. Push (5):
   • Minimum is (5) (only element).

1. Push (3):
   • Minimum updates to (3).

1. Push (2):
   • Minimum updates to (2).

1. Find Minimum:

   • Access (st.top().second), which is (2).

2. Pop (2):

   • Minimum updates to (3).
   • Stack after pop:

---

Why This Works

The key idea behind this approach is that each element stores the minimum seen so far. This way:

• Even if the current minimum is removed (popped), the previous minimum is already stored in the remaining stack.

By maintaining this additional data, the stack efficiently handles frequent minimum queries.

---

Conclusion

The modified stack provides a powerful enhancement to the traditional stack by enabling (O(1)) minimum queries. This approach is particularly useful in scenarios like:

• Competitive programming, where both efficiency and simplicity are crucial.
• Real-time systems, where frequent queries must be resolved quickly.

This design strikes an excellent balance between performance and space efficiency, making it a practical solution for problems involving minimum tracking in stacks.

---

📖 Sources:
I also referred to Sources: CP-Algorithms
for insights and explanations on modified stacks. A great resource for those looking to dive deeper into data structures!

Comments

[Ryo Muta]

Thank you for the introduction! It seems like a great idea with potential for flexibility, such as changing the pair values to the maximum or other values.

[vivekvohra]

You're absolutely right! By modifying the additional stored value (eg. tracking the maximum instead of the minimum or even other metrics like a running sum), you can adapt this idea to suit different problem requirements.