Skip to main content
DSA patterns

Simplify Path

mediumStrings Must-doGoogleMetaMicrosoft

Problem statement

You're given an absolute Unix-style file path, path, which always starts with a /. Rewrite it into its simplified, canonical form — the shortest path that points to the same place.

The rules for reading the input path:

  • A single . means "stay in the current directory" — it can be dropped.
  • A double .. means "go up to the parent directory" — it should remove the directory name before it, unless there's nothing above it to remove (going up from the root just stays at the root).
  • Repeated slashes, like // or ///, count as a single /.
  • Any other run of dots — "...", "...." — is just a normal directory or file name, not a "go up" instruction.

The rules for the output:

  • It starts with exactly one /.
  • Directory names are separated by exactly one /.
  • It never ends with a trailing /, unless the whole path is just the root /.
  • It never contains a lone . or .. segment.

This is exactly the cleanup step a shell or a file-serving API runs before trusting a path someone typed or a client sent — collapsing .. and redundant slashes into the one canonical location it actually refers to.

Examples

Example 1

Input: path = "/home/"

Output: /home

Explanation: The trailing slash is dropped — it doesn't change which directory the path points to.

Example 2

Input: path = "/home//foo/"

Output: /home/foo

Explanation: The double slash between home and foo collapses into one, and the trailing slash is dropped.

Example 3

Input: path = "/home/user/Documents/../Pictures"

Output: /home/user/Pictures

Explanation: .. cancels out the directory right before it (Documents), leaving /home/user/Pictures.

Example 4

Input: path = "/../"

Output: /

Explanation: There's nothing above the root to go up to, so .. at the root is simply ignored.

Example 5

Input: path = "/.../a/../b/c/../d/./"

Output: /.../b/d

Explanation: "..." is three dots, not two — it's a valid directory name here, not a "go up" instruction. a/.. cancels out, c/.. cancels out, and the trailing . and / are dropped, leaving /.../b/d.

Hints

Hint 1: Read the path one directory name at a time (splitting on /), and decide what to do with each name as you see it — you don't need to look at the whole path at once.

Approach

Optimal: Stack, manual scan — no split

Intuition

This is the same stack idea as the first approach, but instead of asking the language's split function to cut the whole path into tokens up front, it walks through the string once with two pointers: skip over any slashes, then read characters until the next slash to get one token. It reaches the exact same decision (push, pop, or skip) for each token — it just gets there without allocating an intermediate list of tokens first, which matters in a language like Java where split runs a small regex engine under the hood.

Steps

  1. Start with an empty stack and a position i = 0.
  2. While there's still string left to read:
    • Skip forward over any / characters.
    • Remember where the next token starts, then advance until the next / (or the end of the string) to find where it ends.
    • That slice is one token — apply the same three rules as before: skip if empty or ., pop if .., otherwise push it.
  3. Once i reaches the end of the string, every token has been handled.
  4. Join the stack with / and add the leading slash, exactly as before.

Dry run

path = "/.../a/../b/c/../d/./", tracing the two-pointer scan:

token found action stack after
"..." push (3 dots isn't ..) [...]
"a" push [..., a]
".." pop [...]
"b" push [..., b]
"c" push [..., b, c]
".." pop [..., b]
"d" push [..., b, d]
"." skip [..., b, d]

The trailing / after the final . just means the scan finds no more characters after skipping it — there's no separate "empty" token to handle the way the split-based version sees one. Joining the stack gives /.../b/d, matching example 5.

Edge cases: a path that is only slashes, like "///", never finds a non-slash character to start a token, so the stack stays empty and the result is the root /. A .. when the stack is already empty is a no-op, same as in the first approach.

Complexity

Time O(n) - Two nested `while` loops still only ever move forward through the string, so together they visit each character once.

Space O(n) - The stack can still hold every directory name in the worst case; the difference from the split-based version is that no separate list of tokens is built first.

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        n = len(path)
        i = 0
        while i < n:
            while i < n and path[i] == '/':
                i += 1
            start = i
            while i < n and path[i] != '/':
                i += 1
            token = path[start:i]
            if token == "" or token == ".":
                continue
            elif token == "..":
                if stack:
                    stack.pop()
            else:
                stack.append(token)
        return "/" + "/".join(stack)


if __name__ == "__main__":
    s = Solution()
    print(s.simplifyPath("/home/"))  # /home
    print(s.simplifyPath("/home//foo/"))  # /home/foo
    print(s.simplifyPath("/home/user/Documents/../Pictures"))  # /home/user/Pictures
    print(s.simplifyPath("/../"))  # /
    print(s.simplifyPath("/.../a/../b/c/../d/./"))  # /.../b/d
RecapThe whole problem in a few lines, for the night before
  • Spot it: "collapse a Unix-style path" — anything mentioning ., .., and redundant slashes
  • Idea: split (or scan) into directory-name tokens; push real names onto a stack, pop on .., skip . and empty tokens
  • Cost: O(n) time, O(n) space, where n is the length of the path
  • Trap: .. at an empty stack must be a no-op, not an error — and only the exact tokens "." / ".." are special, not every run of dots ("..." is a real name)

Interview follow-ups

  • What if the path uses backslashes (Windows-style, \) instead of forward slashes?

    Change the one character the algorithm splits or scans on — everywhere the code checks for /, check for \ instead (or accept either, if paths might mix them). The stack logic for ., .., and ordinary names doesn't change at all, since it never depended on which character happens to be the separator.

  • How would you also resolve a relative path (one that doesn't start with /), given a current working directory?

    Prepend the current working directory to the relative path with a / in between, then run the exact same algorithm on the combined string. The stack doesn't care whether the directories it starts with came from the "given" part of the path or the working directory — they're just names to push, pop, or skip in order.

  • The path could be up to 10 million characters, and this runs on every incoming request. What would you change?

    The algorithm is already O(n) with no wasted work, so there's nothing algorithmically better to do — the gain here is in avoiding repeated allocation. Reuse one stack (or one output buffer) across requests instead of allocating a fresh one each time, and prefer the manual-scan version over the split-based one, since it skips building an intermediate array of every token before processing begins.

Frequently asked questions

Real filesystems behave the same way — cd .. from / leaves you at /, it doesn't fail. The problem mirrors that: popping an already-empty stack simply does nothing, so a leading run of .. segments before any real directory has no effect at all.

The rule is deliberately about the exact token, not "a token made only of dots" — only the precise strings "." and ".." are special. Anything else made of dots, like "..." or "....", is indistinguishable from a name like "reports" as far as the algorithm is concerned, so it's pushed onto the stack like any other name.

Any service that accepts a path from a client — a file browser API, a storage proxy, a container's mounted-volume config — has to canonicalize it before trusting it, or a crafted ../../etc/passwd-style path can escape the directory it was supposed to be confined to. Collapsing .. and redundant slashes the way this problem does is the first step of that kind of path-traversal defense (the second step being to also confirm the result still starts inside the allowed directory).

You could track just the position of the last / in a result buffer you're building up, and truncate back to it when you see a .., which avoids a separate list structure. It's the same idea and the same O(n) cost, just implemented as index bookkeeping into a mutable buffer instead of push/pop on a list — a stack is simply the clearer way to describe and implement it.

No — both produce the exact same sequence of tokens and apply the exact same three rules to each one. The manual scan is worth knowing mainly because it avoids building an intermediate array of tokens up front (useful when memory is tight or split's regex engine is comparatively slow), not because it changes what gets pushed or popped.