Simplify Path
Problem
Given a string path representing an absolute Unix-style file path, return the simplified canonical path.
- 1 ≤ path.length ≤ 3000
- path consists of English letters, digits, period '.', slash '/' or '_'
- path is a valid absolute Unix path
Example
path = "/a/./b/../../c/""/c"Walk through the example path step by step. 1) Start with the input: path = "/a/./b/../../c/". 2) Split by '/' to get raw parts: ["", "a", ".", "b", "..", "..", "c", ""]. The empty strings come from leading, trailing, and double slashes. 3) Initialize an empty stack to represent the current directory path. 4) Process each part in order: - "" → ignore (no directory) - "a" → push onto stack → ["a"] - "." → current directory, ignore - "b" → push onto stack → ["a", "b"] - ".." → go up one level, pop → ["a"] - ".." → go up again, pop → [] - "c" → push onto stack → ["c"] - "" → ignore 5) After processing all parts, the stack holds ["c"], which describes the simplified path from root. 6) Join the stack with '/' and prefix with '/', giving the canonical path "/c".
Approach
Straightforward Solution
A naive approach would try to simplify the path by manually editing the string, repeatedly removing dot and dot-dot segments and collapsing slashes. This is messy, easy to get wrong around edge cases like multiple slashes or long chains of parent moves, and less efficient than a single linear pass with a stack.
Core Observation
The path can be decomposed into components separated by '/', where '.' means current directory (no change), '..' means move up one directory (pop last), and other names mean move into a subdirectory (push). The problem reduces to processing these components in order and maintaining a stack to represent the current directory path.
Path to Optimal
PreviewSplitting the path by '/' yields components that can be processed sequentially. Using a stack to track directory names allows easy handling of '.…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewSplit the input path by '/'. Iterate over each component: skip empty strings and '…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Splitting the path and iterating through each component is O(n), where n is the length of the path string. Each component is processed once, and stack operations are O(1) amortized.
Space
O(n)
The stack stores directory names, which in the worst case can be all components of the path, leading to O(n) auxiliary space. The output string also requires O(n) space but is not counted as auxiliary.
Pattern Spotlight
Stack (Path Simplification)
Use a stack to simulate directory traversal: push directory names, pop on '..', and ignore '.' or empty components, enabling linear-time canonical path construction.
Solution
| 1 | class Solution:
|
| 2 | def simplifyPath(self, path: str) -> str:
|
| 3 | parts = path.split("/")
|
| 4 | stack = []
|
| 5 |
|
| 6 | for part in parts:
|
| 7 | if part == "" or part == ".":
|
| 8 | continue
|
| 9 | elif part == "..":
|
| 10 | if stack:
|
| 11 | stack.pop()
|
| 12 | else:
|
| 13 | stack.append(part)
|
| 14 |
|
| 15 | return "/" + "/".join(stack) |
Step-by-Step Solution
Split Path and Initialize Stack for Directory Tracking
| 3 | parts = path.split("/")
|
| 4 | stack = []
|
Objective
To decompose the input path into manageable components and prepare a stack to track the current directory state.
Key Insight
Splitting the path by '/' isolates directory names and special symbols ('.', '..'). An empty string or '.' means no directory change and can be skipped. The stack will represent the current path state, allowing efficient push/pop operations corresponding to moving into or out of directories.
Interview Quick-Check
Core Logic
Splitting by '/' transforms the path string into discrete components that can be processed sequentially.
Common Pitfalls & Bugs
Treating empty components from leading, trailing, or repeated slashes as real directory names instead of skipping them.
Process Each Path Component to Update Directory Stack
To iterate through each component and update the stack to reflect the current directory after applying Unix path rules.
Construct and Return the Canonical Path from Stack
To build the final simplified path string from the stack contents.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
elif part == "..":Check if the component is '..', indicating moving up one directory.
Recognizing '..' is critical to correctly simulate moving to the parent directory by popping the last directory from the stack.
if stack:Check if the stack is not empty before popping.
Preventing popping from an empty stack avoids invalid path states and respects the root directory boundary.
stack.pop()Pop the last directory from the stack to move up one level.
This operation simulates the effect of '..' in Unix paths, removing the most recent directory from the current path.
Full line-by-line criticality + rationale for all 11 lines available on Pro.
Test Your Understanding
Why is a stack the appropriate data structure for simplifying the Unix path?
See the answer with Pro.
Related Problems
Monotonic Stack pattern
Don't just read it. Drill it.
Reconstruct Simplify Path from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Simplify Path drill