LeetCode 71 – Simplify Path

Simplify Path is a stack problem that arrives disguised as string manipulation, and the reason it is worth doing is that the stack is not an optimisation here — it is the only structure that models what .. actually means. Once you see "go up one level" as "undo the last thing I did", the code writes itself.

The problem

Given an absolute Unix-style file path, return its canonical form. In the canonical path: a single slash separates components, there is no trailing slash, and no component is . or ...

"/home/"            -> "/home"        trailing slash dropped
"/home//foo/"       -> "/home/foo"    repeated slashes collapse
"/../"              -> "/"            the root's parent is the root
"/a/./b/../../c/"   -> "/c"
"/..."              -> "/..."         three dots is an ORDINARY name
"/"                 -> "/"
"/a//b////c/d//././/.." -> "/a/b/c"

"/..." is the one that catches people. Only exactly two dots means parent. Three dots, or "..a", or "a..", are just filenames, and a solution that tests startsWith("..") gets them wrong.

Why a stack

Walk the components left to right and ask what each one does to the path you have built so far:

a name   push it
"."      nothing -- "stay here"
".."     pop the last one -- "undo the previous push"
""       nothing -- an artefact of "//" or the leading "/"

"Undo the most recent operation" is the definition of a stack, which is why nothing simpler works. You cannot resolve .. with a counter, because you need to know which component to remove, and you cannot do it with a single backward pass, because .. can chain.

Splitting is doing more work than it looks

Splitting on "/" handles three of the four cases for free, which is worth noticing rather than writing code to handle them:

"/home//foo/".split("/")  ->  ["", "home", "", "foo"]
                               ^^         ^^
                          leading slash   the doubled slash

Both collapse to empty strings, and empty strings are skipped by the same branch that skips ".". So repeated slashes, the leading slash and any trailing slash all disappear without a dedicated rule. Say that out loud — an interviewer watching you write three special cases for things the split already handled is watching you add bugs.

The pop that must not throw

".." at the root is a no-op, not an error: /.. is / on every Unix system. So the pop has to tolerate an empty stack. In Java that is the difference between two nearly identical methods:

stack.removeLast()   throws NoSuchElementException when empty
stack.pollLast()     returns null when empty  <-- the one you want

Picking pollLast deliberately, and being able to say why, reads much better than an if (!stack.isEmpty()) wrapper — though that is equally correct and clearer in Python, which has no such pair.

Java

class Solution {
    public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<>();

        for (String part : path.split("/")) {
            if (part.isEmpty() || part.equals(".")) {
                continue;                       // "//", the leading "/", and "."
            } else if (part.equals("..")) {
                stack.pollLast();               // at the root this is a no-op, not an error
            } else {
                stack.addLast(part);            // ".." is EQUALS, so "..." lands here
            }
        }

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

        return out.length() == 0 ? "/" : out.toString();
    }
}

Use ArrayDeque rather than Stack. Stack extends Vector, so every operation is synchronised for no benefit, and — the part that actually matters here — iterating a Stack yields elements bottom-to-top while stack.pop() takes from the top, so the two disagree about which end is which. Building the output by iteration is where that bites.

Appending '/' before each component gives the leading slash for free and no trailing one, so the only special case left is the empty stack.

Python

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack: list[str] = []

        for part in path.split("/"):
            if part == "" or part == ".":
                continue
            if part == "..":
                if stack:                 # the root's parent is the root
                    stack.pop()
            else:
                stack.append(part)

        return "/" + "/".join(stack)

The return is one line and needs no empty check: "/".join([]) is "", so the result is "/" exactly when the stack is empty. Worth pointing at — it is the kind of thing that makes a reviewer trust the rest of the function.

Complexity

Each component is pushed at most once and popped at most once, so the total work is linear in the length of the path despite the nested-looking structure. The space is genuinely O(n) and cannot be improved: "/a/b/c/d/e" has no redundancy to remove, so the output is as long as the input.

Splitting allocates the component array up front. Scanning with two indices and slicing lazily avoids it, and is worth mentioning if asked about memory — but it trades clear code for a constant factor, which is rarely the right call in an interview.

What the interviewer is checking

• That you reach for a stack because .. means undo, not because stacks are handy.
• That splitting on "/" handles doubled and trailing slashes for free.
• ".." compared with equality, so "..." stays a filename.
• That popping an empty stack is a no-op — /.. is /.
• The root path "/", and a path that reduces to it.
• No trailing slash on the output, and always a leading one.
• ArrayDeque over Stack, and why the iteration order matters.