Simplify Path
Simplify Path is a medium stack problem solved with the stack basics pattern.
The best approach, optimal (single scan into one builder), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from split and stack up.
Problem
You are given an absolute Unix-style file path path (it starts with '/'). Return its canonical form.
In the input, "." means the current folder, ".." means the parent folder (at the root it stays at the root), and several slashes in a row act like one. Any other part, including names made only of dots such as "...", is an ordinary folder name.
The canonical path starts with a single '/', separates folder names with exactly one '/', has no trailing '/' (unless it is just "/"), and contains no "." or ".." parts.
Examples
Example 1
- Input
path = "/docs//./img/"- Output
"/docs/img"- Why
- The double slash collapses, the "." is dropped, and the trailing slash is removed.
Example 2
- Input
path = "/a/b/../../.."- Output
"/"- Why
- Two ".." climb back to the root; the third has nowhere to go and is ignored.
Example 3
- Input
path = "/.../x/../y"- Output
"/.../y"- Why
- Three dots are an ordinary folder name; ".." only cancels "x".
Constraints
1 <= path.length <= 3000pathcontains English letters, digits,'.','/'and'_'.pathis a valid absolute path (it starts with'/').
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Split and stack | O(n) | O(n) |
| Optimal (single scan into one builder) | O(n) | O(n) |
1Split and stack
O(n)Splitting, scanning the parts and joining are each linear in the path length.O(n)The parts array and the stack together hold up to n characters.Split the path on '/' and process the parts left to right with a stack of folder names. Skip empty parts and "."; on ".." pop if the stack is not empty; push anything else. Finally join the stack from bottom to top, each name preceded by '/', or return "/" if it is empty.
- parts = path.split("/").
- For each part: empty or "." → skip; ".." → pop if possible; otherwise push.
- Build "/" + name for each name from bottom to top; empty result → "/".
class Solution {
public String simplifyPath(String path) {
Deque<String> stack = new ArrayDeque<>();
for (String part : path.split("/")) {
if (part.isEmpty() || part.equals(".")) {
continue;
}
if (part.equals("..")) {
if (!stack.isEmpty()) {
stack.pollLast();
}
} else {
stack.addLast(part);
}
}
if (stack.isEmpty()) {
return "/";
}
StringBuilder sb = new StringBuilder();
for (String name : stack) {
sb.append('/').append(name);
}
return sb.toString();
}
}class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
for part in path.split("/"):
if part == "" or part == ".":
continue
if part == "..":
if stack:
stack.pop()
else:
stack.append(part)
return "/" + "/".join(stack)class Solution {
public:
string simplifyPath(string path) {
vector<string> st;
stringstream ss(path);
string part;
while (getline(ss, part, '/')) {
if (part.empty() || part == ".") continue;
if (part == "..") {
if (!st.empty()) st.pop_back();
} else {
st.push_back(part);
}
}
if (st.empty()) return "/";
string out;
for (auto& name : st) out += "/" + name;
return out;
}
};function simplifyPath(path) {
const stack = [];
for (const part of path.split("/")) {
if (part === "" || part === ".") continue;
if (part === "..") {
if (stack.length) stack.pop();
} else {
stack.push(part);
}
}
return "/" + stack.join("/");
}2Optimal (single scan into one builder)
O(n)Every character is read once and appended or truncated at most once.O(n)The output builder plus one saved length per folder.Skip the split and the list of strings. Scan the path with an index, reading one name at a time between slashes, and write the result straight into a single builder. Keep a stack of the builder lengths before each appended folder: ".." simply truncates the builder back to the last saved length. No intermediate strings are kept besides the current name.
- i = 0; while i < n: skip slashes; read the name from i up to the next '/'.
- "." or empty → nothing. ".." → if lengths is non-empty, cut the builder to lengths.pop().
- Otherwise push the builder's length, then append '/' and the name.
- Return the builder, or "/" if it is empty.
class Solution {
public String simplifyPath(String path) {
StringBuilder sb = new StringBuilder();
Deque<Integer> lengths = new ArrayDeque<>();
int n = path.length(), i = 0;
while (i < n) {
while (i < n && path.charAt(i) == '/') {
i++;
}
int start = i;
while (i < n && path.charAt(i) != '/') {
i++;
}
int len = i - start;
if (len == 0 || (len == 1 && path.charAt(start) == '.')) {
continue;
}
if (len == 2 && path.charAt(start) == '.' && path.charAt(start + 1) == '.') {
if (!lengths.isEmpty()) {
sb.setLength(lengths.pop());
}
continue;
}
lengths.push(sb.length());
sb.append('/').append(path, start, i);
}
return sb.length() == 0 ? "/" : sb.toString();
}
}class Solution:
def simplifyPath(self, path: str) -> str:
out = []
lengths = []
n, i = len(path), 0
while i < n:
while i < n and path[i] == '/':
i += 1
start = i
while i < n and path[i] != '/':
i += 1
name = path[start:i]
if name == "" or name == ".":
continue
if name == "..":
if lengths:
del out[lengths.pop():]
continue
lengths.append(len(out))
out.append('/')
out.extend(name)
return "".join(out) if out else "/"class Solution {
public:
string simplifyPath(string path) {
string sb;
vector<int> lengths;
int n = path.size(), i = 0;
while (i < n) {
while (i < n && path[i] == '/') i++;
int start = i;
while (i < n && path[i] != '/') i++;
int len = i - start;
if (len == 0 || (len == 1 && path[start] == '.')) continue;
if (len == 2 && path[start] == '.' && path[start + 1] == '.') {
if (!lengths.empty()) {
sb.resize(lengths.back());
lengths.pop_back();
}
continue;
}
lengths.push_back(sb.size());
sb += '/';
sb.append(path, start, len);
}
return sb.empty() ? "/" : sb;
}
};function simplifyPath(path) {
const out = [];
const lengths = [];
const n = path.length;
let i = 0;
while (i < n) {
while (i < n && path[i] === '/') i++;
const start = i;
while (i < n && path[i] !== '/') i++;
const name = path.slice(start, i);
if (name === "" || name === ".") continue;
if (name === "..") {
if (lengths.length) out.length = lengths.pop();
continue;
}
lengths.push(out.length);
out.push('/');
for (const ch of name) out.push(ch);
}
return out.length ? out.join('') : "/";
}Edge cases to test
- Just "/" or a run of slashes
- ".." at the root, which stays at the root
- Names made only of dots, such as "..." or "...."
- Names that contain dots, such as "a.b" or "..x"
- A trailing slash
Hints
Hint 1
Split the path on '/'. Empty parts (from repeated slashes) and "." change nothing.
Hint 2
".." undoes the most recent folder, which is exactly what popping a stack does.
Hint 3
Only the exact strings "." and ".." are special; any other part is a folder name, even if it is all dots.
FAQ
What is the best time complexity for Simplify Path?
Optimal (single scan into one builder) runs in O(n) time and O(n) extra space. Every character is read once and appended or truncated at most once.
Which pattern does Simplify Path use?
It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.
Is there a brute force solution for Simplify Path?
Yes. Split and stack takes O(n) time and O(n) space. Split the path on '/' and process the parts left to right with a stack of folder names.
Which edge cases should I test for Simplify Path?
Just "/" or a run of slashes; ".." at the root, which stays at the root; Names made only of dots, such as "..." or "...."; Names that contain dots, such as "a.b" or "..x"; A trailing slash.