Stack

LIFO structure for matching brackets, evaluating expressions, and monotonic problems.

10 problems 1 Easy 9 Medium 0 Hard

Overview

Stacks are essential for problems involving nested structures, backtracking, or next-greater/smaller element patterns. The monotonic stack variant maintains a sorted invariant for O(n) solutions.

When to Use

Valid parentheses / bracket matching
Next greater element
Daily temperatures
Evaluate reverse Polish notation
Min stack
Decode string

Common Mistakes

Not checking if stack is empty before popping
Using a stack when a deque is needed
Confusing increasing vs decreasing monotonic stack

Complexity

Time

O(n) — each element pushed/popped at most once

Space

O(n)

// Monotonic decreasing stack (next greater element)
function nextGreater(arr) {
  const result = new Array(arr.length).fill(-1);
  const stack = []; // stores indices

  for (let i = 0; i < arr.length; i++) {
    while (stack.length && arr[stack[stack.length - 1]] < arr[i]) {
      result[stack.pop()] = arr[i];
    }
    stack.push(i);
  }
  return result;
}

Problems (10)

Hide completed

Problem	Difficulty	Companies	Freq
Valid Parentheses	Easy	GoogleAmazon +2	High
Min Stack	Medium	AmazonBloomberg +1	High
Evaluate Reverse Polish Notation	Medium	AmazonLinkedIn	Medium
Daily Temperatures	Medium	AmazonGoogle +1	High
Decode String	Medium	GoogleAmazon +1	Medium
Asteroid Collision	Medium	AmazonGoogle +1	Medium
Remove K Digits	Medium	GoogleFacebook	Medium
Car Fleet	Medium	AmazonGoogle	Medium
Basic Calculator II	Medium	AmazonFacebook +2	High
Simplify Path	Medium	FacebookAirbnb +1	Medium

Enjoying this free content?

If this saved you time, buying me a coffee keeps new content coming.

☕ Buy me a coffee

Buy me a coffee