Stack
Baseball Game
Replay a sequence of operations and return the final total score. Numbers add a score, "+" adds the sum of the last two, "D" doubles the last, "C" cancels (removes) the last. ["5","2","C","D","+"] → 30.
Stack, one operation at a time
- Number → push it onto the stack.
"+"→ push the sum of the top two."D"→ push double the top."C"→ pop the top off, it's cancelled.- Sum whatever's left on the stack at the end.
python
class Solution:
def calPoints(self, operations: List[str]) -> int:
stack = []
for op in operations:
if op == '+':
stack.append(stack[-1] + stack[-2])
elif op == 'D':
stack.append(stack[-1] * 2)
elif op == 'C':
stack.pop()
else:
stack.append(int(op))
return sum(stack)timeO(n)spaceO(n)
Valid Parentheses
Check whether a string of brackets s is properly matched and nested. "()[]{}" → True. "(]" → False.
Stack, match closers against the last opener
- Opening bracket → push it.
- Closing bracket → pop the stack and check it's the matching opener. Empty stack, or a mismatch → invalid.
- Everything closes out cleanly → the stack is empty at the end.
python
class Solution:
def isValid(self, s: str) -> bool:
hashmap = {
')': '(',
'}': '{',
']': '['
}
stk = []
for c in s:
if c not in hashmap:
stk.append(c)
else:
if not stk:
return False
popped = stk.pop()
if popped != hashmap[c]:
return False
return not stktimeO(n)spaceO(n)
Evaluate Reverse Polish Notation
Evaluate an arithmetic expression given in Reverse Polish (postfix) Notation. ["2","1","+","3","*"] → 9 ((2+1)*3).
Stack, apply each operator to the last two numbers
- Number → push it.
- Operator → pop the last two numbers, apply the operator, push the result back.
- Division truncates toward zero, not floor division, so a negative result rounds up (
ceil) instead of down. - One value left on the stack at the end, that's the answer.
python
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stk = []
for t in tokens:
if t in '+-*/':
b, a = stk.pop(), stk.pop()
if t == '+':
stk.append(a + b)
elif t == '-':
stk.append(a - b)
elif t == '*':
stk.append(a * b)
else:
division = a / b
if division < 0:
stk.append(ceil(division))
else:
stk.append(floor(division))
else:
stk.append(int(t))
return stk[0]timeO(n)spaceO(n)
Asteroid Collision
Asteroids move right (positive) or left (negative). Same size means both explode, otherwise the bigger one survives. Simulate all the collisions and return what's left. [5,10,-5] → [5,10].
Stack, resolve collisions as they happen
- Only a right-moving asteroid on the stack meeting a left-moving one can collide, so only enter the collision loop when the current asteroid moves left (
a < 0) and the top of the stack moves right. - Smaller one loses and disappears, equal sizes both disappear, the bigger one survives and keeps colliding with whatever's next on the stack.
- Whatever's left of the current asteroid, if anything survived, gets pushed on.
python
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
stack = []
for a in asteroids:
while stack and a < 0 and stack[-1] > 0:
diff = a + stack[-1]
if diff < 0:
stack.pop()
elif diff > 0:
a = 0
else:
a = 0
stack.pop()
if a:
stack.append(a)
return stacktimeO(n)spaceO(n)
Daily Temperatures
For each day, find how many days until a warmer temperature (0 if none comes). [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0].
Monotonic stack of unresolved days
- Keep a stack of
(temperature, index)pairs, for days still waiting on a warmer one. - New temperature beats the top of the stack → that day's wait is over. Pop it, record how many days it waited (
i - stk_i). Keep popping while the new temperature keeps beating the stack. - Push the current day on, it's now waiting too.
python
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
temps = temperatures
n = len(temps)
answer = [0] * n
stk = []
for i, t in enumerate(temps):
while stk and stk[-1][0] < t:
stk_t, stk_i = stk.pop()
answer[stk_i] = i - stk_i
stk.append((t, i))
return answertimeO(n)spaceO(n)
Online Stock Span
Design StockSpanner: each call to next(price) returns the span, how many consecutive days up to and including today the price has stayed less than or equal to today's. next(100), next(80), next(60), next(70), next(60), next(75), next(85) → 1, 1, 1, 2, 1, 4, 6.
Monotonic stack of (price, span) pairs
- Keep a stack of
(price, span)pairs, prices decreasing from bottom to top. - New price is
>=the top of the stack → that entry is now covered by today's price, fold its span into today's and pop it. Keep going while the stack keeps folding in. - Push
(price, span)for today, wherespanincludes everything just folded in, plus today itself.
python
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price: int) -> int:
span = 1
while self.stack and self.stack[-1][0] <= price:
span += self.stack[-1][1]
self.stack.pop()
self.stack.append((price, span))
return span
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)timeO(1) amortizedspaceO(n)
Car Fleet
Cars start at various positions heading to target at constant speeds. A faster car catches up to a slower one ahead and they merge into one fleet, capped at the slower speed. Count the fleets that arrive. target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3] → 3.
Sort by position, stack of arrival times
- Sort cars from closest to
targetto farthest, fleets can only form behind a car, never catch one ahead of it. - For each car, compute how long it'd take to reach
targetalone, and push that time. - The car just pushed arrives at the same time or sooner than the one ahead of it → it's caught up and merged into that fleet, pop it.
- What's left on the stack is one entry per fleet.
python
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
pair = [(p, s) for p, s in zip(position, speed)]
pair.sort(reverse=True)
stack = []
for p, s in pair: # Reverse Sorted Order
stack.append((target - p) / s)
if len(stack) >= 2 and stack[-1] <= stack[-2]:
stack.pop()
return len(stack)timeO(n log n)spaceO(n)
Simplify Path
Convert a Unix-style absolute path into its simplified canonical form. "/a/./b/../../c/" → "/c".
Stack, one path segment at a time
- Split on
/, building each segment up character by character. - Segment is
".."→ pop the last directory off, go up one level. - Segment is
"."or empty → skip it, doesn't change the path. - Anything else → push it as a real directory.
- Join what's left on the stack back together with
/.
python
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
cur = ""
for c in path + "/":
if c == "/":
if cur == "..":
if stack:
stack.pop()
elif cur != "" and cur != ".":
stack.append(cur)
cur = ""
else:
cur += c
return "/" + "/".join(stack)timeO(n)spaceO(n)
Decode String
Decode a string written as k[encoded_string], meaning the inner string repeats k times. "3[a]2[bc]" → "aaabcbc". Nesting is allowed: "3[a2[c]]" → "accaccacc".
Two stacks, push on [, pop and repeat on ]
- Digits build up the current repeat count
k. [→ push the string built so far and the count onto their stacks, then start fresh for what's inside the brackets.]→ pop the saved string and count, append the just-finished inner string repeatedktimes.- Anything else → append it to the current string.
python
class Solution:
def decodeString(self, s: str) -> str:
string_stack = []
count_stack = []
cur = ""
k = 0
for c in s:
if c.isdigit():
k = k * 10 + int(c)
elif c == "[":
string_stack.append(cur)
count_stack.append(k)
cur = ""
k = 0
elif c == "]":
temp = cur
cur = string_stack.pop()
count = count_stack.pop()
cur += temp * count
else:
cur += c
return curtimeO(n)spaceO(n)