Problems
Practical mastery of stacks comes from recognizing when a problem requires processing elements in reverse chronological order. Start with these curated challenges to build your intuition. For implementation reference, see our Code Templates.
Easy
1. Valid Parentheses
- Brief: Given a string containing just the characters
(,),{,},[and], determine if the input string is valid. - Why this pattern?: Brackets must be closed in the exact opposite order they were opened (LIFO).
- Key Insight: Use a stack to track open brackets. When a closing bracket appears, it must match the most recently opened bracket at the top of the stack. This validation runs intime andO(N)space.O(N)
Visual Explanation:
flowchart TD
Input["Input: ([])"] --> S0[Empty Stack]
S0 --> S1["Read '(': Push to Stack"]
S1 --> S2["Read '[': Push to Stack"]
S2 --> S3["Read ']': Match & Pop '['"]
S3 --> S4["Read ')': Match & Pop '('"]
S4 --> S5[Stack Empty]
S5 --> Success[Valid Outcome]
function isValid(s) {
const stack = [];
const map = { ')': '(', '}': '{', ']': '[' };
for (const char of s) {
if (map[char]) {
if (stack.pop() !== map[char]) return false;
} else {
stack.push(char);
}
}
return stack.length === 0;
}def is_valid(s: str) -> bool:
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in s:
if char in mapping:
top = stack.pop() if stack else '#'
if mapping[char] != top:
return False
else:
stack.append(char)
return not stackpublic boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(') stack.push(')');
else if (c == '{') stack.push('}');
else if (c == '[') stack.push(']');
else if (stack.isEmpty() || stack.pop() != c) return false;
}
return stack.isEmpty();
}bool isValid(string s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '{' || c == '[') st.push(c);
else {
if (st.empty()) return false;
if (c == ')' && st.top() != '(') return false;
if (c == '}' && st.top() != '{') return false;
if (c == ']' && st.top() != '[') return false;
st.pop();
}
}
return st.empty();
}func isValid(s string) bool {
stack := []rune{}
pairs := map[rune]rune{')': '(', '}': '{', ']': '['}
for _, char := range s {
if opening, ok := pairs[char]; ok {
if len(stack) == 0 || stack[len(stack)-1] != opening {
return false
}
stack = stack[:len(stack)-1]
} else {
stack = append(stack, char)
}
}
return len(stack) == 0
}def is_valid(s)
stack = []
map = { ')' => '(', '}' => '{', ']' => '[' }
s.each_char do |c|
if map.key?(c)
return false if stack.pop != map[c]
else
stack.push(c)
end
end
stack.empty?
end2. Backspace String Compare
- Brief: Determine if two strings are equal when both are typed into empty text editors, where
#represents a backspace. - Why this pattern?: Backspaces affect the most recently typed character, making it a classic Last-In-First-Out (LIFO) scenario.
- Key Insight: Use a stack to process each string. Push characters onto the stack, and pop them when you encounter a
#. This approach takestime andO(N + M)space.O(N + M)
Visual Explanation:
flowchart LR
Input["Input: 'ab#c'"] --> S0[Empty]
S0 -- "Push a" --> S1[a]
S1 -- "Push b" --> S2["a, b"]
S2 -- "Pop for #" --> S3[a]
S3 -- "Push c" --> S4["a, c"]
function backspaceCompare(s, t) {
const build = (str) => {
const stack = [];
for (const char of str) {
if (char === '#') {
stack.pop();
} else {
stack.push(char);
}
}
return stack.join('');
};
return build(s) === build(t);
}def backspace_compare(s: str, t: str) -> bool:
def build(string):
stack = []
for char in string:
if char != '#':
stack.append(char)
elif stack:
stack.pop()
return "".join(stack)
return build(s) == build(t)public boolean backspaceCompare(String s, String t) {
return build(s).equals(build(t));
}
private String build(String str) {
Stack<Character> stack = new Stack<>();
for (char c : str.toCharArray()) {
if (c != '#') {
stack.push(c);
} else if (!stack.isEmpty()) {
stack.pop();
}
}
return String.valueOf(stack);
}bool backspaceCompare(string s, string t) {
auto build = [](string str) {
string res = "";
for (char c : str) {
if (c != '#') {
res.push_back(c);
} else if (!res.empty()) {
res.pop_back();
}
}
return res;
};
return build(s) == build(t);
}func backspaceCompare(s string, t string) bool {
build := func(str string) string {
var stack []rune
for _, char := range str {
if char == '#' {
if len(stack) > 0 {
stack = stack[:len(stack)-1]
}
} else {
stack = append(stack, char)
}
}
return string(stack)
}
return build(s) == build(t)
}def backspace_compare(s, t)
build = ->(str) do
stack = []
str.each_char do |c|
if c == '#'
stack.pop
else
stack.push(c)
end
end
stack.join
end
build.call(s) == build.call(t)
endMedium
3. Daily Temperatures
- Brief: Given an array of temperatures, return an array such that
answer[i]is the number of days you have to wait for a warmer temperature. - Why this pattern?: This is a classic “Next Greater Element” problem solvable with a Monotonic Stack.
- Key Insight: Maintain a decreasing stack of indices. When you encounter a temperature warmer than the one at the stack top, you have found the answer for that past day. This “Next Greater Element” strategy works intime.O(N)
Visual Explanation:
flowchart TD
T[Temp: 73, 74, 75]
S0[Empty Stack] --> S1["Push index 0 (73)"]
S1 --> S2["74 > 73? Pop 0, Ans[0]=1, Push index 1 (74)"]
S2 --> S3["75 > 74? Pop 1, Ans[1]=1, Push index 2 (75)"]
function dailyTemperatures(temperatures) {
const n = temperatures.length;
const res = new Array(n).fill(0);
const stack = []; // decreasing stack of indices
for (let i = 0; i < n; i++) {
while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
const idx = stack.pop();
res[idx] = i - idx;
}
stack.push(i);
}
return res;
}def daily_temperatures(temperatures: List[int]) -> List[int]:
res = [0] * len(temperatures)
stack = [] # contains indices
for i, t in enumerate(temperatures):
while stack and t > temperatures[stack[-1]]:
idx = stack.pop()
res[idx] = i - idx
stack.append(i)
return respublic int[] dailyTemperatures(int[] temperatures) {
int[] res = new int[temperatures.length];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < temperatures.length; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int idx = stack.pop();
res[idx] = i - idx;
}
stack.push(i);
}
return res;
}vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int> res(temperatures.size(), 0);
stack<int> st;
for (int i = 0; i < temperatures.size(); i++) {
while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
int idx = st.top();
st.pop();
res[idx] = i - idx;
}
st.push(i);
}
return res;
}func dailyTemperatures(temperatures []int) []int {
res := make([]int, len(temperatures))
stack := []int{}
for i, t := range temperatures {
for len(stack) > 0 && t > temperatures[stack[len(stack)-1]] {
idx := stack[len(stack)-1]
stack = stack[:len(stack)-1]
res[idx] = i - idx
}
stack = append(stack, i)
}
return res
}def daily_temperatures(temperatures)
res = Array.new(temperatures.length, 0)
stack = []
temperatures.each_with_index do |t, i|
while !stack.empty? && t > temperatures[stack.last]
idx = stack.pop
res[idx] = i - idx
end
stack.push(i)
end
res
end4. Evaluate Reverse Polish Notation
- Brief: Evaluate the value of an arithmetic expression in Reverse Polish Notation.
- Why this pattern?: In RPN, operators apply to the most recently seen numbers, fitting the stack’s LIFO property.
- Key Insight: Push numbers onto the stack. When an operator appears, pop the top two numbers, apply the operation, and push the result back. This evaluates expressions in lineartime.O(N)
Visual Explanation:
flowchart TD
Input["Input: ['2', '1', '+', '3', '*']"]
S0["Stack: [2, 1]"] -- "Read '+'" --> S1["Pop 2, 1 -> Push 3"]
S1 -- "Read '3'" --> S2["Stack: [3, 3]"]
S2 -- "Read '*'" --> S3["Pop 3, 3 -> Push 9"]
function evalRPN(tokens) {
const stack = [];
const ops = {
'+': (a, b) => a + b,
'-': (a, b) => a - b,
'*': (a, b) => a * b,
'/': (a, b) => Math.trunc(a / b)
};
for (const token of tokens) {
if (ops[token]) {
const b = stack.pop();
const a = stack.pop();
stack.push(ops[token](a, b));
} else {
stack.push(Number(token));
}
}
return stack[0];
}def eval_rpn(tokens: List[str]) -> int:
stack = []
for t in tokens:
if t not in "+-*/":
stack.append(int(t))
else:
r, l = stack.pop(), stack.pop()
if t == "+": stack.append(l + r)
elif t == "-": stack.append(l - r)
elif t == "*": stack.append(l * r)
else: stack.append(int(l / r))
return stack.pop()public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String s : tokens) {
if ("+-*/".contains(s)) {
int r = stack.pop();
int l = stack.pop();
if (s.equals("+")) stack.push(l + r);
else if (s.equals("-")) stack.push(l - r);
else if (s.equals("*")) stack.push(l * r);
else stack.push(l / r);
} else {
stack.push(Integer.parseInt(s));
}
}
return stack.pop();
}int evalRPN(vector<string>& tokens) {
stack<int> st;
for (string& t : tokens) {
if (t == "+" || t == "-" || t == "*" || t == "/") {
int r = st.top(); st.pop();
int l = st.top(); st.pop();
if (t == "+") st.push(l + r);
else if (t == "-") st.push(l - r);
else if (t == "*") st.push(l * r);
else st.push(l / r);
} else {
st.push(stoi(t));
}
}
return st.top();
}func evalRPN(tokens []string) int {
stack := []int{}
for _, t := range tokens {
if val, err := strconv.Atoi(t); err == nil {
stack = append(stack, val)
} else {
r, l := stack[len(stack)-1], stack[len(stack)-2]
stack = stack[:len(stack)-2]
var res int
switch t {
case "+": res = l + r
case "-": res = l - r
case "*": res = l * r
case "/": res = l / r
}
stack = append(stack, res)
}
}
return stack[0]
}def eval_rpn(tokens)
stack = []
tokens.each do |t|
case t
when "+", "-", "*", "/"
r, l = stack.pop, stack.pop
stack.push(l.fdiv(r).to_i)
else
stack.push(t.to_i)
end
end
stack.pop
endHard
5. Largest Rectangle in Histogram
- Brief: Find the area of the largest rectangle in a histogram represented by an array of heights.
- Why this pattern?: To find the max area for a bar at index
i, we need to find the nearest boundaries on the left and right that are shorter thanheight[i]. - Key Insight: A monotonic increasing stack allows us to find these boundaries intime instead ofO(N).O(N^2)
Visual Explanation:
flowchart TD
H[Heights: 2, 1, 5, 6, 2, 3]
Step1["Push 2"]
Step2["1 < 2? Pop 2, Area = 2*1=2. Push 1"]
Step3["Push 5, Push 6"]
Step4["2 < 6? Pop 6, Area = 6*1=6. 2 < 5? Pop 5, Area = 5*2=10. Push 2"]
Final["Pop remainder, calculate areas using full width"]
function largestRectangleArea(heights) {
let maxArea = 0;
const stack = [-1]; // anchor index
for (let i = 0; i < heights.length; i++) {
while (stack[stack.length - 1] !== -1 && heights[i] <= heights[stack[stack.length - 1]]) {
const h = heights[stack.pop()];
const w = i - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, h * w);
}
stack.push(i);
}
while (stack[stack.length - 1] !== -1) {
const h = heights[stack.pop()];
const w = heights.length - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, h * w);
}
return maxArea;
}def largest_rectangle_area(heights: List[int]) -> int:
stack = [-1]
max_area = 0
for i in range(len(heights)):
while stack[-1] != -1 and heights[i] <= heights[stack[-1]]:
h = heights[stack.pop()]
w = i - stack[-1] - 1
max_area = max(max_area, h * w)
stack.append(i)
while stack[-1] != -1:
h = heights[stack.pop()]
w = len(heights) - stack[-1] - 1
max_area = max(max_area, h * w)
return max_areapublic int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int maxArea = 0;
for (int i = 0; i < heights.length; i++) {
while (stack.peek() != -1 && heights[i] <= heights[stack.peek()]) {
int h = heights[stack.pop()];
int w = i - stack.peek() - 1;
maxArea = Math.max(maxArea, h * w);
}
stack.push(i);
}
while (stack.peek() != -1) {
int h = heights[stack.pop()];
int w = heights.length - stack.peek() - 1;
maxArea = Math.max(maxArea, h * w);
}
return maxArea;
}int largestRectangleArea(vector<int>& heights) {
stack<int> s;
s.push(-1);
int max_area = 0;
for (int i = 0; i < heights.size(); i++) {
while (s.top() != -1 && heights[i] <= heights[s.top()]) {
int h = heights[s.top()];
s.pop();
int w = i - s.top() - 1;
max_area = max(max_area, h * w);
}
s.push(i);
}
while (s.top() != -1) {
int h = heights[s.top()];
s.pop();
int w = heights.size() - s.top() - 1;
max_area = max(max_area, h * w);
}
return max_area;
}func largestRectangleArea(heights []int) int {
stack := []int{-1}
maxArea := 0
for i, h := range heights {
for stack[len(stack)-1] != -1 && h <= heights[stack[len(stack)-1]] {
height := heights[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
width := i - stack[len(stack)-1] - 1
if height*width > maxArea {
maxArea = height * width
}
}
stack = append(stack, i)
}
for stack[len(stack)-1] != -1 {
height := heights[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
width := len(heights) - stack[len(stack)-1] - 1
if height*width > maxArea {
maxArea = height * width
}
}
return maxArea
}def largest_rectangle_area(heights)
stack = [-1]
max_area = 0
heights.each_with_index do |h, i|
while stack.last != -1 && h <= heights[stack.last]
height = heights[stack.pop]
width = i - stack.last - 1
max_area = [max_area, height * width].max
end
stack.push(i)
end
while stack.last != -1
height = heights[stack.pop]
width = heights.length - stack.last - 1
max_area = [max_area, height * width].max
end
max_area
end6. Trapping Rain Water
- Brief: Compute how much water is trapped after raining between elevation peaks.
- Why this pattern?: A pit where water is trapped is defined by heights forming a “V” shape (decreasing then increasing).
- Key Insight: Maintain a decreasing monotonic stack of indices. When the current height is greater than the stack top, you have found a potential trapping pit. This allows us to calculate total water intime.O(N)
Visual Explanation:
flowchart TD
H["Heights: [0, 1, 0, 2]"]
S0["Push 0"] --> S1["Push 1 (1 > 0, no trap)"]
S1 --> S2["Push 0"]
S2 --> S3["Current 2 > 0: Pop Pit 0, Boundary is 1. Water traps!"]
function trap(height) {
let water = 0;
const stack = [];
for (let i = 0; i < height.length; i++) {
while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
const top = stack.pop();
if (stack.length === 0) break;
const distance = i - stack[stack.length - 1] - 1;
const boundedHeight = Math.min(height[i], height[stack[stack.length - 1]]) - height[top];
water += distance * boundedHeight;
}
stack.push(i);
}
return water;
}def trap(height: List[int]) -> int:
ans = 0
stack = []
for i, h in enumerate(height):
while stack and h > height[stack[-1]]:
top = stack.pop()
if not stack: break
distance = i - stack[-1] - 1
bounded_height = min(h, height[stack[-1]]) - height[top]
ans += distance * bounded_height
stack.append(i)
return anspublic int trap(int[] height) {
int ans = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < height.length; i++) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int top = stack.pop();
if (stack.isEmpty()) break;
int distance = i - stack.peek() - 1;
int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[top];
ans += distance * boundedHeight;
}
stack.push(i);
}
return ans;
}int trap(vector<int>& height) {
int ans = 0;
stack<int> st;
for (int i = 0; i < height.size(); i++) {
while (!st.empty() && height[i] > height[st.top()]) {
int top = st.top();
st.pop();
if (st.empty()) break;
int distance = i - st.top() - 1;
int bounded_height = min(height[i], height[st.top()]) - height[top];
ans += distance * bounded_height;
}
st.push(i);
}
return ans;
}func trap(height []int) int {
ans := 0
var stack []int
for i, h := range height {
for len(stack) > 0 && h > height[stack[len(stack)-1]] {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if len(stack) == 0 {
break
}
distance := i - stack[len(stack)-1] - 1
boundedHeight := min(h, height[stack[len(stack)-1]]) - height[top]
ans += distance * boundedHeight
}
stack = append(stack, i)
}
return ans
}
func min(a, b int) int {
if a < b { return a }
return b
}def trap(height)
ans = 0
stack = []
height.each_with_index do |h, i|
while !stack.empty? && h > height[stack.last]
top = stack.pop
break if stack.empty?
distance = i - stack.last - 1
bounded_height = [h, height[stack.last]].min - height[top]
ans += distance * bounded_height
end
stack.push(i)
end
ans
endRecommended Study Order
- Level 1: Start with Valid Parentheses and Backspace String Compare to understand basic stack mechanics.
- Level 2: Tackle Daily Temperatures and Evaluate Reverse Polish Notation to master the Monotonic Stack pattern and expression evaluation.
- Level 3: Finish with Largest Rectangle in Histogram and Trapping Rain Water to see how stacks derive complex geometrical bounds in linear time.