#71 Simplify Path

frequently reported atMeta Microsoft Amazon Google

the problem

In plain words

Turn an absolute Unix path into its simplified canonical form: one '/' between names, no trailing '/', '.' means current directory, '..' means parent (staying at root if already there). Any other name, including '...', is a normal directory.

in path = "/home//foo/"

out "/home/foo"

in path = "/home/user/Documents/../Pictures"

out "/home/user/Pictures"

in path = "/../"

out "/"

in path = "/.../a/../b/c/../d/./"

out "/.../b/d"

1 ≤ path.length ≤ 3000
Letters, digits, '.', '/', '_'
path is a valid absolute path

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternStack for matching & nesting String parsing

where this runsFile Explorer's address bar and the terminal's cd .. resolve paths the same way: names go in, '..' comes back out.

Going into a directory is a push; '..' is a pop. The stack at the end, read bottom → top, is the path.

solutions

From brute force to optimal

Build the answer directly. A name appends "/name"; '..' cuts back to the last '/'.

Read names between slashes.
Skip empty and '.'.
'..' → setLength(lastIndexOf('/')) if non-empty.
Else append '/' + name.

timeO(n)

Each character is read once; each cut removes characters that were added once.

spaceO(n)

The builder.

javajava.util.*

1class Solution {2    public String simplifyPath(String path) {3        StringBuilder out = new StringBuilder(); // the result itself is the stack: "/a/b"4        int i = 0, n = path.length();5        while (i < n) {6            while (i < n && path.charAt(i) == '/') i++;       // skip slashes7            int start = i;8            while (i < n && path.charAt(i) != '/') i++;       // read one name9            String part = path.substring(start, i);10            if (part.isEmpty() || part.equals(".")) continue;11            if (part.equals("..")) {12                int cut = out.lastIndexOf("/");               // pop = cut back to the last '/'13                if (cut >= 0) out.setLength(cut);14            } else {15                out.append('/').append(part);                 // push16            }17        }18        return out.length() == 0 ? "/" : out.toString();19    }20}

Split into names; push real names, pop on '..', ignore '' and '.'. Join from the bottom.

path.split("/").
'' or '.' → skip; '..' → pop if not empty; otherwise push.
Build "/" + names from the bottom (pollLast).
Empty → "/".

timeO(n)

Splitting and joining are linear; each name is pushed/popped once.

spaceO(n)

The parts array and the stack.

javajava.util.*

1class Solution {2    public String simplifyPath(String path) {3        Deque<String> stack = new ArrayDeque<>();4        for (String part : path.split("/")) {5            if (part.isEmpty() || part.equals(".")) continue;  // "//" and "." change nothing6            if (part.equals("..")) {7                if (!stack.isEmpty()) stack.pop();              // go up (no-op at root)8            } else {9                stack.push(part);                               // "..." is a normal name10            }11        }12        StringBuilder sb = new StringBuilder();13        while (!stack.isEmpty()) sb.append('/').append(stack.pollLast()); // bottom = outermost dir14        return sb.length() == 0 ? "/" : sb.toString();15    }16}

in the room

How to say it in the interview

talk track

List the token rules first: '' and '.' do nothing, '..' pops, anything else pushes.
Point out that '...' is a valid name — a common trap.
Mention the join order: an ArrayDeque iterates top → bottom, so read from the tail.

traps

Popping on '..' when the stack is empty — must stay at root.
Joining the deque in iteration order and getting the path reversed.

what they ask next

Follow-ups

Support a current directory and relative paths (a 'cd' command)?

Start the stack with the current directory's parts unless the new path begins with '/'; then apply the same rules.

before you submit

Edge cases to test

'..' at the root stays at the root: "/../" → "/".
"..." and "..hidden" are ordinary folder names.
Repeated and trailing slashes: "/home//foo/" → "/home/foo".

practise next