Path and Navigation

What is this?

Three problems that look unrelated — decoding 3[a2[c]], finding the longest path in an indented directory listing, and working out which asteroids survive a collision — and all three are the same shape. Something is open and must be remembered until it closes. In the decoder it is a repeat count. In the file listing it is a parent directory. In the asteroid field it is a rock still travelling right, whose fate depends on what it meets.

💡 Fun fact: Asteroid Collision is the odd one out, and deliberately so. Its stack does not hold context to return to — it holds survivors. A left-moving asteroid arriving is not opening anything; it is a challenger that pops right-movers until one is bigger, both are equal, or the stack empties. Recognising that a stack can model "who is still standing" as naturally as "what is still open" is what makes the pattern transferable.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: decide what "unresolved" means for this problem — an open bracket, a parent directory, a surviving asteroid — and push exactly the state you will need when it resolves. The pop is where the answer is assembled.

1. Push the state you will need on the way out

The commonest mistake is pushing too little. When decoding 3[a2[c]], hitting the inner [ means the current partial string "a" and the multiplier 2 must both be preserved, because after the inner group resolves you must write "a" + "cc". Push the pair.

input: 3[a2[c]]

'3'   → num = 3
'['   → push ("", 3);   cur = ""
'a'   → cur = "a"
'2'   → num = 2
'['   → push ("a", 2);  cur = ""
'c'   → cur = "c"
']'   → pop ("a", 2)  → cur = "a" + "c"*2 = "acc"
']'   → pop ("", 3)   → cur = "" + "acc"*3 = "accaccacc"

The same discipline applies to the file path: the stack position is the depth, so stack[depth] holds the length of the path up to that level, and a new entry at depth d attaches to stack[d] — no string concatenation needed, only lengths.

2. When the stack holds survivors instead

Asteroid Collision inverts the roles. Right-movers are pushed. A left-mover fights:

for a in asteroids:
    alive = True
    while alive and a < 0 and stack and stack[-1] > 0:
        if stack[-1] < -a:  stack.pop()          # the defender loses, keep fighting
        elif stack[-1] == -a: stack.pop(); alive = False   # both explode
        else: alive = False                       # the incoming one loses
    if alive:
        stack.append(a)

The while is essential: one large left-mover can destroy several right-movers in sequence. And the three outcomes must be distinguished carefully — equal sizes destroy both, which is the case most implementations get wrong.

3. Where you'll actually meet this

• Template and markup engines. Nested loops or repeats in templating languages expand exactly like the decoder.
• Filesystem and archive tools. Reconstructing full paths from an indented or tab-delimited listing is what tar and tree-viewers do.
• Configuration parsing. YAML's indentation-defined nesting is the file-path problem generalised — depth determines the parent.
• Physics and game simulation. Collision resolution in one dimension, processed in order with a stack of survivors, is the asteroid problem's real-world twin.
• Compression formats. Run-length and nested-repeat encodings decode with this exact push/pop cycle.

4. Problems in this chapter

▶ Decode String

Expand k[encoded] with arbitrary nesting. Push the partial string and the repeat count at each [; assemble on each ].
Pattern: push (context, count), resolve on close. Target: O(output length) time and space.

▶ Asteroid Collision

Simulate collisions between right- and left-moving asteroids. The stack holds surviving right-movers; each left-mover fights until it dies, wins, or annihilates.
Pattern: stack of survivors with a fight loop. Target: O(n) time, O(n) space.

▶ Longest Absolute File Path

Find the longest full path in a tab-indented listing. The stack (or an array indexed by depth) holds the running path length at each level.
Pattern: depth-indexed stack of lengths. Target: O(n) time, O(depth) space.

5. Common pitfalls 🚫

• Pushing only the count in Decode String. The partial string built so far must be preserved too, or the prefix before an inner group is lost.
• Multi-digit repeat counts. 12[a] needs digit accumulation, exactly as in expression parsing.
• Using if instead of while in the asteroid fight. One asteroid can destroy several.
• Mishandling equal sizes. Both asteroids are destroyed — neither survives, and the incoming one must not be pushed.
• Forgetting that same-direction asteroids never collide. Only a right-mover on the stack facing a left-moving arrival is a collision.
• Building strings for file paths. You only need lengths; + 1 accounts for the separator. Concatenating actual paths is O(n²) for no benefit.
• Assuming a file always sits deepest. Only lines containing a . are files, and the longest path may not be the deepest one.

6. Key takeaways

1. Push whatever you will need at the pop. The state you save is dictated by how the group resolves, not by what looks tidy.
2. Depth is an index. For indentation problems the stack position is the parent level — no searching required.
3. A stack can hold survivors, not just context. Recognising that widens the pattern considerably.
4. Fight loops need while, and every outcome — defender dies, both die, challenger dies — needs its own branch.
5. Track lengths, not strings, whenever only a length is asked for.
6. Why interviewers like it: all three are simulations with fiddly rules, so they test precision and case analysis far more than algorithmic insight.

Order: Decode String → Asteroid Collision → Longest Absolute File Path.