Path and Navigation
What is this?
Three problems look unrelated: decoding 3[a2[c]], finding the longest path in an indented directory listing, and working out which asteroids survive a collision. 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.
Worth noticing: Asteroid Collision is the odd one out. 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. A stack can model "who is still standing" as naturally as "what is still open", and seeing that is what makes the pattern transferable.
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
In one line: 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.
![Decode String worked trace on 3[a2[c]] (chalkboard)](https://maangioassets.blob.core.windows.net/diagrams/coding-interview/201/chapters/stack/path-and-navigation/path-and-navigation-summary-diagram-2.svg)
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 the length stored one level above it. No string concatenation is 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. The three outcomes must be kept apart, and equal sizes destroy both.
3. Where you'll actually meet this
- Template and macro expansion. A repeat block that can contain other repeat blocks needs the same stack (or recursion) as the decoder.
- Indented listings. Output in the style of
treeencodes structure by depth, and rebuilding a full path from it is the file-path problem. - Configuration parsing. YAML's indentation-defined nesting is the same idea: depth determines the parent.
- One-dimensional collision simulation. Resolving events in order while keeping a stack of survivors is the asteroid problem.
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: cost follows the decoded output size times the nesting depth, not the input length.
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(n) space if you split the input, O(depth) if you scan by index.
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, as in expression parsing. - Using
ifinstead ofwhilein the asteroid fight. One asteroid can destroy several. - Mishandling equal sizes. Both asteroids are destroyed, 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;
+ 1accounts 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
- Push whatever you will need at the pop. The state you save is dictated by how the group resolves, not by what looks tidy.
- Depth is an index. For indentation problems the stack position is the parent level, so no searching is required.
- A stack can hold survivors, not just context. Recognising that widens the pattern considerably.
- Fight loops need
while, and every outcome (defender dies, both die, challenger dies) needs its own branch. - Track lengths, not strings, whenever only a length is asked for.
- 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, then Asteroid Collision, then Longest Absolute File Path.
Decode String
Core idea: At every
[push the pair (string built so far, repeat count); at every]pop it and append the inner string repeated that many times. Push the prefix as well as the count, or everything before an inner group is lost.
Problem, rephrased
To shave bytes off a mobile sync payload, your protocol compresses repeated fragments with the rule k[encoded_string]: the encoded_string inside the square brackets is repeated exactly k times, and groups may nest. You're given one compressed payload as a string s, where every repeat count k is a positive integer.
Return the decoded string. You may assume s is valid: no stray whitespace, brackets are balanced, and the original data contains no digits, so a digit in s is always part of a repeat count.
Strip the story away and this is the classic Decode String. This is LeetCode 394: Decode String.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson