Path Navigation

What is this?

A file path like /home/user/../photos is really a set of walking directions through folders, and .. just means "step back out of the folder I just entered." Since stepping back always undoes your most recent step, a stack handles it perfectly — like a pile of folders you can only add to or remove from the top. Replay the directions on a stack and whatever folders remain are the clean, simplified path.

flowchart TD A["Split the path on slashes"] --> B["A folder name"] A --> C["A dot dot"] A --> D["A dot or empty"] B --> E["Push the name"] C --> F["Pop the top folder"] D --> G["Skip it"]

💡 Fun fact: Your operating system simplifies paths this exact way every time you open a file, and it also uses the rule to stop sneaky paths full of .. from escaping into folders you should not reach.

🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.

Core idea: A filesystem path is a script of stack operations. Each directory name is a push, every .. is a pop, and . or empty segments (from //) are no-ops. Run the script and the stack you're left with is the resolved path.

Why a stack models a path

Walking into a directory and walking back out with .. is inherently LIFO: .. always cancels the most recently entered directory. That's a pop. So canonicalizing a path is just: split it into segments and replay them as pushes and pops.

Path /a/b/../c/./d// replayed as stack pushes and pops, resolving to /a/c/d

The problem in this chapter

Simplify Path — canonicalize a Unix path

Given an absolute path, produce its canonical form: starts with a single /, no trailing slash (except root), ./empty collapse away, .. goes up one level (and is a no-op at the root), and ordinary names — even odd ones like ... — stay as directories.

Simplify Path flow: split on '/', classify each segment as name/../. or empty, then push/pop/skip and join

Split on /, process each token with a stack, then rebuild "/" + "/".join(stack). → O(n) time, O(n) space.

The cross-cutting skill: classify each segment

Segment	Meaning	Stack move
`""` (from `//` or leading `/`)	nothing	skip
`"."`	current dir	skip
`".."`	parent dir	pop (no-op if empty)
anything else (incl. `"..."`)	a directory name	push

The whole problem is a four-way classification of each token. The trap is treating ... or .... as special — they're just directory names. Only exactly . and .. are magic.

Where you'll meet it beyond the interview

OS kernels resolve paths exactly this way (and must reject .. escaping a chroot — a path-traversal security check).
Container runtimes resolve overlay/bind mounts by canonicalizing paths.
Proxies, routers, and CDNs normalize URL paths before matching routes or cache keys.
Object stores canonicalize keys that look like paths.

📓 Draw it yourself

Path as a stack script. Take /x/y/../../z/ and draw the directory stack evolving segment by segment. Watch .. pop and the double-..-at-root do nothing.
The four cases. Make a tiny table on paper: "", ., .., name → skip/skip/pop/push. Internalize that ... falls into "name."

Snap photos and embed them with the /host-diagrams skill.

Complexity at a glance

Problem	Time	Space
Simplify Path	O(n)	O(n)

Key takeaways

A path is a stack script: names push, .. pops, ./empty skip.
.. at the root is a no-op — pop only if the stack is non-empty.
Only . and .. are special; ..., .... are ordinary directory names.
Rebuild as "/" + "/".join(stack) to get the single-leading-slash, no-trailing-slash form for free.
Why this chapter matters: it's literally how kernels, containers, and proxies resolve paths — and a clean, real-world showcase of the push/pop instinct.

Problem: Simplify Path.

Foundations