Leetcode 71. Simplify Path

Given an absolute Unix-style path, produce its canonical simplified form by collapsing multiple slashes and resolving "." (current dir) and ".." (parent dir) references. This is typically done by processing path segments (e.g., with a stack) to ensure a single leading slash, no trailing slash except for root, and no '.'/'..' tokens.

Asked at:

Meta

DESCRIPTION

You are given an absolute path in a Unix-style file system (always beginning with /). Your task is to convert this path into its simplified canonical form.

Rules of Unix Paths

A single period . → refers to the current directory.
A double period .. → refers to the parent directory (if one exists).
Multiple consecutive slashes (//, ///, etc.) are treated as a single /.
Any sequence of periods other than . or .. should be treated as a valid directory or file name (e.g., "..." or "....").

Requirements for the Canonical Path

Must begin with a single /.
Directory names must be separated by exactly one /.
Must not end with a trailing / (unless it is just /).
Should not contain . or .. symbols after simplification.

Examples

Input:


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

Output:


"/.../b/c"

Explanation: "..." is treated as a valid directory name.

Constraints:

Path is an absolute path starting with '/'
Path length is reasonable for practical file systems
Path contains only valid Unix path characters

Note: Any sequence of periods other than '.' or '..' should be treated as valid directory names

Cannot navigate above root directory

Multiple consecutive slashes are treated as single slash

Understanding the Problem

This problem is asking us to simulate navigating through a Unix file system and return the final canonical path. We need to handle several special cases:

Directory Navigation: Normal directory names just extend our current path
Current Directory ('.'): These should be ignored as they don't change our location
Parent Directory ('..'): These move us up one level in the hierarchy
Multiple Slashes: Should be treated as single separators
Trailing Slashes: Should be removed unless we're at root

The key insight is that we're essentially simulating a stack-based navigation system where we build up our path and occasionally need to backtrack.

Brute Force Approach

The most straightforward approach would be to repeatedly scan the entire path string and apply transformations until no more changes can be made.

We could iteratively:

Replace all consecutive slashes with single slashes using string replacement
Find each occurrence of '/.' and remove it (since it refers to current directory)
Find each occurrence of '/..' and remove it along with the preceding directory
Remove trailing slashes

This would require multiple passes through the string, and for each '..' we encounter, we'd need to scan backwards to find the previous directory to remove. In the worst case with many '..' operations, we might need to scan the entire string multiple times, leading to poor performance on deeply nested paths with many parent directory references.


def simplifyPath(path):
    while True:
        changed = False
        import re
        new_path = re.sub(r'/+', '/', path)
        if new_path != path:
            path = new_path
            changed = True
        new_path = path.replace('/.', '')
        if new_path != path:
            path = new_path
            changed = True
        dot_dot_index = path.find('/..')
        if dot_dot_index != -1:
            if dot_dot_index == 0:
                path = path[3:]
            else:
                prev_slash = path.rfind('/', 0, dot_dot_index)
                if prev_slash == -1:
                    prev_slash = 0
                path = path[:prev_slash] + path[dot_dot_index + 3:]
            changed = True
        if not changed:
            break
    if not path.startswith('/'):
        path = '/' + path
    if len(path) > 1 and path.endswith('/'):
        path = path[:-1]
    return path if path else '/'

Initialize path components array from input string

0 / 183

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n²) Due to checking all possible combinations

Space Complexity: O(n) Additional space for tracking

Building Intuition

What Data Structure is Ideal for this Problem?

After seeing the brute force limitations of multiple string scans, a stack becomes the perfect data structure because:

Natural Hierarchy Modeling: File systems are inherently hierarchical - directories contain subdirectories, and we navigate deeper or back up. A stack's LIFO (Last In, First Out) property perfectly mirrors this - the most recently entered directory is the first one we exit when going up.

Efficient Backtracking: When we encounter '..', we need to go back to the parent directory. With a stack, this is just a pop() operation - O(1) time. With string manipulation, we'd need to find and remove the last directory, which requires scanning.

Clean State Management: The stack maintains our current path state naturally. Each directory we enter gets pushed, each '..' pops the most recent entry, and '.' operations are simply ignored.

The breakthrough insight is recognizing that file system navigation is fundamentally a stack operation. Every time we enter a directory, we're 'pushing' onto our path stack. Every time we use '..', we're 'popping' from our path stack. This transforms a complex string manipulation problem into a simple stack simulation.

Common Mistakes

Trying to manipulate the string directly instead of breaking it into components

Forgetting that '...' (three or more dots) is a valid directory name, not a special operation

Not handling the edge case where '..' is used at the root level

Forgetting to handle multiple consecutive slashes properly

Not removing trailing slashes from the final result

Optimal Solution

Now that we understand why a stack is perfect for tracking our directory hierarchy, here's how we implement it:

Split and Filter: Split the path by '/' and filter out empty strings (from consecutive slashes) and '.' (current directory references)
Stack Processing: For each remaining component:
- If it's '..': pop from stack (if not empty) to go up one directory
- Otherwise: push the directory name onto the stack
Reconstruction: Join all stack elements with '/' and prepend with '/' for the root

The stack naturally handles the hierarchical nature of file systems - we build up the path as we go deeper, and '..' operations simply pop the most recent directory. This eliminates the need for multiple string scans and complex string manipulations.


def simplifyPath(path):
    stack = []
    components = path.split('/')
    
    for component in components:
        if component == '' or component == '.':
            continue
        elif component == '..':
            if stack:
                stack.pop()
        else:
            stack.append(component)
    
    return '/' + '/'.join(stack)

0 / 16

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) Single pass through the data

Space Complexity: O(n) Space for the data structure

What We've Learned

Stack for path navigation: Use a stack whenever you need to process hierarchical paths or nested structures where you might need to "go back" - the stack naturally handles the parent directory (`..`) operations by popping the last directory, mimicking how file systems work.
String splitting preprocessing: Split the path by `/` delimiter first, then process each component separately - this eliminates the complexity of handling multiple consecutive slashes and makes the logic focus purely on directory navigation rules.
Component-based validation: Treat each path component individually: ignore empty strings and `.`, pop from stack for `..`, and push everything else - this separation makes the algorithm robust and handles edge cases like `...` (valid directory name) vs `..` (parent reference).
Root directory boundary protection: Always check if the stack is empty before popping for `..` operations - attempting to go above root directory should be ignored, not cause errors, which prevents stack underflow and matches Unix filesystem behavior.
Efficient path reconstruction: Join the final stack contents with `/` and prepend a single `/` rather than building the string incrementally - this avoids repeated string concatenation overhead and naturally handles the empty stack case (root directory only).
Canonical form normalization: This tokenize-process-rebuild pattern applies broadly to parsing problems: configuration files, URL normalization, import path resolution - anywhere you need to simplify a hierarchical or nested input according to specific rules.

Test Your Understanding

Why is stack the right data structure for this problem?

stack provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late August, 2025

Meta

Staff

Early July, 2025

Meta

Senior

Mid June, 2025

Meta

Senior

variant that also included a cd command

Get Premium to View All 30+ Reports

Comments

Your account is free and you can post anonymously if you choose.

Leetcode 71. Simplify Path

DESCRIPTION

Rules of Unix Paths

Requirements for the Canonical Path

Examples

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

What Data Structure is Ideal for this Problem?

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact