Nested structure via stack

40 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Decode 3[a2[c]]: the rule is that k[string] means repeat the string k times, and brackets can nest. By hand you work from the inside out: 2[c] is cc, so the string becomes 3[acc], which is accaccacc.

Working inside out by hand means finding the innermost bracket, expanding it, rewriting the string, and starting again. Each rewrite copies the whole string, and there are as many rewrites as brackets, so that is O(brackets × length). More importantly, it needs you to see the whole string first. Reading left to right, you hit 3[ before knowing what is inside, so you need somewhere to put the "3 times" instruction while you go and work out the inside.

Build the structure, one piece at a time

Piece one: a current context, which is the string being built right now plus the repeat count that will apply to it. At the very start the current string is empty and there is no count yet.

Piece two: on an opening bracket, push the current context onto a stack and start a fresh, empty inner string. The stack is the pile of unfinished outer strings, each waiting for its inner part.

Piece three: on a closing bracket, the inner string is complete. Pop the outer context, repeat the inner string by the popped count, and append the result to the outer string. That outer string becomes current again.

Digits may be several characters long (12[ab]), so a count is accumulated as count = count × 10 + digit until the bracket arrives. The same stack-of-contexts shape evaluates nested lists, nested function calls (push the caller's state, pop when the callee returns), and arithmetic with parentheses (push the running total and sign, start a fresh total inside the bracket).

Why it is correct

The invariant: the stack, bottom to top, is the chain of enclosing brackets that are currently open, each holding the text already built outside it and the count that will multiply its inside; the current string is the text built so far inside the innermost open bracket. Opening a bracket adds one level and starts its inside empty, so the invariant holds. Closing one finishes exactly the innermost level, which is the top of the stack because brackets nest, and folds it into the level below. Letters only ever extend the innermost text. When the input ends with an empty stack, the current string is the fully decoded result. Nesting is what makes "the top of the stack is the right context" true: the bracket that closes is always the most recently opened one, the same fact as in bracket matching.

Why it is fast

Each input character does O(1) work plus the copying when a bracket closes. Every character of the final output is written once when its level is folded into the level outside it, but a character inside nested brackets is copied once per level, so the cost is O(output size × nesting depth) in the worst case and O(output) when nesting is shallow, which is what the problem statement bounds. The by-hand rewrite copied the whole string per bracket, which is worse. The stack never holds more than one context per open bracket, O(depth) memory.

How to recognise it in an interview

Cues: "nested", "encoded with brackets", "evaluate an expression with parentheses", "nested list", "function calls and returns in a log". The tell is a structure that opens, has content, and closes, where the content must be finished before the opener's instruction can apply.

Say: "On an open bracket I push the current context and start fresh; on a close I pop and fold the inner result into the outer context." Decode String is the example. Basic Calculator pushes the running total and the sign at "(", and on ")" multiplies the inner total by that sign and adds it to the popped total. Exclusive Time of Functions pushes a function on "start" and pops it on "end", charging the elapsed time to the top.

02The idea in one line

On '[' push the current context; on ']' pop and fold the inner result into it.

Reach for it when: Decode strings, nested lists, mini interpreters, exclusive time of functions.

Cost: O(output) time.

03The walk-through, step by step

The video works one example: Decode String on '3[a2[c]]'. These are its captions in order, so you can follow without the video or check a step you missed.

1. On '[' push the current context; on ']' pop and fold the inner result into it
2. digit 3: repeat count = 3
3. '[': push ('', 3); start a fresh inner string
4. letter 'a': append to the current string → 'a'
5. digit 2: repeat count = 2
6. '[': push ('a', 2); start a fresh inner string
7. letter 'c': append to the current string → 'c'
8. ']': pop ('a', 2): 'a' + 2×'c' = 'acc'
9. ']': pop ('', 3): '' + 3×'acc' = 'accaccacc'
10. Stack empty: decoded 'accaccacc'
11. Each bracket pushes and pops once; cost is the output length

04Asked at Google

7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Stack: Matching with a stack, Expression evaluation, Auxiliary-min stack, Collision simulation.