Simplify Path

Difficulty: Medium Source: NeetCode

Problem

You are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplified canonical path.

The rules of a Unix-style file system are as follows:

A single period '.' represents the current directory.

A double period '..' represents the parent directory. Move to the parent of the current directory.

Any other valid sequence of characters represents a directory or file name.

Multiple consecutive slashes '//' are treated as a single slash '/'.

The simplified path must:

Start with a single slash '/'.

Directories within the path are separated by exactly one slash '/'.

Not end with a slash '/', unless it is the root directory.

Not have any single or double periods used to denote current or parent directories.

Example 1: Input: path = “/home/” Output: “/home”

Example 2: Input: path = “/../” Output: “/”

Example 3: Input: path = “/home//foo/” Output: “/home/foo”

Example 4: Input: path = “/a/./b/../../c/” Output: “/c”

Constraints:

1 <= path.length <= 3000

path consists of English letters, digits, period '.', slash '/' or '_'.

path is a valid absolute Unix path.

Prerequisites

Before attempting this problem, you should be comfortable with:

Stack — Used to track the current directory hierarchy as you process path components.
String splitting — Splitting on '/' tokenizes the path into components.

Splitting the path on '/' gives you a list of components. Empty strings result from consecutive slashes — you can ignore those. Single dots mean “stay here” — also ignore. Double dots mean “go up one level” — pop from the stack. Everything else is a real directory name — push it. Once processed, join the stack contents with '/' and prepend the root slash.

Algorithm

Split path on '/' to get components.
Initialize an empty stack.
For each component:
- Skip if it is empty or ".".
- Pop from the stack if it is ".." (only if the stack is non-empty).
- Otherwise push the component.
Return "/" + "/".join(stack).

Solution

def simplifyPath(path):
    stack = []

    for component in path.split("/"):
        if component == "" or component == ".":
            # Empty from double slash, or current directory — skip
            continue
        elif component == "..":
            # Go up one level — pop if possible
            if stack:
                stack.pop()
        else:
            # Valid directory or file name
            stack.append(component)

    return "/" + "/".join(stack)


# Test cases
print(simplifyPath("/home/"))               # Expected: "/home"
print(simplifyPath("/../"))                 # Expected: "/"
print(simplifyPath("/home//foo/"))          # Expected: "/home/foo"
print(simplifyPath("/a/./b/../../c/"))      # Expected: "/c"
print(simplifyPath("/"))                    # Expected: "/"
print(simplifyPath("/a/b/c/../../d"))       # Expected: "/a/d"
print(simplifyPath("/.../a/../b"))          # Expected: "/.../b"  ('...' is a valid dir name)

Complexity

Time: O(n) — splitting and joining are both linear in the path length.
Space: O(n) — the stack holds at most n/2 components.

Common Pitfalls

Treating "..." (three dots) as parent directory. Only ".." (exactly two dots) means “go up.” Any other sequence of dots — like "..." — is a valid directory name and should be pushed.

Not handling ".." at the root. Going “up” from the root should do nothing, not cause an error. The if stack: guard before popping handles this gracefully.

Forgetting to handle multiple consecutive slashes. path.split("/") naturally produces empty strings between consecutive slashes. Skipping empty components handles this without any special-case logic.

Adding a trailing slash. The join produces no trailing slash because "/".join([]) is "" and "/".join(["a", "b"]) is "a/b". The only slash comes from the explicit "/" you prepend.

Note Book