Problem Description

You are given an absolute path for a Unix-style file system that always starts with a slash '/'. Your task is to convert this path into its simplified canonical form.

The Unix-style file system follows these rules:

• A single period '.' means the current directory
• A double period '..' means the parent directory (go up one level)
• Multiple consecutive slashes like '//' or '///' should be treated as a single slash '/'
• Any sequence of periods that doesn't match the above rules (like '...' or '....') should be treated as a valid directory or file name

The simplified canonical path must:

• Start with a single slash '/'
• Separate directories with exactly one slash '/'
• Not end with a slash '/' (unless it's the root directory)
• Not contain any '.' or '..' as directory references

For example:

• Input: "/home/" → Output: "/home"
• Input: "/../" → Output: "/" (can't go above root)
• Input: "/home//foo/" → Output: "/home/foo"
• Input: "/a/./b/../../c/" → Output: "/c"

The solution uses a stack to process each directory component. When encountering '..', it pops from the stack (going up one directory). When encountering a valid directory name, it pushes to the stack. Finally, it joins all stack elements with '/' to form the canonical path.

Intuition

Think of navigating through directories like walking through rooms in a building. When you encounter a directory name, you enter that room (go deeper). When you see '..', you go back to the previous room (go up one level). When you see '.', you stay in the same room (no movement).

The key insight is that we need to keep track of our current path as we process each component. A stack is perfect for this because:

1. Directory navigation is inherently stack-like: When you enter a directory, you're adding to your path (push). When you go back with '..', you're removing the last directory you entered (pop).

2. We only care about the final state: We don't need to preserve the original path structure - we just need to know where we end up after all the navigation commands.

3. Sequential processing: We can process the path from left to right, making decisions about each component independently based on simple rules.

By splitting the path on '/', we get individual components that we can evaluate:

• Empty strings (from consecutive slashes) and '.' don't change our position
• '..' means go back (pop from stack if possible)
• Everything else is a real directory name to enter (push to stack)

After processing all components, the stack contains exactly the directories in our final path, in order from root to destination. Joining them with '/' and adding a leading '/' gives us the canonical path.

This approach naturally handles edge cases like trying to go above root (stack is empty, so pop does nothing) and multiple consecutive slashes (they create empty strings that we skip).

Learn more about Stack patterns.

Solution Approach

The solution uses a stack data structure to build the canonical path by processing each directory component sequentially.

Step-by-step implementation:

1. Split the path into components: Use path.split('/') to break the path into individual directory names. This automatically handles multiple consecutive slashes by creating empty strings between them.

2. Initialize an empty stack: stk = [] will store the valid directory names in our final path.

3. Process each component: Iterate through each substring s from the split operation:

   • Skip empty strings and current directory: If s is empty (from consecutive slashes) or equals '.', continue to the next iteration
   • Handle parent directory: If s == '..':
     • Check if the stack is not empty before popping (we can't go above root)
     • If stk has elements, call stk.pop() to remove the last directory
   • Handle regular directories: For any other string (including '...', '....', etc.):
     • Push it onto the stack with stk.append(s)

4. Build the final path: After processing all components:

   • Join all elements in the stack with '/' separator: '/'.join(stk)
   • Add a leading '/' to ensure the path starts with root: '/' + '/'.join(stk)
   • This automatically handles the root directory case (empty stack returns '/')

Example walkthrough with path "/a/./b/../../c/":

• Split: ['', 'a', '.', 'b', '..', '..', 'c', '']
• Process:
  • '' → skip
  • 'a' → stack: ['a']
  • '.' → skip, stack: ['a']
  • 'b' → stack: ['a', 'b']
  • '..' → pop, stack: ['a']
  • '..' → pop, stack: []
  • 'c' → stack: ['c']
  • '' → skip
• Result: '/' + 'c' = '/c'

The time complexity is O(n) where n is the length of the input path, and space complexity is O(n) for the stack storage.

Example Walkthrough

Let's trace through the path "/home/../usr/./bin/" step by step:

Initial Setup:

• Input path: "/home/../usr/./bin/"
• Split on /: ["", "home", "..", "usr", ".", "bin", ""]
• Initialize empty stack: []

Processing Each Component:

1. Component: "" (empty string)

   • This comes from the leading /
   • Action: Skip
   • Stack: []

2. Component: "home"

   • Valid directory name
   • Action: Push to stack
   • Stack: ["home"]

3. Component: ".."

   • Parent directory reference
   • Action: Pop from stack (remove "home")
   • Stack: []

4. Component: "usr"

   • Valid directory name
   • Action: Push to stack
   • Stack: ["usr"]

5. Component: "."

   • Current directory reference
   • Action: Skip (stay in same directory)
   • Stack: ["usr"]

6. Component: "bin"

   • Valid directory name
   • Action: Push to stack
   • Stack: ["usr", "bin"]

7. Component: "" (empty string)

   • This comes from the trailing /
   • Action: Skip
   • Stack: ["usr", "bin"]

Building Final Path:

• Join stack elements with /: "usr/bin"
• Add leading /: "/usr/bin"

Result: "/usr/bin"

The stack perfectly tracks our navigation: we entered "home", went back up with "..", entered "usr", stayed put with ".", then entered "bin". The final canonical path shows where we ended up after all these operations.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the path string.

The algorithm performs the following operations:

• path.split('/'): This operation traverses the entire string once to split it by '/', which takes O(n) time.
• The for loop iterates through each component produced by the split operation. In the worst case, there could be O(n) components (though typically much fewer).
• Inside the loop, each operation (append, pop, string comparison) takes O(1) time for each component.
• '/'.join(stk): This operation takes O(m) time where m is the total length of all strings in the stack, which is bounded by O(n) since these strings came from the original path.

Overall, the time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n), where n is the length of the path string.

The space usage includes:

• The stk list: In the worst case, if the path contains no '..' or '.' and all valid directory names, the stack could store all components from the path, using up to O(n) space.
• The result of path.split('/'): This creates a list of substrings that together can be at most O(n) characters.
• The final string created by '/' + '/'.join(stk): This creates a new string of length at most O(n).

Therefore, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly handling the root directory case

A common mistake is forgetting that when the stack is empty, the result should be "/" (root directory), not an empty string.

Incorrect approach:

# This would return an empty string for root directory
return '/'.join(directory_stack)  # Wrong: returns "" when stack is empty

Correct solution:

# Always prepend '/' to ensure we have at least the root
return '/' + '/'.join(directory_stack)  # Returns "/" when stack is empty

2. Not properly handling consecutive slashes

Some developers try to manually handle consecutive slashes with complex logic instead of leveraging the split function's behavior.

Incorrect approach:

# Trying to manually remove consecutive slashes
while '//' in path:
    path = path.replace('//', '/')  # Unnecessary preprocessing

Correct solution:

# split('/') naturally handles consecutive slashes by creating empty strings
path_components = path.split('/')
# Then just skip empty components in the loop
if not component or component == '.':
    continue

3. Treating special directory names incorrectly

A critical mistake is assuming that any sequence of dots should be treated specially. Only exactly "." and ".." have special meanings.

Incorrect approach:

# Wrong: treating "..." as going up multiple directories
if component.startswith('..'):
    for _ in range(len(component) - 1):
        if directory_stack:
            directory_stack.pop()

Correct solution:

# Only ".." means parent directory; "..." is a valid directory name
if component == '..':
    if directory_stack:
        directory_stack.pop()
else:
    # "...", "....", etc. are treated as regular directory names
    directory_stack.append(component)

4. Attempting to go above the root directory

When encountering ".." at the root level, some implementations might crash or produce incorrect results.

Incorrect approach:

# This could cause an error if stack is empty
if component == '..':
    directory_stack.pop()  # IndexError when stack is empty!

Correct solution:

# Always check if stack has elements before popping
if component == '..':
    if directory_stack:  # Only pop if there's something to pop
        directory_stack.pop()

5. Adding a trailing slash to the result

The problem specifically states that the result should not end with a slash unless it's the root directory.

Incorrect approach:

# Wrong: always adding a trailing slash
return '/' + '/'.join(directory_stack) + '/'

Correct solution:

# No trailing slash (except for root which is just "/")
return '/' + '/'.join(directory_stack)