Stack

Step 1 Understand it

Remember it by

The most recent unfinished thing comes first: push it, and pop when its match arrives.

Watch it happen

The idea

A stack is last-in, first-out. Use it when the newest item is the one that gets resolved next: matching brackets, undo, or 'the next greater element' (a monotonic stack keeps items in sorted order and pops everything the new item beats).

Picture it

flowchart LR
  N["next value x"] --> Q{"stack not empty and<br/>top value < x?"}
  Q -->|"yes"| P["pop the top:<br/>its answer is x"] --> Q
  Q -->|"no"| PU["push x"] --> N

Analogy

A pile of plates: you add and remove only from the top. For brackets, every closing one must match the plate on top.

Where the analogy breaks

Plates don't care about order. A monotonic stack does: before pushing, it pops every item smaller (or bigger) than the new one, and that pop is the moment you record an answer.

Step 2 Recognise it

Words that signal it

• 'Valid parentheses', nested or matching pairs
• 'Next greater / smaller element', 'how many days until warmer'
• 'Evaluate an expression', 'decode a string'
• 'Undo', 'backspace', 'most recent'

Don't confuse it with

• Queue / BFS: First-in, first-out (process in arrival order, level by level) → queue. Most recent first → stack.
• Two Pointers: A palindrome check uses two pointers; nested matching (brackets) needs a stack because pairs can wrap around each other.

Gut check

Does the newest item get resolved first, or do I need the next bigger thing? → stack.

How to recognise it in an interview

The problem involves 'matching' elements, 'nearest', 'undo', or checking if things are 'validly nested'.

Step 3 The template

The general shape. Adapt it to each problem rather than learning one solution per problem.

def next_greater(nums):
    answer = [-1] * len(nums)
    stack = []                          # indexes; their values are decreasing
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            j = stack.pop()             # x is the first thing bigger than nums[j]
            answer[j] = x               # (or i - j for a distance)
        stack.append(i)
    return answer

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if (c == ')' && top != '(') return false;
                if (c == '}' && top != '{') return false;
                if (c == ']' && top != '[') return false;
            }
        }
        return stack.isEmpty();
    }
}

Common mistakes

• Popping from an empty stack: check if stack before stack[-1].
• Forgetting the leftovers at the end: in Valid Parentheses, a non-empty stack means unmatched openers.
• Storing values when you need distances: push indexes, then i − j gives the gap (Daily Temperatures).

Step 4 Watch it run

Two problems, traced step by step exactly as the code runs.

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    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

def daily_temperatures(temps):
    answer = [0] * len(temps)
    stack = []                          # days still waiting for a warmer day
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

Step 5 Practise

Read each question and say the pattern and the trick out loud before you open the answer. Then solve it on LeetCode. Tick a problem once you've solved it on your own: it comes back for review tomorrow, then after 3, 7, 14 and 30 days, then every month, on the DSA page.

Easy

1. Mark "Valid Parentheses" as solved Valid Parentheses Easy

   Decide whether a string of brackets is correctly opened and closed.

   Show answer

   Technique: Stack

   The clue: Nested matching pairs.

   The trick: Push openers; each closer must match the top of the stack; the stack must end empty.

Medium

1. Mark "Min Stack" as solved Min Stack Medium

   Design a stack that also returns its minimum in O(1).

   Show answer

   Technique: Stack with a second 'minimum so far' stack

   The clue: O(1) minimum while items come and go in stack order.

   The trick: Alongside each pushed value, push the minimum so far; popping removes both.

2. Mark "Evaluate Reverse Polish Notation" as solved Evaluate Reverse Polish Notation Medium

   Evaluate an expression written in reverse Polish notation, like ['2', '1', '+', '3', '*'].

   Show answer

   Technique: Stack

   The clue: Each operator uses the two most recent numbers.

   The trick: Push numbers; on an operator, pop two (b first, then a), push a op b; divide truncating towards zero.

3. Mark "Daily Temperatures" as solved Daily Temperatures Medium

   For each day, how many days until a warmer temperature?

   Show answer

   Technique: Monotonic decreasing stack

   The clue: 'How long until the next greater…'.

   The trick: Keep waiting days on a stack; a warmer day pops and answers all cooler days on top.

4. Mark "Car Fleet" as solved Car Fleet Medium

   Cars drive towards a target at different speeds and can't overtake; count how many fleets arrive.

   Show answer

   Technique: Sort + stack of arrival times

   The clue: Cars can't pass, so a faster car behind joins the one ahead.

   The trick: Sort by position from closest to the target; compute arrival times; a car that would arrive sooner than the fleet ahead merges into it.

Hard

1. Mark "Largest Rectangle In Histogram" as solved Largest Rectangle In Histogram Hard

   Find the largest rectangle that fits inside a histogram.

   Show answer

   Technique: Monotonic increasing stack

   The clue: For each bar: how far can it stretch left and right before a shorter bar?

   The trick: Keep increasing heights on a stack; when a shorter bar arrives, pop and compute each popped bar's widest rectangle.

What to say in the interview

'Because we need to evaluate the most recently seen items first, I'll use a Stack to enforce Last-In-First-Out processing.'

Follow-up prep

How would you implement a Stack using only Queues?