Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Split the path on '/', then process each component with a stack. Ignore empty strings (from '//') and '.' (current directory). For '..' pop one directory off the stack if it's non-empty (you can't go above root). Push any real directory name. Finally, join the stack with '/' and prepend a leading '/'. The stack naturally models 'go up = undo the last directory'. O(n) time, O(n) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you reach for a stack to model directory navigation, and whether you enumerate every token case correctly: empty, '.', '..' (with the root-boundary guard), and real names.
Where candidates slip
Forgetting that '..' at root is a no-op (popping an empty stack), mishandling empty tokens from '//', or treating multi-dot names like '...' as special when they're ordinary directory names.
How to stand out
Cleanly split into the four token cases up front, state the root-boundary invariant ('you can never go above /'), and rebuild the canonical path in one join — then note that names like '...' are valid directories, not navigation.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewSplit path on '/'token value?'' or '.''..'Explore the full treeCollapse the tree
How to read it:'..' pops the most recent directory; '.' and empties are ignored.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 1 · Optimal
Stack of Directory Names (Optimal)
1Hint 1Explore hintHide hint
Walking the path, '..' has to cancel whatever directory you most recently entered. What data structure lets you undo the most recent action in O(1)?
2Hint 2Explore hintHide hint
Split the path on '/' to get components. Classify each: empty string and '.' do nothing, '..' pops, any other string is a directory to push.
3Hint 3Explore hintHide hint
Guard the pop so '..' at the root (empty stack) does nothing, then rebuild the answer as '/' joined with the stack contents.
A · Core idea
Canonicalizing a path is fundamentally about navigation history: entering a directory is a 'push', and '..' ('go up') must undo the most recent push. That last-in-first-out structure is exactly a stack, which is why the clean solution tokenizes the path and folds each token into a stack of directory names.
Tokenizing on '/'. Splitting the path on '/' turns "/home//foo/" into components ['', 'home', '', 'foo', '']. Crucially, redundant slashes and the leading/trailing slash all surface as empty strings, which we simply skip. This is why we don't need any special pre-cleaning of // or trailing / — the split plus an empty-token skip handles them uniformly. (In Java, split("/") similarly yields empty entries that we filter.)
The four token cases. Each component is exactly one of: (1) empty string → skip (redundant slash); (2) '.' → skip (current directory, no movement); (3) '..' → pop one directory, but only if the stack is non-empty; (4) anything else → push it as a real directory name. The third case carries the key invariant: you can never go above the root. At /, a '..' has nowhere to go, so popping an empty stack must be a no-op — forgetting the non-empty guard either crashes (popping empty) or, worse in some languages, silently misbehaves.
Why '...' is not special. The prompt is explicit that only the exact strings '.' and '..' are navigation. A token like '...', '....', or 'a.b' is an ordinary directory name and goes through the push branch untouched. Candidates who over-generalize 'dots mean navigation' get these wrong. Matching '.' and '..' by exact equality (not by 'starts with a dot') is what keeps this correct.
Rebuilding the canonical path. After processing, the stack holds the surviving directories in order from root to leaf. The canonical path is '/' followed by those names joined by single slashes: '/' + '/'.join(stack). This construction gives every required property for free — it starts with a single slash, separates directories by exactly one slash, and has no trailing slash. The lone special case is an empty stack, where '/'.join([]) is '' and the result becomes just '/', the root — precisely what we want for inputs like "/../" or "/".
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
path = "/a/./b/../../c/"Interactive diagram
'..' at root is a no-op
''Popping is guarded so the path can never escape '/'.
"/c"C · Code with teaching comments
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The stack is doing one job: remembering the navigation history so '..' can reverse it in O(1). Whenever a problem has an operation that cancels the most recent prior operation, a stack is almost certainly the model. The split-then-fold structure here (tokenize, classify, mutate stack, rebuild) is a reusable template for path/expression canonicalization.
ComplexityO(n) time, O(n) space — Splitting is O(n) and each of the O(n) tokens is processed in O(1) (push/pop/skip). The final join is O(n). The stack and the output string are each at most O(n) → O(n) time and O(n) space.
E · Edge cases and pitfalls8path = "/" — Split → ['','']; both skipped; empty stack → '/'.Explore edge casesHide edge cases
Edge cases handled
path = "/"Split → ['','']; both skipped; empty stack → '/'.path = "/..."'...' is a valid name → pushed → '/...'.path = "/../"'..' on empty stack is a no-op → '/'.path = "/a//b////c/d//././/.."Empties and '.' skipped, final '..' pops d → '/a/b/c'.
Pitfalls
- Popping an empty stack on '..' — crashes or misbehaves; always guard with a non-empty check.
- Treating '...' or '..foo' as navigation — only exact '.' and '..' are special.
- Forgetting that split produces empty tokens for '//' and trailing '/' — they must be skipped.
- In Java, iterating an ArrayDeque used as a stack in the wrong direction — reverses the path.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic String simplifyPath(String path) { Deque<String> stack = new ArrayDeque<>(); for (String part : path.split("/")) { if (part.isEmpty() || part.equals(".")) { continue; // redundant slash or current dirExplore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Popping an empty stack on '..'
At the root, '..' has nowhere to go. Popping an empty stack throws in Java and silently underflows logic elsewhere. Guard the pop.
Explore the code comparisonHide the code comparison
Popping an empty stack on '..'
At the root, '..' has nowhere to go. Popping an empty stack throws in Java and silently underflows logic elsewhere. Guard the pop.
Don't write this
elif part == '..':
stack.pop() # IndexError when at rootWrite this instead
elif part == '..':
if stack:
stack.pop() # no-op at root2Treating '...' as navigation
Only the exact strings '.' and '..' are special. Matching by 'starts with a dot' wrongly drops valid directories like '...' or 'a.b'.
Explore the code comparisonHide the code comparison
Treating '...' as navigation
Only the exact strings '.' and '..' are special. Matching by 'starts with a dot' wrongly drops valid directories like '...' or 'a.b'.
Don't write this
if (part.startsWith(".")) { // wrongly catches '...', '.hidden'
// treat as navigation
}Write this instead
if (part.equals(".")) { /* skip */ }
else if (part.equals("..")) { /* pop */ }
else { stack.push(part); } // '...' lands here as a real name3Forgetting empty tokens from redundant slashes
split('/') turns '//' and a trailing '/' into empty strings. If you don't skip them, you push '' as a fake directory and corrupt the join.
Explore the code comparisonHide the code comparison
Forgetting empty tokens from redundant slashes
split('/') turns '//' and a trailing '/' into empty strings. If you don't skip them, you push '' as a fake directory and corrupt the join.
Don't write this
for part in path.split('/'):
if part == '..': ...
else: stack.append(part) # pushes '' for '//'Write this instead
for part in path.split('/'):
if part == '' or part == '.':
continue
# ... handle '..' and namesRevise
Carry the pattern into the interview
Pattern to remember
Tokenize on '/', use a stack to resolve '.' and '..'
Code pattern to memorize
stack = []
for part in path.split('/'):
if part == '' or part == '.': continue
elif part == '..': if stack: stack.pop()
else: stack.push(part)
return '/' + '/'.join(stack)Rules to remember
- 1Split on
'/'and skip empty tokens — consecutive slashes//and a trailing slash both produce''. - 2
'.'means 'current directory' → ignore it entirely. - 3
'..'means 'go up' → pop the stack, but only if it's non-empty (..at root is a no-op, you can't escape/). - 4Everything else is a real directory name → push it (names may contain dots like
...ora.b, treat them literally). - 5Rebuild as
'/' + join(stack, '/'); an empty stack yields just'/'(the root).
Use this pattern when
- Canonicalize a Unix-style absolute file path
- Any 'undo the last step' processing where '..' reverses a push
- Resolving sequences with reversible operations (a stack mirrors history)
- Token-by-token state where the most recent item is what you cancel
Choose another pattern when
- Relative paths or symbolic-link resolution against a real filesystem → needs OS calls, not pure string logic
- You must preserve '.'/'..' literally (not resolve them) → it's a parsing, not a canonicalization, task
- Windows-style backslash paths or drive letters → different separators and rules
- You need the path's parent only → simple rsplit, no stack
Interview takeaway
A stack is the natural model whenever an operation ('..') undoes the most recent action (a pushed directory). Tokenize, fold each token into stack state, and rebuild. The same 'most-recent-cancels' shape powers expression evaluation, Backspace String Compare, and Min Stack.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternStack-based token folding for path canonicalization. Recognize it when an operation undoes the most recent prior step — here '..' reverses the last directory push. Tokenize on the separator, classify each token, mutate the stack, and rebuild. The same LIFO model underlies Valid Parentheses, Backspace String Compare, and RPN evaluation.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Backspace String CompareComing soonSame 'most-recent-cancels' idea — '#' pops the last char like '..' pops a directory.
- Evaluate Reverse Polish NotationStack folds tokens too: operands push, operators pop two and push the result.
- Valid ParenthesesStack matches the most recent open bracket — the canonical LIFO problem.
- Longest Absolute File PathComing soonParse a tabbed path tree with a stack of directory depths/lengths.