Problem Statement
Simplify Path
You are given a file path, the kind you see when you click through folders on a computer. It looks like "/home/user/docs". The slashes separate folder names. Your job is to clean it up into its simplest correct form, called the canonical form. There are a few special rules. A single dot "." means "stay in the current folder", so it does nothing. Two dots ".." mean "go back up one folder". Extra slashes like "//" should count as one. The cleaned path must start with a single "/", must not have a trailing "/" at the end (unless it is just the root "/"), and must use single slashes between folder names. The right tool here is a stack. A stack is like a pile of plates: you add a plate to the top and you take a plate off the top, so the last one you put on is the first one you take off. That matches folders perfectly. Walking into a folder is putting a plate on the pile, and ".." (go up one folder) is taking the top plate off.
Signals to notice
Brute force first
Not applicable — stack IS the natural approach.
The key insight
Split by '/'. For each part: '.' = skip, '..' = pop, '' = skip, else push. Join with '/' prefix. O(n).
Trace it on path="/home//foo/"
split('/') -> ['', 'home', '', 'foo', ''], stack=[]
part='' -> empty, skip; stack=[]
part='home' -> name, push; stack=['home']
part='' -> empty, skip; stack=['home']
part='foo' -> name, push; stack=['home','foo']
part='' -> empty, skip; stack=['home','foo']
join: '/' + 'home/foo' -> return '/home/foo'What must stay true
The stack represents root-to-current path. '..' = go up (pop). Valid names = go deeper (push).
Shape of the loop
stack = []
for part in path.split('/'):
if part in ('', '.'): continue
elif part == '..': if stack: stack.pop()
else: stack.push(part)
return '/' + '/'.join(stack)Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Popping empty stack on '..' — stay at root (don't pop).