LIFO order, monotonic stacks, and stack-based state machines are the key patterns here. The stack lets you defer work until context is clear.
Problems: 7
Easy: 1
Medium: 5
Hard: 1
Learning approach: Read the problem. Try the test cases yourself first.
Click Hint if stuck — it guides without spoiling.
Use Show Solution only after a genuine attempt.
Then hit Let's Code to run your solution live.
For every closing bracket, what must the most recently opened (top of stack) bracket be?
Python Solution
def isValid(s):
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for ch in s:
if ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else:
stack.append(ch)
return not stack
Key idea: Push opening brackets. For each closing bracket, check that the top of the stack is the matching opener. If the stack is empty at the end, the string is valid.
Key idea: Store each element as (val, min_so_far). The second element is the minimum of all values at or below this position. Popping naturally restores the previous minimum.
Scan tokens left to right. Numbers go on the stack. Operators pop two operands, compute, and push the result.
Python Solution
def evalRPN(tokens):
stack = []
ops = {'+', '-', '*', '/'}
for t in tokens:
if t in ops:
b, a = stack.pop(), stack.pop()
if t == '+': stack.append(a + b)
elif t == '-': stack.append(a - b)
elif t == '*': stack.append(a * b)
else: stack.append(int(a / b)) # truncate toward zero
else:
stack.append(int(t))
return stack[0]
Key idea: Classic stack-based evaluation. For division, use int(a/b) (not //) to truncate toward zero rather than flooring.
At each step you can add '(' if open < n, or ')' if close < open. When the string has 2n characters, it's a valid combination.
Python Solution
def generateParenthesis(n):
result = []
def backtrack(s, open_count, close_count):
if len(s) == 2 * n:
result.append(s)
return
if open_count < n:
backtrack(s + '(', open_count + 1, close_count)
if close_count < open_count:
backtrack(s + ')', open_count, close_count + 1)
backtrack('', 0, 0)
return result
Key idea: Backtracking with two constraints: add '(' only if fewer than n have been used; add ')' only if fewer than the number of '(' used. This naturally generates only valid sequences.
Given array temperatures, return an array answer where answer[i] is the number of days until a warmer temperature. If no future warmer day exists, put 0.
Use a stack of indices. When the current temperature is warmer than the top of the stack, pop and record the gap. The stack holds 'pending' cold days.
Python Solution
def dailyTemperatures(temperatures):
result = [0] * len(temperatures)
stack = [] # indices of days still waiting for a warmer day
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
Key idea: Maintain a monotonic decreasing stack of indices. When today is warmer than a past day on the stack, that past day has found its answer. The stack holds the indices of days still waiting.
Time: O(n) — each index pushed and popped once. Space: O(n).
n cars are driving toward the same destination at target miles. Given position and speed arrays, return the number of car fleets that arrive at the destination.
sort by position descendingtime to targetmonotonic stack
Sort cars by starting position (closest to target first). A car can only catch up to a car ahead of it. If a car takes more time than the one in front, it forms a new fleet.
Python Solution
def carFleet(target, position, speed):
# Pair and sort by position descending (closest to target first)
pairs = sorted(zip(position, speed), reverse=True)
stack = [] # stores arrival times of fleets
for pos, spd in pairs:
time = (target - pos) / spd
# If this car arrives later than the current last fleet,
# it cannot catch up → new fleet
if not stack or time > stack[-1]:
stack.append(time)
return len(stack)
Key idea: Sort by position (closest to target first). A car behind can only catch the one ahead if its time ≤ that car's time. If a car is slower (larger time), it forms a new fleet. The stack counts distinct fleets.
Time: O(n log n) — dominated by sort. Space: O(n).
Use a monotonic increasing stack. When a shorter bar is encountered, all taller bars on the stack can extend to the right up to (but not including) the current bar.
Python Solution
def largestRectangleArea(heights):
stack = [] # (start_index, height)
max_area = 0
for i, h in enumerate(heights):
start = i
while stack and stack[-1][1] > h:
idx, height = stack.pop()
# This bar extends from its original start to current i
max_area = max(max_area, height * (i - idx))
start = idx # the current bar can extend back to this point
stack.append((start, h))
# Process remaining bars (they extend to the right end)
for idx, height in stack:
max_area = max(max_area, height * (len(heights) - idx))
return max_area
Key idea: Monotonic increasing stack. When a shorter bar appears, pop taller bars and compute their area (they can't extend further right). The key insight: when popping, the shorter current bar can extend left to fill the gap.