LeetCode 71 - Simplify Path

LeetCode Problem 71

Difficulty: 🟡 Medium
Topics: String, Stack

Solution

Problem Understanding

The problem gives us an absolute Unix-style file path and asks us to convert it into its canonical, simplified form.

An absolute path always starts from the root directory, represented by /. The input path may contain unnecessary components such as repeated slashes, references to the current directory, or references to parent directories. Our job is to normalize the path while following Unix filesystem rules.

The input string can contain four important types of path components:

1. Normal directory names such as "home" or "Documents"
2. A single period ".", which means "stay in the current directory"
3. A double period "..", which means "move to the parent directory"
4. Empty components caused by consecutive slashes such as "//"

The output must be a canonical path that satisfies all of the following:

• It starts with exactly one slash
• Directory names are separated by exactly one slash
• It does not end with a trailing slash unless the path is simply /
• It does not contain "." or ".." as navigation instructions

One subtle but very important detail is that only "." and ".." have special meanings. Strings such as "..." or "...." are treated as ordinary directory names. A naive implementation that treats any sequence of periods specially would produce incorrect results.

The constraints tell us that the path length can be at most 3000 characters. This is small enough that even moderately inefficient solutions may pass, but the natural optimal solution runs in linear time and is straightforward to implement.

Several edge cases are especially important:

• Moving above the root directory is not allowed, for example "/../" should still become "/"
• Multiple consecutive slashes should collapse into one
• Trailing slashes should be removed
• "." should be ignored completely
• ".." should remove the previous valid directory if one exists
• Names like "..." should remain untouched because they are valid directory names

Approaches

Brute Force Approach

A brute force solution could repeatedly scan and modify the string until no more simplifications are possible.

For example, we could:

• Replace "//" with "/"
• Remove occurrences of "/./"
• Resolve parent directory patterns such as "/a/../"

This process would continue repeatedly until the path stabilizes.

This works because every pass simplifies the path a little more, eventually reaching canonical form. However, repeatedly rebuilding and rescanning strings is inefficient. Every replacement operation may require traversing most of the string, and multiple passes may be needed.

In the worst case, this approach can become quadratic because each simplification may trigger another full scan of the path.

Optimal Approach

The key insight is that path processing naturally behaves like a stack problem.

When traversing directories:

• Entering a directory pushes it onto the current path
• Encountering ".." removes the most recent directory
• Encountering "." changes nothing

This exactly matches stack behavior.

We split the path using / as the separator and process each component one by one:

• Ignore empty strings and "."
• Pop from the stack for ".." if possible
• Push normal directory names onto the stack

At the end, the stack contains the canonical path components in order.

This approach processes each component exactly once, making it linear in time complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeated string rebuilding and rescanning
Optimal	O(n)	O(n)	Single pass using a stack

Algorithm Walkthrough

1. Split the path string using '/' as the delimiter.

This converts the path into individual components. Consecutive slashes naturally create empty strings, which we can ignore later.

Example:

"/home//foo/"

becomes:

["", "home", "", "foo", ""]

2. Create an empty stack.

The stack represents the current valid canonical path. Each directory name added to the stack represents moving deeper into the filesystem hierarchy. 3. Process each component one by one.

For every component:

• If the component is empty or ".", ignore it.

• Empty strings come from repeated slashes

• "." means stay in the current directory

• If the component is "..":

• Remove the most recent directory from the stack if one exists

• If the stack is already empty, do nothing because we cannot move above root

• Otherwise, treat the component as a valid directory name and push it onto the stack.

4. Reconstruct the canonical path.

Join all directory names in the stack using '/' and prepend a leading slash.

Example:

["home", "user", "Pictures"]

becomes:

"/home/user/Pictures"

5. Return the resulting string.

Why it works

The stack always maintains the correct canonical path for all components processed so far.

Whenever we enter a directory, we push it onto the stack. Whenever we encounter "..", we remove the most recent directory because moving to the parent directory reverses the most recent descent. Ignoring "." and empty strings preserves the correct filesystem semantics.

Since every component is processed exactly once and every operation maintains a valid path state, the final reconstructed path is guaranteed to be the correct canonical form.

Python Solution

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack: list[str] = []

        components = path.split("/")

        for component in components:
            if component == "" or component == ".":
                continue

            if component == "..":
                if stack:
                    stack.pop()
            else:
                stack.append(component)

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

The implementation begins by splitting the input path into components using / as the delimiter. This allows us to process each directory token independently.

The stack stores the valid directory hierarchy. Every normal directory name is appended to the stack because it represents descending into a directory.

When the algorithm encounters "..", it removes the most recent directory from the stack if possible. This simulates moving to the parent directory.

Empty strings and "." are ignored because they do not affect the canonical location.

Finally, the stack contents are joined together using single slashes, and a leading slash is added to produce the final canonical path.

Go Solution

func simplifyPath(path string) string {
    stack := []string{}

    components := strings.Split(path, "/")

    for _, component := range components {
        if component == "" || component == "." {
            continue
        }

        if component == ".." {
            if len(stack) > 0 {
                stack = stack[:len(stack)-1]
            }
        } else {
            stack = append(stack, component)
        }
    }

    return "/" + strings.Join(stack, "/")
}

The Go implementation follows the same logic as the Python solution. The main difference is that Go uses slices instead of dynamic lists.

Removing the top element from the stack is done using slice truncation:

stack = stack[:len(stack)-1]

The solution also uses strings.Split and strings.Join from the standard library, so the full LeetCode submission would require:

import "strings"

There are no integer overflow concerns because the algorithm only manipulates strings and slice indices.

Worked Examples

Example 1

Input:

"/home/"

Split components:

["", "home", ""]

Component	Action	Stack
""	Ignore empty	[]
"home"	Push directory	["home"]
""	Ignore empty	["home"]

Final path:

"/home"

Example 2

Input:

"/home//foo/"

Split components:

["", "home", "", "foo", ""]

Component	Action	Stack
""	Ignore	[]
"home"	Push	["home"]
""	Ignore	["home"]
"foo"	Push	["home", "foo"]
""	Ignore	["home", "foo"]

Final path:

"/home/foo"

Example 3

Input:

"/home/user/Documents/../Pictures"

Split components:

["", "home", "user", "Documents", "..", "Pictures"]

Component	Action	Stack
""	Ignore	[]
"home"	Push	["home"]
"user"	Push	["home", "user"]
"Documents"	Push	["home", "user", "Documents"]
".."	Pop	["home", "user"]
"Pictures"	Push	["home", "user", "Pictures"]

Final path:

"/home/user/Pictures"

Example 4

Input:

"/../"

Split components:

["", "..", ""]

Component	Action	Stack
""	Ignore	[]
".."	Cannot pop, already root	[]
""	Ignore	[]

Final path:

"/"

Example 5

Input:

"/.../a/../b/c/../d/./"

Split components:

["", "...", "a", "..", "b", "c", "..", "d", ".", ""]

Component	Action	Stack
""	Ignore	[]
"..."	Push valid directory	["..."]
"a"	Push	["...", "a"]
".."	Pop	["..."]
"b"	Push	["...", "b"]
"c"	Push	["...", "b", "c"]
".."	Pop	["...", "b"]
"d"	Push	["...", "b", "d"]
"."	Ignore	["...", "b", "d"]
""	Ignore	["...", "b", "d"]

Final path:

"/.../b/d"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character and component is processed once
Space	O(n)	Stack may store all path components

The algorithm performs a single pass over the path components. Each component is pushed onto or popped from the stack at most once, making all stack operations collectively linear.

The space complexity is linear because, in the worst case, every component may be a valid directory name that must be stored in the stack.

Test Cases

solution = Solution()

assert solution.simplifyPath("/home/") == "/home"  # trailing slash removal

assert solution.simplifyPath("/home//foo/") == "/home/foo"  # repeated slashes

assert solution.simplifyPath("/home/user/Documents/../Pictures") == "/home/user/Pictures"  # parent directory

assert solution.simplifyPath("/../") == "/"  # cannot move above root

assert solution.simplifyPath("/.../a/../b/c/../d/./") == "/.../b/d"  # valid multi-dot directory

assert solution.simplifyPath("/") == "/"  # root directory only

assert solution.simplifyPath("/.") == "/"  # current directory at root

assert solution.simplifyPath("/./././") == "/"  # repeated current directory references

assert solution.simplifyPath("/a/b/c") == "/a/b/c"  # already canonical

assert solution.simplifyPath("/a/../../b/../c//.//") == "/c"  # multiple pops and cleanup

assert solution.simplifyPath("/a//b////c/d//././/..") == "/a/b/c"  # mixed operations

assert solution.simplifyPath("/...") == "/..."  # dots as valid directory name

assert solution.simplifyPath("/..hidden") == "/..hidden"  # leading dots in filename

assert solution.simplifyPath("/a/..") == "/"  # return to root

assert solution.simplifyPath("/a/../..") == "/"  # attempt to go above root

assert solution.simplifyPath("/abc/.../def") == "/abc/.../def"  # preserve special names

Test	Why
"/home/"	Removes trailing slash
"/home//foo/"	Collapses repeated slashes
"/home/user/Documents/../Pictures"	Resolves parent directory correctly
"/../"	Prevents traversal above root
"/.../a/../b/c/../d/./"	Handles valid dot names and navigation
"/"	Root path edge case
"/."	Ignores current directory
"/./././"	Handles repeated "." references
"/a/b/c"	Leaves canonical path unchanged
"/a/../../b/../c//.//"	Multiple parent traversals
"/a//b////c/d//././/.."	Mixed complex normalization
"/..."	Preserves "..." as a valid directory
"/..hidden"	Preserves hidden-style names
"/a/.."	Returns correctly to root
"/a/../.."	Extra parent traversal beyond root
"/abc/.../def"	Keeps non-special dot sequences

Edge Cases

One important edge case is attempting to move above the root directory. For example, the input "/../../a" tries to traverse upward multiple times before entering "a". A buggy implementation might incorrectly create invalid negative traversal states. This implementation avoids that problem by only popping from the stack if the stack is non-empty.

Another critical edge case involves multiple consecutive slashes such as "/a///b//c/". Splitting on / creates empty string components. If those empty strings are treated as directories, the final output becomes incorrect. The implementation explicitly ignores empty components, which naturally collapses repeated slashes into a single separator.

A subtle but very common source of bugs is handling dot sequences incorrectly. Only "." and ".." are special. Strings such as "...", "....", or "..hidden" are ordinary directory names. Some naive solutions incorrectly treat any string containing periods as navigation syntax. This implementation checks for exact equality with "." and "..", ensuring that all other names remain valid path components.

Another edge case occurs when the final canonical path should be the root directory itself. For example, inputs like "/a/.." or "/./" eventually simplify to an empty stack. The implementation correctly reconstructs the path as "/" instead of returning an empty string.