106. Simplify Path

🔗 LeetCode Problem: 71. Simplify Path
📊 Difficulty: Medium
🏷️ Topics: Stack, String

Problem Statement

Given an absolute path for a Unix-style file system, which begins with a slash '/', transform it to its simplified canonical path.

In Unix-style file system context, a single period '.' signifies the current directory, a double period ".." denotes moving up one directory level, and multiple slashes such as "//" are interpreted as a single slash. In this problem, treat sequences of periods not covered by the previous rules (like "...") as valid names for files or directories.

The canonical path should adhere to the following format: - The path must start with a single slash '/'. - Directories within the path should be separated by only one slash '/'. - The path must not end with a trailing '/', unless it is the root directory. - The path must not have any single or double periods ('.' and '..') used to denote current or parent directory.

Return the simplified canonical path.

Example 1:

Input: path = "/home/"
Output: "/home"

Explanation: The trailing slash should be removed.

Example 2:

Input: path = "/home//foo/"
Output: "/home/foo"

Explanation: Multiple consecutive slashes are replaced by a single one.

Example 3:

Input: path = "/home/user/Documents/../Pictures"
Output: "/home/user/Pictures"

Explanation: A double period ".." refers to the directory up a level.

Example 4:

Input: path = "/../"
Output: "/"

Explanation: Going one level up from the root directory is not possible.

Example 5:

Input: path = "/.../a/../b/c/../d/./"
Output: "/.../b/d"

Explanation: "..." is a valid name for a directory in this problem.

Constraints: - 1 <= path.length <= 3000 - path consists of English letters, digits, period '.', slash '/' or '_'. - path is a valid absolute Unix path.

🌟 ELI5: The Simple Idea!

Think of navigating a file system:

Unix path rules:
  /home/user     → Normal path
  .              → Current directory (ignore)
  ..             → Parent directory (go back)
  //             → Multiple slashes = one slash
  /home/         → Trailing slash (remove)

Example: "/a/./b/../../c/"

Step by step:
  /a    → Go to directory 'a'
  /.    → Stay in same directory (ignore)
  /b    → Go to directory 'b' (now at /a/b)
  /..   → Go up one level (now at /a)
  /..   → Go up one level (now at /)
  /c    → Go to directory 'c' (now at /c)
  /     → Trailing slash (ignore)

Result: "/c"

The Stack Analogy:

Use stack to track directories:

/a    → Push 'a' → Stack: [a]
/.    → Ignore   → Stack: [a]
/b    → Push 'b' → Stack: [a, b]
/..   → Pop 'b'  → Stack: [a]
/..   → Pop 'a'  → Stack: []
/c    → Push 'c' → Stack: [c]

Build result: "/c" ✓

🎨 Visual Understanding

Example 1: Basic Simplification

Input: "/home//foo/"

Split by '/': ["", "home", "", "foo", ""]

Process each part:
  "" (empty) → Skip
  "home"     → Push to stack
  "" (empty) → Skip
  "foo"      → Push to stack
  "" (empty) → Skip

Stack: [home, foo]

Build result: "/" + "home" + "/" + "foo" = "/home/foo" ✓

Example 2: Going Up Levels

Input: "/a/./b/../../c/"

Split by '/': ["", "a", ".", "b", "..", "..", "c", ""]

Process:
  "" → Skip
  "a" → Push → Stack: [a]
  "." → Current dir, ignore → Stack: [a]
  "b" → Push → Stack: [a, b]
  ".." → Go up, pop 'b' → Stack: [a]
  ".." → Go up, pop 'a' → Stack: []
  "c" → Push → Stack: [c]
  "" → Skip

Stack: [c]

Result: "/c" ✓

Example 3: Can't Go Above Root

Input: "/../"

Split: ["", "..", ""]

Process:
  "" → Skip
  ".." → Try to go up, but stack empty → Ignore
  "" → Skip

Stack: []

Result: "/" (root) ✓

🎯 Approach: Stack with String Split ⭐

The Standard Solution

Algorithm:

1. Split path by '/' to get directories
2. Use stack to track current path
3. For each part:
   - If ".." and stack not empty: pop (go up)
   - If "." or empty: skip (ignore)
   - Otherwise: push (valid directory)
4. Build result by joining stack with '/'

Implementation

/**
 * Stack-based path simplification
 * Time: O(n), Space: O(n)
 */
public String simplifyPath(String path) {
    Stack<String> stack = new Stack<>();

    // Split by '/' and process each part
    String[] parts = path.split("/");

    for (String part : parts) {
        if (part.equals("..")) {
            // Go up one directory
            if (!stack.isEmpty()) {
                stack.pop();
            }
        } else if (!part.equals(".") && !part.isEmpty()) {
            // Valid directory name
            stack.push(part);
        }
        // Ignore "." and empty strings
    }

    // Build canonical path
    if (stack.isEmpty()) {
        return "/";
    }

    StringBuilder result = new StringBuilder();
    for (String dir : stack) {
        result.append("/").append(dir);
    }

    return result.toString();
}

⏰ Time: O(n) - Split and process once
💾 Space: O(n) - Stack and split array

Using Deque (Modern Approach)

public String simplifyPath(String path) {
    Deque<String> stack = new ArrayDeque<>();
    String[] parts = path.split("/");

    for (String part : parts) {
        if (part.equals("..")) {
            if (!stack.isEmpty()) {
                stack.pop();
            }
        } else if (!part.equals(".") && !part.isEmpty()) {
            stack.push(part);
        }
    }

    // Build result (note: Deque iteration order)
    StringBuilder result = new StringBuilder();
    if (stack.isEmpty()) {
        return "/";
    }

    // Need to reverse or build from bottom
    List<String> list = new ArrayList<>(stack);
    Collections.reverse(list);

    for (String dir : list) {
        result.append("/").append(dir);
    }

    return result.toString();
}

🔍 Super Detailed Dry Run

Example: path = "/a/./b/../../c/"

Goal: Simplify to canonical path

═══════════════════════════════════════════════════════════════
Step 1: Split by '/'
═══════════════════════════════════════════════════════════════

path.split("/") = ["", "a", ".", "b", "..", "..", "c", ""]

Explanation:
  "/a/./b/../../c/"
  Split points: ↑ ↑ ↑ ↑  ↑  ↑  ↑ ↑

  Before first '/': "" (empty)
  Between '/' and 'a': "a"
  Between 'a' and '.': "."
  Between '.' and 'b': "b"
  And so on...

parts = ["", "a", ".", "b", "..", "..", "c", ""]

═══════════════════════════════════════════════════════════════
Step 2: Process Each Part
═══════════════════════════════════════════════════════════════

stack = []

Iteration 1: part = ""
  Check: Is it ".."? No
  Check: Is it "."? No
  Check: Is it empty? Yes
  Action: Skip (ignore empty)
  Stack: []

Iteration 2: part = "a"
  Check: Is it ".."? No
  Check: Is it "." or empty? No
  Action: Valid directory → Push
  Stack: [a]

Iteration 3: part = "."
  Check: Is it ".."? No
  Check: Is it "."? Yes
  Action: Skip (current directory)
  Stack: [a]

Iteration 4: part = "b"
  Check: Is it ".."? No
  Check: Is it "." or empty? No
  Action: Valid directory → Push
  Stack: [a, b]

Iteration 5: part = ".."
  Check: Is it ".."? Yes
  Check: Is stack empty? No
  Action: Pop (go up one level)
  Popped: "b"
  Stack: [a]

Iteration 6: part = ".."
  Check: Is it ".."? Yes
  Check: Is stack empty? No
  Action: Pop (go up one level)
  Popped: "a"
  Stack: []

Iteration 7: part = "c"
  Check: Is it ".."? No
  Check: Is it "." or empty? No
  Action: Valid directory → Push
  Stack: [c]

Iteration 8: part = ""
  Check: Is it ".."? No
  Check: Is it "."? No
  Check: Is it empty? Yes
  Action: Skip
  Stack: [c]

═══════════════════════════════════════════════════════════════
Step 3: Build Result
═══════════════════════════════════════════════════════════════

Stack: [c]

Check: Is stack empty? No

Build canonical path:
  result = ""

  For each dir in stack (bottom to top):
    dir = "c"
    result = result + "/" + "c"
    result = "/c"

Return: "/c" ✓

Example 2: path = "/../"

Split: ["", "..", ""]

Process:
  "" → Skip → Stack: []
  ".." → Try pop, but stack empty → Skip → Stack: []
  "" → Skip → Stack: []

Stack is empty → Return "/" ✓

Example 3: path = "/home//foo/"

Split: ["", "home", "", "foo", ""]

Process:
  "" → Skip
  "home" → Push → [home]
  "" → Skip
  "foo" → Push → [home, foo]
  "" → Skip

Stack: [home, foo]

Build: "/home/foo" ✓

🎯 Why This Solution Works

The Stack Insight

Why stack is perfect:

1. Directory navigation is LIFO:
   /a/b/c
   Enter: a → b → c (push, push, push)
   Exit: c → b → a (pop, pop, pop)

2. ".." means "undo last directory":
   This is exactly what pop() does!

3. Stack maintains current path:
   Stack contents = directories from root to current

Handling Special Cases

Empty string / "." → Skip
  These don't change directory
  Ignore them

".." → Pop
  Go up one level
  But only if not at root (check isEmpty)

Multiple slashes "//" → Handled by split
  split("/") creates empty strings
  We skip empty strings

Trailing slash "/home/" → Handled by split
  Creates empty string at end
  We skip it

"..." or "....abc" → Valid directory names!
  Not "." or "..", so push to stack

Building the Result

Stack: [home, user, docs]

Build path:
  Start with "/"
  For each dir: append "/" + dir
  Result: "/" + "home" + "/" + "user" + "/" + "docs"
          = "/home/user/docs" ✓

Edge case (empty stack):
  Stack: []
  Means we're at root
  Return: "/" ✓

⚠️ Common Mistakes

Mistake 1: Not handling empty stack on ".."

// ❌ WRONG - EmptyStackException
if (part.equals("..")) {
    stack.pop();  // What if at root?
}

// ✓ CORRECT - Check first
if (part.equals("..")) {
    if (!stack.isEmpty()) {
        stack.pop();
    }
}

Mistake 2: Treating "..." as ".."

// ❌ WRONG - "..." is a valid directory name!
if (part.contains("..")) {
    stack.pop();
}

// ✓ CORRECT - Exact match only
if (part.equals("..")) {
    stack.pop();
}

Mistake 3: Wrong result building order

// ❌ WRONG - LIFO gives reversed order!
while (!stack.isEmpty()) {
    result.append("/").append(stack.pop());
}
// For [a, b, c] gives "/c/b/a" ✗

// ✓ CORRECT - Iterate normally (bottom to top)
for (String dir : stack) {
    result.append("/").append(dir);
}
// For [a, b, c] gives "/a/b/c" ✓

Mistake 4: Forgetting root-only case

// ❌ WRONG - Empty string for root!
StringBuilder result = new StringBuilder();
for (String dir : stack) {
    result.append("/").append(dir);
}
return result.toString();  // "" if stack empty!

// ✓ CORRECT - Handle empty stack
if (stack.isEmpty()) {
    return "/";
}

Mistake 5: Adding trailing slash

// ❌ WRONG - Adds trailing slash
result.append("/").append(dir).append("/");
// Gives "/home/" instead of "/home"

// ✓ CORRECT - No trailing slash
result.append("/").append(dir);

🎯 Pattern Recognition

Problem Type: Path Processing / Directory Navigation
Core Pattern: Stack Pattern 6 - Path Processing

When to Apply:
✓ File/directory path manipulation
✓ Navigation with up/back operations
✓ URL normalization
✓ Undo/redo with hierarchy

Recognition Keywords:
- "path"
- "directory"
- ".." (parent directory)
- "." (current directory)
- "canonical"
- "simplify"
- Unix/file system

Similar Problems:
- Crawler Log Folder (LC 1598) - Similar with "../"
- Basic Calculator (LC 224) - Nested operations
- Decode String (LC 394) - Nested structures

Key Components:
┌────────────────────────────────────────────┐
│ Stack: Track current path                 │
│ Split: By '/' separator                   │
│ ".." → Pop (go up)                        │
│ "." or empty → Skip                       │
│ Valid name → Push                         │
│ Build: Join with '/'                      │
│ Time: O(n), Space: O(n)                   │
└────────────────────────────────────────────┘

🧠 Interview Strategy

Step 1: "This is a path simplification problem"
Step 2: "I'll use a stack to track directories"
Step 3: "Split by '/', process each part"

Key Points to Mention:
- Split path by '/' to get components
- Stack tracks current directory path
- ".." means go up (pop)
- "." means current (skip)
- Empty means multiple slashes (skip)
- Build result by joining stack
- Handle edge case: empty stack = root

Walk Through Example:
"For '/a/./b/../../c/':
 Split: ['', 'a', '.', 'b', '..', '..', 'c', '']
 Process:
   'a' → Push: [a]
   '.' → Skip: [a]
   'b' → Push: [a,b]
   '..' → Pop: [a]
   '..' → Pop: []
   'c' → Push: [c]
 Result: '/c'"

Why Stack:
"Directory navigation is LIFO.
 '..' undoes last directory entry.
 Stack naturally handles this with pop.
 Stack contents represent path from root."

Complexity:
"Time: O(n) for split and process.
 Space: O(n) for stack and split array.
 Optimal for this problem."

Edge Cases to Mention:
✓ Root directory "/"
✓ Going above root "/../"
✓ Multiple slashes "///"
✓ Trailing slash "/home/"
✓ "..." as valid directory name

📝 Quick Revision Notes

🎯 Core Concept:

Simplify Path: Split by '/'. Use stack to track path. ".." → pop (go up). "." or empty → skip. Valid name → push. Build result: join stack with '/'. Handle empty stack → return "/".

⚡ Quick Implementation:

import java.util.Stack;

class Solution {
  public String simplifyPath(String path) {
    StringBuilder sb = new StringBuilder("/");
    Stack<String> stack = new Stack<>();
    String[] dirs = path.split("/");

    for(String dir : dirs) {
      if(dir.isEmpty()) {
        continue;
      }

      switch (dir) {
        case ".":
          // do nothing          
          break;
        case "..":
          // pop out
          if(!stack.isEmpty()) {
            stack.pop();
          }
          break;
        default:
          stack.push(dir);
          break;
      }
    }

    for(String s : stack) {
      sb.append(s).append("/");
    }

    if(!sb.toString().equals("/") && sb.charAt(sb.length() - 1) == '/') {
      sb.deleteCharAt(sb.length() - 1);
    }    

    return sb.toString();
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    System.out.println(s.simplifyPath("/home//////foo///")); // |||home||||||||||||foo|
    System.out.println(s.simplifyPath("/home/"));
    System.out.println(s.simplifyPath("/home//foo/"));
    System.out.println(s.simplifyPath("/home/user/Documents/../Pictures"));
    System.out.println(s.simplifyPath("/../"));
    System.out.println(s.simplifyPath("/.../a/../b/c/../d/./"));
  }
}

🔑 Key Insights:

Pattern: Stack Pattern 6 (Path Processing)
Split: By '/' separator
Three cases: ".." (pop), "." or empty (skip), valid (push)
Check empty: Before popping
Build order: Bottom to top (iterate, don't pop)
Time: O(n), Space: O(n) ✓

🎪 Memory Aid:

"Split path, stack tracks, '..' pops, build from stack!"
"Split, track, pop up, push valid, join!" ✨

⚠️ Three Critical Checks:

1. Before popping:
   if (!stack.isEmpty()) stack.pop();
   (Can't go above root!)

2. Valid directory check:
   !part.equals(".") && !part.isEmpty()
   (Skip "." and empty, but not "...")

3. Empty stack at end:
   if (stack.isEmpty()) return "/";
   (Root directory case!)

🧪 Edge Cases

Case 1: Root directory

Input: "/"
Output: "/"
Stack empty → root

Case 2: Can't go above root

Input: "/../"
Output: "/"
Try to pop empty stack → ignore

Case 3: Multiple slashes

Input: "/home//foo/"
Output: "/home/foo"
Empty strings from split → skip

Case 4: Current directory markers

Input: "/a/./b/."
Output: "/a/b"
"." → skip (current directory)

Case 5: Valid "..." directory

Input: "/.../a/../b/c/../d/./"
Output: "/.../b/d"
"..." is valid name, not special

Case 6: Complex navigation

Input: "/a/../../b/../c//.//"
Output: "/c"
Multiple ups and downs

All handled correctly! ✓

🎓 Complexity Analysis

Time Complexity: O(n)

Where n = path.length

Split: O(n)
  path.split("/") scans entire string

Process: O(k) where k = number of parts
  Each part processed once
  k ≤ n

Build result: O(k)
  Iterate through stack
  k ≤ n

Total: O(n) + O(k) + O(k) = O(n) ✓

Space Complexity: O(n)

Split array: O(k) where k ≤ n
  Stores all parts from split

Stack: O(k)
  Worst case: all valid directories
  Example: "/a/b/c/d"
  Stack: [a, b, c, d]

Result string: O(k)
  Final path

Total: O(n) ✓

🔄 Variations & Extensions

Extension 1: Windows Paths

// Handle backslash separator
String[] parts = path.split("[/\\\\]");

// Handle drive letters
if (parts.length > 0 && parts[0].matches("[A-Za-z]:")) {
    result.append(parts[0]);
    // Process rest normally
}

Extension 2: Return All Intermediate Paths

public List<String> getAllPaths(String path) {
    List<String> result = new ArrayList<>();
    Stack<String> stack = new Stack<>();

    for (String part : path.split("/")) {
        if (part.equals("..")) {
            if (!stack.isEmpty()) stack.pop();
        } else if (!part.isEmpty() && !part.equals(".")) {
            stack.push(part);
        }

        // Add current path
        result.add(buildPath(stack));
    }

    return result;
}

Same Pattern: - Crawler Log Folder (LC 1598) - Very similar with "../", "./", "x/" - Minimum Remove to Make Valid Parentheses (LC 1249)

Stack Processing: - Decode String (LC 394) - Nested structures - Basic Calculator (LC 224) - Operator precedence

Happy practicing! 🎯

Note: This problem teaches Stack Pattern 6: Path Processing! Master this and you understand: (1) directory navigation, (2) undo operations with stack, (3) string splitting and processing, (4) building results from stack. This pattern appears in file system problems, URL normalization, and undo/redo implementations. Common at Meta and Amazon! 💪✨