Shorten Path

Tags

Shorten Path

Category

Stacks

Difficulty

Hard

Problem Statement

Given a Unix-style file path as a string, simplify it to its canonical form. The path may contain "." (current directory), ".." (parent directory), multiple consecutive slashes, and regular directory names. Return the shortened path. If the path is absolute (starts with "/"), the result should also be absolute. If relative, the result should be relative and may start with ".." components.

Intuition

A stack is ideal for simulating directory navigation. Regular directory names are pushed onto the stack. A "." is ignored (stay in current directory). A ".." pops the last directory (go up one level). The key subtlety is handling relative paths: in a relative path, leading ".." tokens cannot be removed and must be preserved. In an absolute path, ".." at the root is simply ignored.

Approach

  1. Determine if the path is absolute (starts with "/").
  2. Split the path by "/" to get individual tokens.
  3. Filter out empty strings and "." tokens.
  4. Initialize an empty stack.
  5. For each token: a. If the token is "..":
    • If the path is absolute: pop from the stack if it is not empty (cannot go above root).
    • If the path is relative: pop from the stack only if the top is not ".." (and stack is not empty). Otherwise, push "..". b. Otherwise, push the token onto the stack.
  6. Join the stack elements with "/" and prepend "/" if the path is absolute.

Pseudocode

function shortenPath(path):
    isAbsolute = path[0] == '/'
    tokens = split path by '/'
    stack = []

    for token in tokens:
        if token == "" or token == ".":
            continue
        if token == "..":
            if isAbsolute:
                if stack is not empty:
                    stack.pop()
            else:
                if stack is not empty and stack.top() != "..":
                    stack.pop()
                else:
                    stack.push("..")
        else:
            stack.push(token)

    if isAbsolute:
        return "/" + join(stack, "/")
    else:
        return join(stack, "/")

Time & Space Complexity

  • Time: O(n) where n is the length of the path string. Splitting and iterating through tokens is linear.
  • Space: O(n) for the stack and the split tokens.

Key Insights

  • Absolute vs. relative paths require different handling of "..": absolute paths cap at root, relative paths may accumulate leading ".." components.
  • Empty tokens from consecutive slashes and "." tokens are simply discarded.
  • The stack naturally models directory traversal: push to enter a directory, pop to leave it.
  • The result for an absolute path always starts with "/", while a relative path never does (unless it is empty, in which case it could be ".").

Edge Cases

  • Root path "/": returns "/".
  • Path with only ".." components: for absolute, returns "/"; for relative, returns the ".." chain.
  • Path with trailing slashes: e.g., "/foo/bar/" simplifies to "/foo/bar".
  • Multiple consecutive slashes: "//foo///bar" simplifies to "/foo/bar".
  • Path like "../../foo": relative path that goes up two levels then into "foo".
  • Empty path or just ".": returns an empty string or the appropriate relative representation.

Linked mentions