71. Simplify Path — DSA Atlas

MediumStack and Expression ProcessingStackStack of path components

Simplify Path

Given an absolute Unix-style file path, return its canonical form. Collapse repeated slashes into one, drop '.' (current directory), and let '..' move up one directory (ignored at the root). The canonical path starts with a single '/', has no trailing '/', and has exactly one '/' between components.

Open official problem prompt ↗

In plain English

Reduce a messy absolute path to its unique simplest equivalent form.

Picture it like this

Walking through folders in a file browser: entering a folder is a push, clicking the 'up' button is a pop, and clicking the current folder ('.') does nothing.

Example

Input: path = "/a/./b/../../c/"
Output: "/c"
Why: '.' is skipped, 'b' is entered then removed by the first '..', 'a' is removed by the second '..', leaving only 'c'.

Constraints

1 <= path.length <= 3000path consists of English letters, digits, '.', '/' and '_'path is a valid absolute Unix path beginning with a single '/'

Pattern lesson

See the pattern, then code

Stack of path components

↗

Stack and Expression Processing

Nested structures, matching delimiters, undo behavior, or unresolved operations.. Split on '/', then treat real directory names as pushes and '..' as pops; '.' and empty tokens are noise. The stack ends holding the surviving directories in order.

New words, made simpleKnow these before the algorithm

Canonical path: The single simplest string that names the same directory, with no redundant slashes or dots.
'..': Parent directory; moves one level up, or stays put at the root.
'.': The current directory; contributes nothing to the path.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

In-place string surgery

Overlapping replacements are fiddly and rescans make it quadratic.

Repeatedly search for '/./' , '//' and '/name/../' substrings and delete them until stable.

Time O(n^2)Space O(n)

Best choiceSplit and stack

One clean pass that handles every rule locally.

Tokenize on '/', push real names, pop on '..', ignore '.' and empties, then rejoin.

Time O(n)Space O(n)

The rule we keep true

Invariant

The stack always holds the directory components of the simplified path for everything processed so far, top being the deepest current directory.

Why this is correct

Reasoning

Splitting on '/' isolates each component so the rules apply independently. '..' can only undo the immediately preceding real directory, which is the stack top, and a pop restores the correct parent. Ignoring '.' and empty tokens removes exactly the redundant pieces the canonical form forbids.

The algorithm in three movesSay these aloud before coding

1Split the path on '/'

push 'a' -> ['a']

2Skip empty tokens and '.'

push 'b' -> ['a','b']

3On '..' pop the stack if it is non-empty

'..' pops -> ['a']

4Otherwise push the directory name

'..' pops -> []

5Join the stack with '/' and prepend a leading '/'

push 'c' -> ['c']

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

..3

..4

1 · Read'a'

2 · AskName, dot, or up?

3 · Update statestack = ['a']

4 · ResultReal name, push

Key takeaway

Real names are pushed; each '..' pops the most recent directory, leaving ['c'].

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 4Tokenize
Splitting on '/' turns any run of slashes into empty strings that are naturally skipped.
2
Lines 5-6Drop noise
Empty tokens and '.' contribute nothing to the canonical path.
3
Lines 7-9Handle '..'
Pop only when the stack is non-empty so '..' at the root is a no-op.
4
Lines 12Reassemble
Joining with '/' and prepending one '/' produces exactly one separator between names and no trailing slash.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Root path '/' returns '/'
Trailing slash must be removed
Multiple consecutive slashes collapse to one
'..' at the root is ignored and cannot go above it
A directory literally named '...' is a valid name, not an up-command

Common beginner mistakes

Popping when the stack is empty for a leading '..'
Treating '...' or '..foo' as special when only exactly '..' means up
Forgetting to strip the trailing slash
Returning an empty string instead of '/' when the stack ends empty

Check your understanding

For path '/../', why is the answer '/' and not an error?

Simplify Path

Simplify Path

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Stack and Expression Processing