AlgoMaster Logo

Simplify Path

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We need to take a messy Unix file path and clean it up into its canonical form. When you type cd /home/user/../Documents/./photos// in a terminal, the shell resolves all the .. (go up one directory), . (stay in current directory), and extra slashes before navigating. We need to do the same thing programmatically.

The parts that need care:

  • .. should go up one level, but it cannot go above the root /.
  • . does nothing and should be ignored.
  • Multiple slashes act like one.
  • Sequences like ... or .... are valid directory names, not special commands.

This maps onto a stack. As we process each directory name in the path, we either push it onto a stack (a real directory), skip it (.), or pop from the stack (..). The final stack gives us the simplified path. A stack fits because .. always undoes the most recent directory we entered, the last-in-first-out behavior a stack provides.

Key Constraints:

  • 1 <= path.length <= 3000 -> The input is small, so a single linear pass is fast enough and no performance tricks are needed.
  • path consists of letters, digits, ., /, or _ -> The only special tokens to detect are ., .., and the / separator. Everything else is a directory name.
  • path is a valid absolute Unix path -> It always starts with /, so the input needs no validation.

Approach 1: Manual Character-by-Character Parsing

Intuition

Without a split function, we walk through the path character by character, building up each directory name as we go. Each / (or the end of the string) marks the end of a complete component to process.

A stack holds the directories of the simplified path. For each component we extract:

  • If it is empty or ".", skip it.
  • If it is "..", pop from the stack (when the stack is not empty).
  • Otherwise, push it onto the stack.

This version avoids building an intermediate array of components, processing one character at a time directly off the input.

Algorithm

  1. Initialize an empty stack and a variable component to build the current directory name.
  2. Append a trailing / to the path so the last component gets processed in the loop.
  3. Iterate through each character in the path:
    • If the character is /, process the current component:
      • If the component is ".." and the stack isn't empty, pop from the stack.
      • If the component is non-empty and not "." and not "..", push it onto the stack.
      • Reset the component to empty.
    • Otherwise, append the character to the component.
  4. Build the result by joining the stack contents with / and prepending a /.

Visualization and Code

Loading animation...

The character-by-character parsing is correct but verbose. Splitting the path by / up front removes the manual tokenization and leaves only the stack logic to write.

Approach 2: Split and Stack (Optimal)

Intuition

Instead of parsing characters one at a time, we split the entire path by / at once. This gives an array of components, where empty strings come from consecutive slashes and the rest are directory names, ., or ...

The processing then reduces to three rules over the components:

  • Skip empty strings and ".".
  • For "..", pop from the stack when it is not empty.
  • For anything else, push it onto the stack.

The final answer is / followed by the stack contents joined with /. The logic is the same stack as Approach 1, but the split handles tokenization, so there is less code to get wrong.

Algorithm

  1. Split the path by "/" to get an array of components.
  2. Initialize an empty stack (list/deque).
  3. For each component:
    • If it's empty or ".", skip it.
    • If it's "..", pop from the stack if the stack isn't empty.
    • Otherwise, push the component onto the stack.
  4. Return "/" + stack contents joined by "/".

Visualization and Code

Loading animation...