Simplify Path
Canonicalise a Unix file path with a stack, where `..` is a pop and `.` is a no-op
Problem Statement
Given an absolute Unix-style path, return its canonical form. The canonical path:
- Starts with a single
/ - Has exactly one
/between components - Does not end with
/(unless it is the root/) - Contains no
.or..components
Input: "/home/" → "/home"
Input: "/../" → "/" (cannot go above root)
Input: "/home//foo/" → "/home/foo" (collapse repeated slashes)
Input: "/a/./b/../../c/" → "/c"
Input: "/a/../../b/" → "/b"Intuition
Directory navigation is naturally last-in-first-out: .. undoes the most recent cd. That is a stack.
The key insight
Split the path on / and process the components left to right:
| Component | Action |
|---|---|
"" (from // or a trailing /) | ignore |
"." (current directory) | ignore |
".." (parent directory) | pop — but only if the stack is non-empty |
| anything else | push — it is a real directory name |
Join the stack with /, prefix a /, and you have the canonical path.
Splitting handles the messy slash rules for free. "/home//foo/".split("/") gives ["", "home", "", "foo", ""] — every irregularity becomes an empty string, and empty strings are simply ignored.
Watch it run
Approach
Walk the components
Skip "" and ".". On "..", pop if the stack is non-empty. Otherwise push the component.
Join with / and prefix a /
An empty stack joins to "", and "/" + "" = "/" — the root case falls out with no special handling.
`..` at the root must be a no-op, not an error
"/../" resolves to "/". In Unix, the parent of the root is the root itself. Popping an empty stack would crash in Python and silently return undefined in TypeScript, so the emptiness check is required.
Solution
def simplify_path(path: str) -> str:
"""Return the canonical form of an absolute Unix path."""
stack: list[str] = []
for part in path.split("/"):
if part == "" or part == ".":
continue # empty (from // or a trailing /) or current dir
if part == "..":
if stack: # cannot go above the root
stack.pop()
continue
stack.append(part) # a real directory name
return "/" + "/".join(stack)A language difference worth knowing
Array.prototype.pop() on an empty array returns undefined and does nothing — so TypeScript needs no emptiness guard. Python's list.pop() raises IndexError, so the if stack: check is mandatory.
The same asymmetry appeared in Valid Parentheses.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
- Time — splitting is
O(n), and each component is pushed and popped at most once. - Space —
O(n)for the split components and the stack. A path like"/a/b/c/d/…"with no..keeps everything.
Edge Cases
Related Problems
- Valid Parentheses — the stack as a matching structure
- Evaluate Reverse Polish Notation — a stack of operands
- Min Stack — designing around stack behaviour