71. Simplify Path (Medium)

Problem

Given a string path representing an absolute Unix file system path (starting with '/'), convert it to its simplified canonical form.

The rules:

A single period '.' refers to the current directory (no change).
A double period '..' moves up one level (pop the stack if non-empty).
Multiple consecutive slashes are treated as one.
Any other component is a valid directory name and gets pushed.

The result must start with '/' and must not end with '/' (unless it is the root itself).

Examples

"/home/" → "/home"
"/home//foo/" → "/home/foo"
"/home/user/Documents/../Pictures" → "/home/user/Pictures"
"/../" → "/" (cannot go above root)
"/a/./b/../../c/" → "/c"

LeetCode 71 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Split on slash, stack for components

Split the path on '/' to get individual components. For each component:

Skip empty strings (consecutive slashes or leading/trailing slash produce these).
Skip '.' (current directory, no movement).
On '..', pop the top of the stack if non-empty (move up one level).
Anything else is a directory name: push it.

Join the stack with '/' and prepend '/' for the result.

def simplify_path(path: str) -> str:
    parts = path.split("/")          # L1: O(n) split into components
    stack = []                       # L2: O(1) init
    for part in parts:               # L3: iterate each component
        if not part or part == ".":  # L4: skip empty string and current-dir dot
            continue
        elif part == "..":           # L5: go up one level
            if stack:                # L6: O(1) non-empty check
                stack.pop()          # L7: O(1) amortized pop
        else:
            stack.append(part)       # L8: O(1) push directory name
    return "/" + "/".join(stack)     # L9: O(n) join result

function simplifyPath(path: string): string {
    const parts = path.split('/');           // L1: O(n) split into components
    const stack: string[] = [];              // L2: O(1) init
    for (const part of parts) {             // L3: iterate each component
        if (!part || part === '.') continue; // L4: skip empty and current-dir dot
        if (part === '..') {                 // L5: go up one level
            if (stack.length) stack.pop();   // L6-L7: O(1) pop if non-empty
        } else {
            stack.push(part);                // L8: O(1) push directory name
        }
    }
    return '/' + stack.join('/');            // L9: O(n) join result
}

func simplifyPath(path string) string {
    parts := strings.Split(path, "/")        // L1: O(n) split into components
    stack := []string{}                      // L2: O(1) init
    for _, part := range parts {             // L3: iterate each component
        if part == "" || part == "." {       // L4: skip empty and current-dir dot
            continue
        } else if part == ".." {             // L5: go up one level
            if len(stack) > 0 {             // L6: O(1) non-empty check
                stack = stack[:len(stack)-1] // L7: O(1) pop
            }
        } else {
            stack = append(stack, part)      // L8: O(1) push directory name
        }
    }
    return "/" + strings.Join(stack, "/")    // L9: O(n) join result
}

final class Solution {
    func simplifyPath(_ path: String) -> String {
        var stack: [Substring] = []
        for component in path.split(separator: "/") {
            if component == "." { continue }
            if component == ".." {
                _ = stack.popLast()
            } else {
                stack.append(component)
            }
        }
        return "/" + stack.joined(separator: "/")
    }
}

Where the time goes, line by line

Variables: n = len(path), k = number of components after splitting.

Line	Per-call cost	Times executed	Contribution
L1 (split)	$O(n)$	1	$O(n)$
L3 (loop)	$O(1)$	k	$O(k)$
L4-L8 (per-component stack ops)	$O(1)$	k	$O(k)$
L9 (join)	$O(n)$	1	$O(n)$

k is at most n (each char could be its own component), so both $O(k)$ terms collapse into $O(n)$ .

Complexity

Time: $O(n)$ , driven by the split and join (L1, L9).
Space: $O(n)$ for the stack and parts list.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Key takeaways

Split on '/' first: it handles all slash-count variants in one step. No need to manually scan.
Empty string components come from leading '/', trailing '/', and multiple consecutive slashes; ignoring them is the cleanest way to handle all three cases at once.
The '..' rule only pops if the stack is non-empty: attempting to go above root is silently ignored, matching Unix behavior.
Joining with '/' and prepending a single '/' handles the root case (stack == [] gives "/" + "" == "/").

Valid Parentheses, another stack-as-pending-context problem
Decode String, nested structure resolved with a stack
Stacks, underlying data structure

Stack Parsing, the last open, first closed model for nested syntax and reversible operations.
Simulation, the explicit state model for executing rules exactly while keeping cases organized.

71. Simplify Path (Medium)

Problem

Try it yourself

Approach 1: Split on slash, stack for components

Key takeaways

Related topics

Related concepts