Simplify Path

Medium Stack Stack Basics Original on LeetCode

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 <= 3000
  • path contains English letters, digits, '.', '/' and '_'.
  • path is 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.

00:00
Testcase

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.

ApproachTimeSpace
Split and stackO(n)O(n)
Optimal (single scan into one builder)O(n)O(n)

1Split and stack

TimeO(n)Splitting, scanning the parts and joining are each linear in the path length.
SpaceO(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.

  1. parts = path.split("/").
  2. For each part: empty or "." → skip; ".." → pop if possible; otherwise push.
  3. 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();
    }
}

2Optimal (single scan into one builder)

TimeO(n)Every character is read once and appended or truncated at most once.
SpaceO(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.

  1. i = 0; while i < n: skip slashes; read the name from i up to the next '/'.
  2. "." or empty → nothing. ".." → if lengths is non-empty, cut the builder to lengths.pop().
  3. Otherwise push the builder's length, then append '/' and the name.
  4. 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();
    }
}

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.