Generated by Codex with GPT-5

Quick facts

Problem gist

The task is to turn a Unix-style absolute path into its canonical form. A canonical path always starts with one slash, uses one slash between directory names, has no trailing slash unless the path is the root, and removes navigation tokens that do not represent real directory names.

The tricky tokens are simple once separated from ordinary names. An empty token comes from repeated slashes and should be ignored. A single dot means “stay here” and should also be ignored. A double dot means “go to the parent directory”; for an absolute path, trying to go above the root simply keeps you at the root. Every other token, including names with dots such as ... or a.b, is a real directory name.

Deriving the stack solution

Think of the canonical path as the list of directories from the root to the current location. That list behaves like a stack. When the parser sees a normal directory name, it pushes the name. When it sees .., it pops the most recent directory if one exists. When it sees . or an empty token, it does nothing.

After every token has been processed, the stack contains exactly the directory names that should appear in the final path, in order. Joining them with slashes and adding the leading slash produces the canonical absolute path. If the stack is empty, the same join expression naturally produces /.

This is optimal because every character only needs to be inspected as part of splitting and processing its component. The algorithm runs in O(n) time for a path of length n, and uses O(d) extra space for the remaining directory depth.

Python solution

class Solution:
    def simplifyPath(self, path: str) -> str:
        canonical_components = self._build_canonical_components(path)
        return "/" + "/".join(canonical_components)

    def _build_canonical_components(self, path: str) -> list[str]:
        canonical_components: list[str] = []

        for component in path.split("/"):
            if component == "" or component == ".":
                # Repeated slashes and current-directory markers do not change
                # the canonical location.
                continue

            if component == "..":
                # Absolute paths cannot move above root, so an empty stack stays
                # empty when another parent-directory marker appears.
                if canonical_components:
                    canonical_components.pop()
                continue

            # Any other token is a literal directory name, even if it contains
            # dots, such as "..." or "a.b".
            canonical_components.append(component)

        return canonical_components

Edge cases to remember

Paths with repeated slashes, such as /home//foo/, should behave as if there were only one separator between names. A path that climbs too far upward, such as /../../a, should become /a because absolute paths cannot escape the root. Directory names are only special when the whole component is exactly . or ..; a component like ... is just a normal name.

Interview follow-ups

What changes if the path can be relative?

For a relative path, leading .. components cannot always be discarded. The same stack idea still works, but the parser must preserve unresolved parent moves when there is no earlier directory name to cancel. For example, ../../a/./b should usually normalize to ../../a/b, not /a/b. The main tradeoff is that the return format now depends on whether the input had a root, so the implementation should track an is_absolute flag and apply different rules when .. appears on an empty stack.

Can the solution avoid calling split?

Yes. A streaming parser can scan the string character by character, build the current component until it reaches a slash, then apply the same stack rules to that component. This keeps the same O(n) time complexity and still uses O(d) stack space, but it avoids allocating the full list of split components at once. That matters when the path is very large or when the parser is reading from a stream.

Symbolic links cannot be handled correctly by string normalization alone because the meaning of a component depends on file-system metadata. A resolver would need to walk components from left to right, check whether each real component is a symlink, replace it with the symlink target when needed, and then continue normalizing. It also needs cycle detection, a maximum symlink depth, and careful handling of relative symlink targets. The complexity is no longer just about string length; it also depends on file-system lookups.

How would this work for Windows paths?

The core stack idea is still useful, but parsing rules change. The implementation must recognize both \ and / as separators, preserve drive roots such as C:\, and decide how to handle UNC paths like \\server\share. It should also be explicit about case sensitivity because Windows path comparison is usually case-insensitive, while Unix path comparison is usually case-sensitive. The normalization logic stays linear, but the tokenizer and root handling become more detailed.