NeetCode 150 · Stack

Stack Problems

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.
01 Easy StringStack
Given string s containing only '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
Test Cases
isValid('()') → True isValid('()[]{}') → True isValid('(]') → False
stackclosing→opening mapO(n)
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.
Time: O(n).
Space: O(n).
02 Medium StackDesign
Design a stack that supports push, pop, top, and getMin in O(1).
Test Cases
s = MinStack() s.push(-2); s.push(0); s.push(-3) s.getMin() → -3 s.pop() s.getMin() → -2
(val, min) pairsO(1) mindesign
Each element in the stack can remember the minimum at the time it was pushed. How would that let you recover the min after a pop?
Python Solution
class MinStack: def __init__(self): self.stack = [] # stores (value, current_min) def push(self, val): cur_min = min(val, self.stack[-1][1] if self.stack else val) self.stack.append((val, cur_min)) def pop(self): self.stack.pop() def top(self): return self.stack[-1][0] def getMin(self): return self.stack[-1][1]
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.
Time: O(1) for all operations.
Space: O(n).
03 Medium ArrayStackMath
Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, and / (truncate toward zero).
Test Cases
evalRPN(['2','1','+','3','*']) → 9 evalRPN(['4','13','5','/','+']) → 6 evalRPN(['10','6','9','3','+','-11','*','/', '*','17','+','5','+']) → 22
stackint() truncationoperator dispatch
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.
Time: O(n).
Space: O(n).
04 Medium StringBacktrackingStack
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Test Cases
generateParenthesis(3) → ['((()))','(()())','(())()','()(())','()()()'] generateParenthesis(1) → ['()']
backtrackingopen/close counterspruning
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.
Time: O(4ⁿ/√n) — Catalan number.
Space: O(n) recursion depth.
05 Medium ArrayStackMonotonic Stack
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.
Test Cases
dailyTemperatures([73,74,75,71,69,72,76,73]) → [1,1,4,2,1,1,0,0] dailyTemperatures([30,40,50,60]) → [1,1,1,0]
monotonic decreasing stackindex differencesO(n)
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).
06 Medium ArrayStackSorting
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.
Test Cases
carFleet(12, [10,8,0,5,3], [2,4,1,1,3]) → 3 carFleet(10, [3], [3]) → 1
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).
07 Hard ArrayStackMonotonic Stack
Given an array of integers heights representing a histogram's bar heights, return the area of the largest rectangle in the histogram.
Test Cases
largestRectangleArea([2,1,5,6,2,3]) → 10 largestRectangleArea([2,4]) → 4
monotonic increasing stackextend leftO(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.
Time: O(n).
Space: O(n).
← Prev Category Next Category →