INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD
01
00/15
01 / COVER MODULE 12 · STACKS & QUEUES
INVARIANT · MODULE 12 · STACKS & QUEUES
LAST IN, FIRST OUT

A stack answers one question in O(1): what is the most recent thing still open? Brackets, undo, expressions and nested strings all ask it. Nine moves, fifteen problems.

15Problems
6Families
9Units
12Live walks
← → ↑ ↓  or  W A S D  navigate SPACE next   DOUBLE-CLICK to advance I index   G goto problem   P predict H hide solutions   F fullscreen
INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
02 / INDEX PRESS I FROM ANYWHERE

INDEX — ALL 15 PROBLEMS

Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.

MATCH THE TOP · 02
CANCEL WITH THE TOP · 03
CARRY A SUMMARY · 01
EVALUATE · 03
NESTED FRAMES · 03
BUILD THE STRUCTURE · 03
SOLVED HAS A JUDGE LINK
INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
03 / MECHANISM UNIT 01 · MATCHING BRACKETS

A CLOSER ENDS THE MOST RECENT OPENER

Push every opener. A closer must match the top, the most recent opener still open. Last in, first out.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
04 / DRILL UNIT 01 · Matching Brackets

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

isValid("([)]"). What is returned, and at which character is it decided?

At the ), the top is [, not (. The pairs cross, so it returns there.

DRILL 02 · BUG

A solution keeps one counter per kind, fails if any goes below 0, and accepts if all end at 0. Which input does it wrongly accept?

Each counter stays ≥ 0 and ends at 0, yet the pairs cross. Counters cannot see order.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
05 / PROBLEM #01 · MATCH · EASY

Valid Parentheses

EASY match ▶ SOLVE ON LEETCODE

GIVEN · ASKEDA string of ()[]{}. Return true if every bracket is closed by the same kind, in the right order.

SIGNAL — WHAT GIVES IT AWAY

Three kinds of bracket, and every closer must close the most recent opener still open.

INTUITION

Push each opener. A closer pops the top and must be its partner. At the end nothing may be left open.

STEPS
  1. Opener: push it
  2. Closer with an empty stack: return false
  3. Closer: pop the top; if it is not the matching opener, return false
  4. After the loop: valid only if the stack is empty
BRUTEO(n²) deleting adjacent pairs until none are left
→
OPTIMALO(n)
↕ SCROLL
bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);   // an opener waits
        else {
            if (st.empty()) return false;                    // nothing is open
            char open = st.top(); st.pop();
            if ((c == ')' && open != '(') || (c == ']' && open != '[') ||
                (c == '}' && open != '{')) return false;     // the pairs cross
        }
    }
    return st.empty();                                       // all closed?
}
TIMEO(n)each character is pushed and popped at most once
SPACEO(n)the stack, all openers in the worst case
TRAP

Counting each kind separately. ([)] has one of each pair and is still invalid. Order matters, and only a stack keeps it.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
06 / MECHANISM UNIT 02 · CANCEL WITH THE TOP

ONLY THE TOP CAN CANCEL

Build the answer as a stack. A letter equal to the top removes it, and the letter below becomes the next one's neighbour.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
07 / MECHANISM UNIT 02 · RUNS OF K

STORE RUNS, NOT LETTERS

Each entry is a letter and its run length. A run that reaches k is popped whole, and the run below can grow again.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
08 / DRILL UNIT 02 · Cancel With the Top · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

removeDuplicates("azxxzy") with pairs. What is returned?

xx goes, which makes the two z's neighbours, and they go too. a and y are left.

DRILL 02 · TRACE

s = "pbbcggttciiippooaais" and k = 2. What is left?

Pairs vanish as they form: bb, gg and tt, then the two c's, the i's, p's, o's and a's.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
09 / PROBLEM #02 · CANCEL · EASY

Remove All Adjacent Duplicates In String

EASY cancel ▶ SOLVE ON LEETCODE

GIVEN · ASKEDA string of lowercase letters. Repeatedly remove two adjacent equal letters until none are left. Return the final string.

SIGNAL — WHAT GIVES IT AWAY

Two equal letters side by side vanish, and a removal can make new neighbours equal.

INTUITION

Build the answer as a stack. A letter equal to the top cancels it; any other letter is pushed. A removal is handled for free: the next letter meets whatever was below.

STEPS
  1. For each letter c: if the top equals c, pop it
  2. Otherwise push c
  3. The stack, bottom to top, is the answer
BRUTEO(n²) deleting a pair and rescanning
→
OPTIMALO(n)
↕ SCROLL
string removeDuplicates(string s) {
    string st;                                // the answer is the stack
    for (char c : s) {
        if (!st.empty() && st.back() == c) st.pop_back();   // c cancels the top
        else st.push_back(c);
    }
    return st;
}
TIMEO(n)each letter is pushed and popped at most once
SPACEO(n)the stack, which is also the answer
TRAP

Rescanning after each removal. while a pair exists, delete it and start again is O(n²) and times out at n = 10⁵.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
10 / PROBLEM #03 · CANCEL · MED

Remove All Adjacent Duplicates in String II

MED cancel ▶ SOLVE ON LEETCODE

GIVEN · ASKEDA string and an integer k. Repeatedly remove k adjacent equal letters until none are left. Return the final string.

SIGNAL — WHAT GIVES IT AWAY

As #02, but a run must reach k equal letters to vanish, and k can be large.

INTUITION

Store runs, not letters: each entry is a letter and the length of its run. A letter equal to the top grows the run; a run that reaches k is popped whole.

STEPS
  1. Top run has the same letter: add 1 to its count
  2. Otherwise push (c, 1)
  3. If the top count is now k, pop the run
  4. Write each run out, bottom to top
BRUTEO(nk) checking the last k − 1 letters each time
→
OPTIMALO(n)
↕ SCROLL
string removeDuplicates(string s, int k) {
    vector<pair<char, int>> st;               // (letter, length of its run)
    for (char c : s) {
        if (!st.empty() && st.back().first == c) st.back().second++;
        else st.push_back({c, 1});
        if (st.back().second == k) st.pop_back();   // k in a row vanish
    }
    string out;
    for (auto& p : st) out.append(p.second, p.first);
    return out;
}
TIMEO(n)each letter changes one count and each run is popped once
SPACEO(n)one entry per surviving run
TRAP

Peeking k − 1 letters back. Checking the last k − 1 letters on every push is O(nk). The count on top already knows the run's length.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
11 / PROBLEM #04 · CANCEL · MED

Simplify Path

MED cancel ▶ SOLVE ON LEETCODE

GIVEN · ASKEDAn absolute Unix path. Return its canonical form: one slash between names, no . or .., no trailing slash.

SIGNAL — WHAT GIVES IT AWAY

A Unix path with ., .. and repeated slashes, reduced to its canonical form.

INTUITION

Split on '/'. A name opens a directory, so push it. .. closes the most recent one, so pop. Empty parts and . change nothing.

STEPS
  1. Split the path on '/'
  2. Empty part or '.': skip
  3. '..': pop if the stack is not empty (at the root, stay)
  4. Anything else, '...' included: push
  5. Join with '/' and a leading '/'; an empty stack is "/"
↕ SCROLL
string simplifyPath(string path) {
    vector<string> st;                        // the directories still open
    stringstream ss(path);
    string part;
    while (getline(ss, part, '/')) {
        if (part.empty() || part == ".") continue;       // "//" and "." change nothing
        if (part == "..") { if (!st.empty()) st.pop_back(); }   // up one level
        else st.push_back(part);              // "..." is an ordinary name
    }
    string out;
    for (auto& d : st) out += "/" + d;
    return out.empty() ? "/" : out;
}
TIMEO(n)each part is pushed and popped at most once
SPACEO(n)the parts on the stack
TRAP

Treating any run of dots as special. Only . and .. are. ... is a directory name and must be pushed.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
12 / DRILL UNIT 02 · Cancel With the Top · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRANSFER

In Simplify Path, which part plays the letter that cancels the top?

".." closes the most recent directory. "." and "" do nothing, and "..." is a name.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
13 / MECHANISM UNIT 03 · A STACK OF INDICES

THE BOTTOM OF THE STACK IS A BASE

Keep indices. After a pop, the top is the last index that cannot be in the run, so i − top is its length.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
14 / DRILL UNIT 03 · A Stack of Indices

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

s = "()(())". What is on the stack when the loop ends?

Every ( closed, so only the first base is left. The last pop measured 5 − (−1) = 6.

DRILL 02 · RECALL

Why does the stack start with −1 instead of empty?

i − top needs an index before the run. For a run that starts at 0, that index is −1.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
15 / PROBLEM #05 · MATCH · HARD

Longest Valid Parentheses

HARD match ▶ SOLVE ON LEETCODE

GIVEN · ASKEDA string of ( and ). Return the length of the longest well-formed substring.

SIGNAL — WHAT GIVES IT AWAY

The length of the longest valid substring, not just whether the string is valid.

INTUITION

Keep indices. The bottom of the stack is a base: the last index that cannot be in the current run. After a pop, i − top is the length of the valid run ending at i.

STEPS
  1. Push −1 as the first base
  2. '(': push its index
  3. ')': pop; if the stack is now empty, push i as the new base
  4. Otherwise best = max(best, i − top)
BRUTEO(n³) checking every substring
→
OPTIMALO(n)
↕ SCROLL
int longestValidParentheses(string s) {
    stack<int> st;
    st.push(-1);                              // the index just before the current run
    int best = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '(') st.push(i);
        else {
            st.pop();                         // close the most recent '('
            if (st.empty()) st.push(i);       // an unmatched ')' is the new base
            else best = max(best, i - st.top());
        }
    }
    return best;
}
TIMEO(n)one pass, each index pushed and popped once
SPACEO(n)the index stack
TRAP

Counting matched pairs. ()(() has two pairs but the longest valid run is 2, not 4. Lengths come from indices, never from counts.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
16 / MECHANISM UNIT 04 · CARRY THE MINIMUM

EVERY ENTRY REMEMBERS THE MIN BELOW IT

Push (x, min(x, top's min)). That min cannot change while the entry is on the stack, so a pop needs no repair.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
17 / DRILL UNIT 04 · Carry the Minimum

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

push 4, push 2, push 6, pop, push 1, pop. What does getMin return?

(1, 1) was popped. The top is (2, 2), and it stored its own min when it was pushed.

DRILL 02 · BUG

A min stack keeps one variable mn, lowered on push. What breaks?

After the min is popped, the next smallest is unknown without scanning the stack.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
18 / PROBLEM #06 · AUGMENT · MED

Min Stack

MED augment ▶ SOLVE ON LEETCODE

GIVEN · ASKEDDesign a stack with push, pop, top and getMin, each in O(1).

SIGNAL — WHAT GIVES IT AWAY

A stack that must also answer getMin() in O(1), through any mix of pushes and pops.

INTUITION

Each entry stores its value and the minimum of itself and everything below it. That minimum never changes while the entry is on the stack, so a pop needs no repair.

STEPS
  1. push(x): m = min(x, the top's min), or x on an empty stack; push (x, m)
  2. pop(): pop the pair
  3. top(): the top's value
  4. getMin(): the top's min
BRUTEO(n) getMin by scanning the stack
→
OPTIMALO(1)
↕ SCROLL
class MinStack {
    stack<pair<int, int>> st;                 // (value, minimum at or below it)
public:
    void push(int val) {
        int m = st.empty() ? val : min(val, st.top().second);
        st.push({val, m});
    }
    void pop() { st.pop(); }
    int top() { return st.top().first; }
    int getMin() { return st.top().second; }
};
TIMEO(1)every operation reads or writes the top only
SPACEO(n)one pair per value
TRAP

One global min variable. It is right until the minimum is popped. Then the next smallest is unknown without a scan, which is O(n).

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
19 / MECHANISM UNIT 05 · POSTFIX EVALUATION

OPERANDS WAIT, THE OPERATOR COMES AFTER

Push numbers. An operator pops two and pushes one. The first pop is the right operand.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
20 / DRILL UNIT 05 · Postfix Evaluation

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

tokens = ["4", "13", "5", "/", "+"]. What is returned?

13 / 5 truncates to 2, and 4 + 2 = 6.

DRILL 02 · BUG

The / branch is written st.push(b / a) after b = pop, a = pop. What does ["6", "3", "/"] return?

b is 3, the right operand. Swapping computes 3 / 6, which truncates to 0.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
21 / PROBLEM #07 · EVALUATE · MED

Evaluate Reverse Polish Notation

MED evaluate ▶ SOLVE ON LEETCODE

GIVEN · ASKEDTokens of an expression in reverse Polish notation, with + − * /. Return its value; division truncates toward zero.

SIGNAL — WHAT GIVES IT AWAY

An expression in postfix: every operator comes after its two operands, and there are no parentheses.

INTUITION

Push numbers. An operator pops two, applies itself and pushes the result, which is then an operand like any other. The first pop is the right operand.

STEPS
  1. Number: push it
  2. Operator: b = pop, a = pop (in that order)
  3. Push a op b; division truncates toward zero
  4. At the end one value is left: return it
↕ SCROLL
int evalRPN(vector<string>& tokens) {
    stack<int> st;
    for (string& t : tokens) {
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            int b = st.top(); st.pop();       // the right operand comes off first
            int a = st.top(); st.pop();
            if (t == "+") st.push(a + b);
            else if (t == "-") st.push(a - b);
            else if (t == "*") st.push(a * b);
            else st.push(a / b);              // truncates toward zero, as asked
        } else st.push(stoi(t));
    }
    return st.top();
}
TIMEO(n)each token is pushed or popped a constant number of times
SPACEO(n)the operand stack
TRAP

Python's //. It floors, so -7 // 2 is −4 where the judge wants −3. Divide the absolute values and put the sign back.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
22 / MECHANISM UNIT 06 · INFIX TO POSTFIX

AN OPERATOR WAITS UNTIL NOTHING STRONGER CAN ARRIVE

Operands go straight out. Before pushing an operator, pop every waiting one that binds at least as tightly. ^ groups right to left.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
23 / MECHANISM UNIT 06 · BASIC CALCULATOR II

* AND / NOW, + AND − AT THE END

A stack of signed terms. When a number ends, + and − push it; * and / fold it into the term on top. Then add up.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
24 / DRILL UNIT 06 · Precedence · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

What is the postfix form of a+b*c-d?

* leaves before +. Then − pops +, because they bind equally and read left to right.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
25 / PROBLEM #08 · EVALUATE · MED

Infix to Postfix

MED evaluate ▶ SOLVE ON GEEKSFORGEEKSGeeksforGeeks rates it Medium. LeetCode has no free problem for this conversion.

GIVEN · ASKEDAn infix expression over letters and digits with + − * / ^ and parentheses. Return its postfix form.

SIGNAL — WHAT GIVES IT AWAY

Infix in, postfix out, with ^, * / and + − and parentheses. The statement says ^ groups right to left.

INTUITION

Operands go straight to the output. An operator waits on a stack; before it is pushed, every waiting operator that binds at least as tightly leaves first. A ')' empties back to its '('.

STEPS
  1. Letter or digit: append to the output
  2. '(': push
  3. ')': pop to the output until '(', then drop the '('
  4. Operator c: pop while the top binds tighter, or equally and c is not ^; then push c
  5. At the end pop everything to the output
↕ SCROLL
int prec(char c) {
    if (c == '^') return 3;
    if (c == '*' || c == '/') return 2;
    if (c == '+' || c == '-') return 1;
    return 0;                                 // '(' never wins
}
string infixToPostfix(string& s) {
    string out;
    stack<char> ops;
    for (char c : s) {
        if (isalnum(c)) out += c;             // operands go straight out
        else if (c == '(') ops.push(c);
        else if (c == ')') {
            while (ops.top() != '(') { out += ops.top(); ops.pop(); }
            ops.pop();                        // drop the '('
        } else {
            // pop what binds at least as tightly; ^ groups right to left
            while (!ops.empty() && (prec(ops.top()) > prec(c) ||
                   (prec(ops.top()) == prec(c) && c != '^'))) {
                out += ops.top(); ops.pop();
            }
            ops.push(c);
        }
    }
    while (!ops.empty()) { out += ops.top(); ops.pop(); }
    return out;
}
TIMEO(n)each operator is pushed and popped once
SPACEO(n)the operator stack and the output
TRAP

Treating ^ like the others. a^b^c is a^(b^c), so the answer is abc^^. Popping equal precedence for ^ gives ab^c^.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
26 / PROBLEM #09 · EVALUATE · MED

Basic Calculator II

MED evaluate ▶ SOLVE ON LEETCODE

GIVEN · ASKEDA string with non-negative integers, + − * / and spaces. Return its value; division truncates toward zero.

SIGNAL — WHAT GIVES IT AWAY

Non-negative integers with + − * / and spaces, but no parentheses.

INTUITION

Keep a stack of signed terms. When a number ends, look at the operator before it: + and − push it as a new term, * and / combine it with the term on top at once. Sum the stack.

STEPS
  1. Read digits into num
  2. At an operator or the end: apply the PREVIOUS operator to num
  3. + pushes num, − pushes −num, * and / change the top term
  4. Remember the new operator, reset num
  5. Return the sum of the terms
↕ SCROLL
int calculate(string s) {
    vector<int> st;                           // signed terms, added at the end
    long num = 0;
    char op = '+';                            // the operator before num
    for (int i = 0; i <= (int)s.size(); i++) {
        char c = i < (int)s.size() ? s[i] : '+';   // a sentinel closes the last number
        if (isdigit(c)) { num = num * 10 + (c - '0'); continue; }
        if (c == ' ') continue;
        if (op == '+') st.push_back(num);
        else if (op == '-') st.push_back(-num);
        else if (op == '*') st.back() *= num;      // * and / bind now
        else st.back() /= num;
        op = c; num = 0;
    }
    int sum = 0;
    for (int t : st) sum += t;
    return sum;
}
TIMEO(n)one pass over the characters
SPACEO(n)the terms (O(1) is possible with a running last term)
TRAP

Forgetting the last number. The loop acts when an operator arrives, and the last number has none after it. The sentinel '+' closes it.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
27 / DRILL UNIT 06 · Precedence · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Basic Calculator II on "14-3/2". Which terms are on the stack before the sum?

− pushes −3, then / folds 2 into it: −3 / 2 truncates to −1. 14 − 1 = 13.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
28 / MECHANISM UNIT 07 · NESTED FRAMES

PARK THE OUTER FRAME, BUILD THE INNER ONE

[ pushes the text so far and its count. ] repeats the inside and joins it back onto the parked text.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
29 / DRILL UNIT 07 · Nested Frames · 1 OF 3

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

decodeString("3[a2[c]]")?

The inner frame gives "cc", so each outer copy is "acc", three times.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
30 / PROBLEM #10 · FRAMES · MED

Decode String

MED frames ▶ SOLVE ON LEETCODE

GIVEN · ASKEDAn encoded string where k[s] means s repeated k times, possibly nested. Return the decoded string.

SIGNAL — WHAT GIVES IT AWAY

k[...] repeats what is inside, and brackets nest: 3[a2[c]].

INTUITION

Each '[' opens a frame. Park the text built so far and the count on the stack, then build the inside from empty. At ']' the inside is repeated and joined to the parked text.

STEPS
  1. Digit: k = k·10 + digit (counts can have several digits)
  2. '[': push (cur, k); cur = "", k = 0
  3. ']': pop (prev, times); cur = prev + cur repeated times
  4. Letter: append to cur
↕ SCROLL
string decodeString(string s) {
    stack<pair<string, int>> st;              // (text before '[', its repeat count)
    string cur;
    int k = 0;
    for (char c : s) {
        if (isdigit(c)) k = k * 10 + (c - '0');   // counts can be 100
        else if (c == '[') { st.push({cur, k}); cur = ""; k = 0; }
        else if (c == ']') {
            pair<string, int> f = st.top(); st.pop();
            string rep;
            for (int j = 0; j < f.second; j++) rep += cur;
            cur = f.first + rep;              // fold the inner frame into the outer
        } else cur += c;
    }
    return cur;
}
TIMEO(output)every character of the answer is written a constant number of times per level
SPACEO(output)the parked frames and the text
TRAP

Reading the count as one digit. 12[a] is twelve a's. Build k digit by digit, and reset it after the '['.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
31 / PROBLEM #11 · FRAMES · HARD

Basic Calculator

HARD frames ▶ SOLVE ON LEETCODE

GIVEN · ASKEDA string with integers, + −, parentheses and spaces; − may be unary. Return its value without eval.

SIGNAL — WHAT GIVES IT AWAY

+, −, parentheses and a unary minus, as in -(2 + 3). No * or /.

INTUITION

Without * and / the value is a signed sum. A '(' parks the running result and the sign in front of the group; ')' finishes the group and folds it back in with that sign.

STEPS
  1. Digit: build num
  2. '+' or '−': result += sign·num; num = 0; sign = ±1
  3. '(': push (result, sign); result = 0; sign = 1
  4. ')': result += sign·num; pop (r, sg); result = r + sg·result
  5. Return result + sign·num
↕ SCROLL
int calculate(string s) {
    stack<pair<long, int>> st;                // (result before '(', sign in front of it)
    long result = 0, num = 0;
    int sign = 1;
    for (char c : s) {
        if (isdigit(c)) num = num * 10 + (c - '0');
        else if (c == '+' || c == '-') {
            result += sign * num; num = 0;
            sign = c == '+' ? 1 : -1;         // a unary minus is handled the same way
        } else if (c == '(') {
            st.push({result, sign});          // park the outer frame
            result = 0; sign = 1;
        } else if (c == ')') {
            result += sign * num; num = 0;
            pair<long, int> f = st.top(); st.pop();
            result = f.first + f.second * result;   // fold the group back in
        }
    }
    return result + sign * num;
}
TIMEO(n)one pass
SPACEO(n)one parked frame per open parenthesis
TRAP

Flipping the signs inside the group by hand. Only the sign in front of the '(' matters, and it is parked with the frame. Multiply the finished group by it once.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
32 / DRILL UNIT 07 · Nested Frames · 2 OF 3

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Basic Calculator on "1 - (2 - 3)". The frame parked at ( is (1, −1) and the group is −1. What is returned?

Fold the group in with the parked sign: 1 + (−1)·(−1) = 2.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
33 / PROBLEM #12 · FRAMES · HARD

Parsing A Boolean Expression

HARD frames ▶ SOLVE ON LEETCODEAlso linked from DP 4, where the deck notes it does not need DP. It is a stack problem, so it is taught here. Progress is kept per deck.

GIVEN · ASKEDA boolean expression of t, f, !(…), &(…) and |(…). Return its value.

SIGNAL — WHAT GIVES IT AWAY

Nested !(…), &(…,…) and |(…,…) over t and f, any depth.

INTUITION

Push every character except commas. A ')' closes the innermost frame: pop its values down to '(', pop the operator, and push the frame's one-letter value.

STEPS
  1. ',': skip
  2. Anything but ')': push it
  3. ')': pop values until '(', counting t and f; pop '('; pop the operator
  4. ! is f > 0, & is f == 0, | is t > 0; push t or f
  5. At the end the single value left is the answer
↕ SCROLL
bool parseBoolExpr(string expression) {
    stack<char> st;
    for (char c : expression) {
        if (c == ',') continue;
        if (c != ')') { st.push(c); continue; }   // operators, '(' and values wait
        int t = 0, f = 0;                     // close the innermost frame
        while (st.top() != '(') { if (st.top() == 't') t++; else f++; st.pop(); }
        st.pop();                             // the '('
        char op = st.top(); st.pop();
        bool v = op == '!' ? f > 0 : op == '&' ? f == 0 : t > 0;
        st.push(v ? 't' : 'f');               // the frame becomes one value
    }
    return st.top() == 't';
}
TIMEO(n)each character is pushed and popped once
SPACEO(n)the stack of waiting characters
TRAP

Evaluating the operator before its frame closes. An operand of & may itself be a frame. Only a ')' says every operand is known.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
34 / DRILL UNIT 07 · Nested Frames · 3 OF 3

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

In &(t,|(f,t),f), which frame is evaluated first?

The first ) closes the innermost frame. Its value, t, then waits on the stack for &.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
35 / MECHANISM UNIT 08 · THE RING BUFFER

A FIXED ARRAY WHOSE ENDS WRAP ROUND

head and count are the whole state. The rear is (head + count) % k. Nothing is ever shifted.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
36 / DRILL UNIT 08 · The Ring Buffer

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

k = 3. enQueue 1, 2, 3, then deQueue, then enQueue 4. Where is 4, and what is head?

head = 1 and count = 2, so the rear is (1 + 2) % 3 = 0.

DRILL 02 · RECALL

Why keep count instead of only head and tail indices?

With only two indices, a full ring and an empty one look the same.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
37 / PROBLEM #13 · DESIGN · MED

Design Circular Queue

MED design ▶ SOLVE ON LEETCODE

GIVEN · ASKEDDesign a circular queue of capacity k: enQueue, deQueue, Front, Rear, isEmpty, isFull.

SIGNAL — WHAT GIVES IT AWAY

A queue of fixed capacity k, every operation O(1), and no shifting.

INTUITION

A fixed array, a head index and a count. The rear is (head + count) % k, so both ends wrap round. Dequeue only moves head; the old value is simply no longer counted.

STEPS
  1. enQueue: if count == k return false; write at (head + count) % k; count++
  2. deQueue: if count == 0 return false; head = (head + 1) % k; count--
  3. Front: a[head]; Rear: a[(head + count − 1) % k]; −1 when empty
  4. isEmpty: count == 0; isFull: count == k
↕ SCROLL
class MyCircularQueue {
    vector<int> a;
    int head = 0, count = 0;                  // the front slot, how many are live
public:
    MyCircularQueue(int k) : a(k) {}
    bool enQueue(int value) {
        if (isFull()) return false;
        a[(head + count) % a.size()] = value; // the rear wraps round
        count++;
        return true;
    }
    bool deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % a.size();         // the old front is simply forgotten
        count--;
        return true;
    }
    int Front() { return isEmpty() ? -1 : a[head]; }
    int Rear() { return isEmpty() ? -1 : a[(head + count - 1) % a.size()]; }
    bool isEmpty() { return count == 0; }
    bool isFull() { return count == (int)a.size(); }
};
TIMEO(1)index arithmetic only
SPACEO(k)the k slots
TRAP

head and tail with nothing else. When they meet, the queue could be full or empty. Keep a count, or leave one slot unused.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
38 / MECHANISM UNIT 09 · QUEUE FROM TWO STACKS

POURING ONE STACK INTO ANOTHER REVERSES IT

Push onto in, serve from out. Pour only when out is empty: each value moves once, O(1) amortised.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
39 / MECHANISM UNIT 09 · STACK FROM ONE QUEUE

ROTATE THE OLDER VALUES BEHIND THE NEW ONE

After a push, move the size − 1 older values from the front to the back. The front is always the top.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
40 / DRILL UNIT 09 · One Structure From the Other · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Queue from two stacks: push 1, push 2, pop, push 3, pop, pop. How many values move from in to out in total?

The first pop pours 1 and 2. The second finds 2 waiting. The third pours 3. Three moves.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
41 / PROBLEM #14 · DESIGN · EASY

Implement Queue using Stacks

EASY design ▶ SOLVE ON LEETCODE

GIVEN · ASKEDImplement a FIFO queue (push, pop, peek, empty) using only two stacks.

SIGNAL — WHAT GIVES IT AWAY

A FIFO queue using only stack operations, with every operation O(1) on average.

INTUITION

Push onto in. Serve from out. When out runs dry, pour all of in into it, which reverses it and puts the oldest on top. Each value is poured once.

STEPS
  1. push(x): onto in
  2. pop / peek: if out is empty, move everything from in to out
  3. Then pop or read the top of out
  4. empty: both stacks empty
BRUTEO(n) per pop, pouring both ways every time
→
OPTIMALO(1) amortised
↕ SCROLL
class MyQueue {
    stack<int> in, out;                       // in: newest on top · out: oldest on top
    void shift() {
        if (out.empty())                      // pour only when out has run dry
            while (!in.empty()) { out.push(in.top()); in.pop(); }
    }
public:
    void push(int x) { in.push(x); }
    int pop() { shift(); int x = out.top(); out.pop(); return x; }
    int peek() { shift(); return out.top(); }
    bool empty() { return in.empty() && out.empty(); }
};
TIMEO(1) amortisedeach value is moved from in to out at most once
SPACEO(n)the two stacks
TRAP

Pouring on every pop. Moving in to out while out still holds values buries older values under newer ones, and the order breaks.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
42 / PROBLEM #15 · DESIGN · EASY

Implement Stack using Queues

EASY design ▶ SOLVE ON LEETCODE

GIVEN · ASKEDImplement a LIFO stack (push, pop, top, empty) using only queues.

SIGNAL — WHAT GIVES IT AWAY

A LIFO stack using only queue operations: push to the back, pop from the front, size.

INTUITION

Keep the queue in stack order, newest at the front. After pushing x to the back, move the size − 1 older values from the front to the back, one at a time.

STEPS
  1. push(x): q.push(x), then rotate size − 1 times (front to back)
  2. pop(): pop the front
  3. top(): the front
  4. empty(): q is empty
↕ SCROLL
class MyStack {
    queue<int> q;                             // the front of q is the top of the stack
public:
    void push(int x) {
        q.push(x);
        for (int i = 0; i + 1 < (int)q.size(); i++) {   // rotate the older ones behind x
            q.push(q.front()); q.pop();
        }
    }
    int pop() { int x = q.front(); q.pop(); return x; }
    int top() { return q.front(); }
    bool empty() { return q.empty(); }
};
TIMEO(n) push · O(1) popeach push rotates every older value once
SPACEO(n)the queue
TRAP

Rotating size times instead of size − 1. One rotation too many moves x itself to the back, and the order is lost.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
43 / DRILL UNIT 09 · One Structure From the Other · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Stack from one queue, holding 3, 2, 1 from the front. After push 4, how many rotations were made, and what is the queue?

size − 1 = 3 rotations move 3, 2 and 1 behind 4, which now leads.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
44 / SIGNALS WHEN YOU SEE X, REACH FOR Y

WHICH MOVE, AND WHAT GIVES IT AWAY

Nine moves, and each has a phrase in the statement that gives it away.

“VALID” / “BALANCED” / “MATCHING”

push the openers; a closer must match the top

MATCH THE TOPO(n)
“ADJACENT … REMOVED” / BACKSPACE / ..

each item cancels the top or is pushed; the survivors are the answer

CANCEL WITH THE TOPO(n)
“LONGEST VALID” / A LENGTH, NOT A YES

store indices; the index below the run is a base, and i − top is its length

STACK OF INDICESO(n)
“ALSO RETURN THE MIN, IN O(1)”

each entry carries a summary of everything below it

CARRY A SUMMARYO(1) each
THE OPERATOR AFTER ITS OPERANDS

push numbers; an operator pops two and pushes one

POSTFIX EVALUATIONO(n)
PRECEDENCE: * / BEFORE + −

pop what binds at least as tightly before pushing; * and / at once, + and − at the end

PRECEDENCEO(n)
k[…] / NESTED ( … ) / !( … )

park the outer frame at the opener, fold the inner one back in at the closer

NESTED FRAMESO(n)
“FIXED CAPACITY”, O(1), NO SHIFTING

head and count in a fixed array; both ends wrap with %

RING BUFFERO(1) each
“USING ONLY STACKS” / “ONLY QUEUES”

pour in → out when out is empty; rotate size − 1 after a push

BUILD ONE FROM THE OTHERO(1) amortised · O(n) push
INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
45 / RECALL RETRIEVAL, NOT RECOGNITION · 1 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

Each * in a string deletes the closest letter to its left that is not a star, and the star goes too. Which move solves it in one pass?

A star cancels the top letter. Push letters, pop on a star; the stack is the answer.

DRILL 02 · TRANSFER

Score a balanced bracket string: () is 1, AB is A + B and (A) is 2·A. Which move?

Each '(' opens a frame that is scored at its ')' and folded into the frame around it.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
46 / RECALL RETRIEVAL, NOT RECOGNITION · 2 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · RECALL

Which of these needs the stack to start with a sentinel index, −1?

−1 is the base before index 0, so a run that starts at 0 can be measured as i − (−1).

DRILL 02 · RECALL

A queue built from two stacks takes n pushes and n pops, in any order. What do they cost in total?

Each value is pushed, poured once and popped once: three stack operations each, 3n in all.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
47 / TRAPS PLAUSIBLE, WRONG, AND SILENT

SIX WAYS TO BE PLAUSIBLY WRONG

None of these crash on the samples. Each one fails a hidden test.

COUNTING INSTEAD OF STACKING

([)] has a closer for every opener and is still invalid. Only the order on a stack catches crossed pairs.

POPPING AN EMPTY STACK

A closer or an operator with nothing below it. Check empty() first: in C++, top() on an empty stack is undefined.

THE OPERANDS THE WRONG WAY ROUND

The first pop is the right operand. a − b and a / b change if you swap them, and tests with only + and * never notice.

FLOOR DIVISION IN PYTHON

-7 // 2 is −4. The judges truncate toward zero and want −3.

^ GROUPED LEFT TO RIGHT

a^b^c is a^(b^c). A ^ already waiting must stay when another ^ arrives.

head == tail WITH NO COUNT

In a ring, equal ends mean full or empty. Keep a count, or leave one slot unused.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
48 / CHEATSHEET REVISION SURFACE

ONE SCREEN, THE WHOLE DECK

Nine moves on one page. The right column is the cue for each.

ALGORITHM
TIME
SPACE
REACH FOR IT WHEN
Match the top
O(n)
O(n)
brackets; a closer ends the most recent opener
Cancel with the top
O(n)
O(n)
adjacent removals, '..' in a path; runs of k as (item, count)
Stack of indices
O(n)
O(n)
a length or distance; a base below the run
Carry a summary
O(1) per op
O(n)
the min or max of the whole stack, at any time
Postfix evaluation
O(n)
O(n)
operators after operands; the first pop is the right side
Precedence
O(n)
O(n)
infix to postfix; * and / now, + and − later
Nested frames
O(n)
O(depth)
k[…], ( … ) with signs, nested boolean operators
Ring buffer
O(1) per op
O(k)
a fixed-capacity queue; (head + count) % k
Build one from the other
O(1) amortised
O(n)
pour in → out only when out is empty
INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
49 / CLOSE MODULE 12 · STACKS & QUEUES

STACK IT YOURSELF

Brackets matched against the top; letters cancelled it; indices measured runs; pairs carried a minimum; operators waited their turn; frames nested; a ring wrapped; and each structure was built from the other.

00%
OF THIS DECK SOLVED
← ALL TOPICS← STRINGSLRU CACHE · LINKED LIST 3

Module 12. Fifteen problems: fourteen on LeetCode, one on GeeksforGeeks. Next: the monotonic stack.

INVARIANT · STACKS & QUEUES · MATCH, CANCEL, EVALUATE & BUILD · STACKS & QUEUES
■ TOO SMALL TO READ
1280×720
INVARIANT · MODULE 12 · STACKS & QUEUES

This one needs a laptop

Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.

Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.

YOUR SCREEN0 × 0
NEEDED1060 × 610
WHAT IS WAITING ON THE LAPTOP
WATCH IT RUN, THEN RUN IT FROM MEMORY
Your progress is saved per device, so anything you tick on the laptop will be waiting there.