Simplify Path: Stack-Based Directory Navigation

Simplify Path is LeetCode 71, rated Medium, and it is a clean example of using a stack to process structured tokens. If you have ever typed cd /a/./b/../../c/ in a terminal and wondered what path you end up at, this problem is asking you to compute that.

The core insight is that a Unix file path is just a sequence of navigation commands separated by slashes. A stack lets you track your current position by pushing directory names and popping when you see ... Once you see it that way, the solution writes itself.

The problem

You are given a string path representing an absolute Unix-style file path (starting with a slash). Convert it to its simplified canonical form.

The rules:

• A single period "." refers to the current directory. It does nothing.
• A double period ".." moves up to the parent directory. If you are already at root, it stays at root.
• Multiple consecutive slashes (//) are treated as a single slash.
• Trailing slashes are removed.
• The result must start with a single / and have no trailing slash (unless the result is root / itself).

Examples:

• "/home/" becomes "/home"
• "/a/./b/../../c/" becomes "/c"
• "/../" becomes "/" (cannot go above root)
• "/home//foo/" becomes "/home/foo"

The approach

Split the path by "/" and you get a list of tokens. Some of those tokens are directory names you want to keep, and others are navigation commands or empty strings from consecutive slashes.

Here is the full algorithm:

1. Split the path string by "/".
2. Initialize an empty stack.
3. Iterate through each token:
   • If the token is empty or ".", skip it.
   • If the token is "..", pop from the stack (if the stack is not empty).
   • Otherwise, the token is a directory name. Push it onto the stack.
4. Join the stack elements with "/" and prepend a leading "/".

That is it. The stack naturally tracks which directories you are inside, and popping handles the parent navigation. At the end, the stack contains exactly the directories in the canonical path, from root to deepest.

Visual walkthrough

Let's trace through "/a/./b/../../c/". After splitting by "/", the tokens are ["", "a", ".", "b", "..", "..", "c", ""]. The empty strings from leading and trailing slashes get skipped. Watch how the stack builds up the final path.

The stack ends with ["c"], so the result is "/" + "/".join(["c"]) which gives "/c". That matches what you would get by navigating this path in an actual terminal.

The code

Here is the Python solution for LeetCode 71, Simplify Path:

def simplify_path(path: str) -> str:
    stack = []

    for token in path.split("/"):
        if token == "..":
            if stack:
                stack.pop()
        elif token and token != ".":
            stack.append(token)

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

Let's walk through the important details:

• Splitting by "/" produces empty strings for leading slashes, trailing slashes, and consecutive slashes. For example, "/a//b/" splits into ["", "a", "", "b", ""]. The condition token and token != "." filters out all empty strings and single dots in one check.
• Order of checks. You check for ".." first, then filter out empty and "." tokens, then push everything else. This keeps the logic flat with no nesting.
• Pop safety. The if stack guard before stack.pop() handles the case where ".." appears when you are already at root. You simply ignore it, which matches Unix behavior.
• Building the result. "/".join(stack) combines the directory names with slashes, and prepending "/" gives the leading slash. If the stack is empty (you ended up at root), the result is just "/".

Complexity analysis

Time: O(n). Splitting the string takes O(n). Iterating through the tokens is O(n). Each token is pushed or popped at most once, and both operations are O(1). Joining the stack at the end is O(n). Total: O(n).

Space: O(n). The split produces up to O(n) tokens. The stack holds at most O(n) directory names. The output string is at most O(n) characters. Everything is linear.

You cannot do better than O(n) time because you must read every character of the input. The solution is optimal.

The building blocks

This problem is built on two core building blocks:

Stack-based parsing

The pattern of walking through a sequence of tokens and using a stack to track state. You push elements when they represent something to keep, and pop when you encounter a "go back" signal. This is the same structure behind:

• Valid Parentheses: push openers, pop on closers
• Evaluate Reverse Polish Notation: push numbers, pop on operators
• Min Stack: push with tracking, pop with cleanup
• Basic Calculator: stack-driven expression evaluation

In Simplify Path, directory names get pushed and ".." triggers a pop. The stack always reflects your current position in the directory tree.

Token filtering

Before the stack logic even runs, you need to separate meaningful tokens from noise. Splitting by a delimiter and then filtering out empty or irrelevant results is a pattern that appears in many string problems. Here, splitting by "/" and discarding "" and "." reduces the problem to a clean sequence of directory names and ".." commands.

Edge cases to watch for

These are the cases that trip people up in interviews and test suites:

• Root only. "/" splits into ["", ""]. Both tokens are empty, both get skipped. The stack stays empty, and the result is "/". Correct.
• Consecutive slashes. "/home//foo/" splits into ["", "home", "", "foo", ""]. Empty strings are filtered out, leaving ["home", "foo"]. Result: "/home/foo".
• ".." at root. "/../" tries to pop from an empty stack. The if stack guard prevents an error, and the result is "/". This matches Unix behavior where cd .. at root keeps you at root.
• Trailing slash. "/home/" splits into ["", "home", ""]. The trailing empty string is filtered. Result: "/home". No trailing slash in the output.
• Deeply nested ".." sequences. "/a/b/c/../../../d" pops c, then b, then a, leaving the stack empty before pushing d. Result: "/d".

From understanding to recall

The Simplify Path solution is short. The core logic is about 8 lines. But under interview pressure, the small details matter. Do you split by "/" or iterate character by character? Do you check ".." before or after the empty-string filter? What do you return when the stack is empty?

These are not conceptual gaps. They are recall gaps. You understand the algorithm right now, but producing it from scratch in three weeks is a different skill entirely.

Spaced repetition bridges that gap. You type the path simplifier from memory at increasing intervals. Each repetition reinforces the split-filter-push-pop flow, the pop safety guard, and the join step. After a few cycles, the whole thing is automatic. You do not fumble the details under pressure because you have already written this code a dozen times.

Related posts

• Valid Parentheses - The classic stack-based parsing problem, using the same push/pop pattern for bracket matching
• Evaluate Reverse Polish Notation - Another stack parsing problem where tokens drive push and pop operations in sequence

CodeBricks breaks the Simplify Path stack algorithm into its reusable building blocks and drills them with spaced repetition. You type the solution from scratch each time, so when LeetCode 71 or any path-processing problem comes up in an interview, the code flows without hesitation.