Stack simulation / design (Stack Sub-pattern)
Simulate a process where each new item interacts only with the latest survivor: it may cancel it, be cancelled, or be pushed. Design questions keep extra info in each stack entry.
- ›
"collide", "explode", "cancel"
- ›
file paths with
.and.. - ›
"design a stack that also returns the minimum in O(1)"
Write the interaction rule first: which pairs fight (only → then ←), what .. does on an empty stack. For design, store the extra answer with each entry ((value, min so far)) so a pop automatically restores the old answer. Notice how the popping grows across the three questions: in Min Stack only the caller pops; in Simplify Path one .. pops one folder; in Asteroid Collision one asteroid can pop many in a while loop — the same move Monotonic Stack is built on.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Min StackWalkthroughMediumBasic Anchor·LeetCode #155
- 2Simplify PathWalkthroughMediumSlight Variation·LeetCode #71
- 3Asteroid CollisionWalkthroughMediumMedium·LeetCode #735
Template
// Asteroid Collision: the new item fights the latest survivor until one side wins.
vector<int> asteroidCollision(vector<int>& asteroids) {
vector<int> st; // survivors so far, as a stack
for (int a : asteroids) {
bool alive = true;
while (alive && a < 0 && !st.empty() && st.back() > 0) { // only → ← collide
if (st.back() < -a) st.pop_back(); // top explodes, keep fighting
else {
if (st.back() == -a) st.pop_back(); // equal: both explode
alive = false; // new one explodes
}
}
if (alive) st.push_back(a);
}
return st;
}