Algorithm

Simplify Path

Stacks & Queues Pattern

Simplify Path

Given a string path, which is an absolute path to a file or directory in a Unix-style file system, convert it to the simplified canonical path. A single period '.' refers to the current directory, a double period '..' moves up one level, and multiple consecutive slashes are treated as a single slash. The canonical path must start with a single slash and must not end with a slash (unless it is the root).

CONSTRAINTS
  • 1 <= path.length <= 3000
  • path consists of English letters, digits, period, slash, or underscore
  • path is a valid absolute Unix path (starts with '/')
EXAMPLE 1
Input: path = "/home/"
Output: "/home"
Trailing slash removed. Directory 'home' is pushed once.
EXAMPLE 2
Input: path = "/../"
Output: "/"
Going up from root stays at root. Stack is empty after '..' on empty stack, result is '/'.
EXAMPLE 3
Input: path = "/home//foo/"
Output: "/home/foo"
Double slash creates an empty segment which is skipped.
What if '..' appears at the root level?
In Unix, going above root stays at root. The stack simply stays empty — we only pop if the stack is non-empty.
Does the output require a trailing slash?
No, except for the root '/'. Join the stack with '/' and prepend a single '/' — no trailing slash added.

When you are navigating through folders on a computer, you are building a history of where you have been. If you go into folder A, then B, and then hit "..", you are not just deleting text—you are undoing your last move and jumping back to A.

This Undo behavior is why a Stack is the perfect data structure for simplifying file paths. A Stack remembers the sequence of your deeper dives and allows you to pop the most recent directory the moment it gets cancelled by a ".." command.

The Breadcrumb Trail

- Splitting the Noise: First, we ignore all the extra slashes. By splitting the path by "/", we get a clean list of individual commands: folder names, dots ("."), or double-dots ("..").
- Filtering the Segments:
- Folder Name: This is a deep dive. Push it onto the Stack.
- "." (Current Dir): This does nothing. Ignore it.
- ".." (Parent Dir): This is the undo button. Pop the most recent folder off the Stack. If you are already at the root, ignore it (you cannot go higher than home!).
- The Final Assembly: After processing all segments, the folders remaining in the Stack represent your final, direct path. Just join them back together with slashes!

Code Blueprint
text
stack = []
segments = path.SPLIT('/')

FOR each part in segments:
    IF part is ".." :
        IF stack is NOT empty:
            stack.POP()
    ELSE IF part is empty OR part is "." :
        CONTINUE
    ELSE:
        stack.PUSH(part)

RETURN "/" + stack.JOIN('/')
Worked Example:/a/./b/../../c/
0
a
Top
Split components: ['a', '.', 'b', '..', '..', 'c']. Parse 'a': Push directory 'a' to stack. Stack = ['a'].
0
a
Parse '.': Dot represents current directory. Do nothing. Stack = ['a'].
0
a
1
b
Top
Parse 'b': Push directory 'b' to stack. Stack = ['a', 'b'].
0
a
Top
Parse '..': Double dot. Pop directory 'b' (go up one level). Stack = ['a'].
Parse '..': Double dot. Pop directory 'a' (go up to root). Stack is now empty.
0
c
Top
Parse 'c': Push directory 'c'. End of components. Join stack with slashes. Result: '/c'.
Interactive Strategy Visualization
PATH NORMALIZATION INSIGHT

Unix-style traversal logic with Stack

/
home
foo
..
bar
/

Mental Model

  • Breadcrumb Trail: The stack acts as a breadcrumb trail of your location.
  • Backtracking: `..` means "go back", modeled by `stack.pop()`.
LOGICSTEP 1/6
Process '/home/foo/../bar/'
RULES

Canonical Path Rules

1. Always start with `/`. 2. Single `/` between directories. 3. No trailing `/`. 4. Remove `.` and handling `..`. The stack approach handles all these naturally.

O(N) One Pass · O(N) Stack of Live Folders