71. Simplify Path - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

The Simplify Path problem asks us to convert an absolute Unix-style file path into its simplified canonical form. We are given a string path that represents an absolute path (it always begins with '/', indicating the root directory). Our task is to simplify this path by resolving special directory references and removing unnecessary parts.

In a Unix-style file system, the following special rules apply:

A single dot (".") refers to the current directory and thus can be ignored (it doesn’t change the path).
A double dot ("..") refers to the parent directory, meaning we should move one level up (remove the last directory from the path). If we are already at the root (no parent), ".." has no effect (it’s like staying at /).
Multiple consecutive slashes ("//") are treated as a single slash (i.e., they represent the same directory separator and don’t imply empty directories).
Any other names (including names with periods like "..." or "..a") are treated as normal directory names (they do not carry special meaning other than their literal name).

The simplified canonical path must meet these conditions :

It starts with a single slash / (root).
No segment is empty – directories in the path are separated by a single slash, and there are no extra slashes.
It does not end with a trailing slash (unless the path is just the root /).
It only contains the necessary directory names – no . or .. should remain in the final output.

Constraints:

1 <= path.length <= 3000
path consists of English letters, digits, underscores ('_'), slashes ('/'), or periods ('.').
path is a valid absolute Unix path (meaning it starts with '/' and only contains valid path symbols as above).

Example Inputs and Outputs:

Example 1:
Input: path = "/home/"
Output: "/home"
Explanation: The trailing slash is removed in the simplified path.
Example 2:
Input: path = "/../"
Output: "/"
Explanation: "../" means go up one directory from root. Since we’re at root, this has no effect, and the result remains the root directory /.
Example 3:
Input: path = "/home//foo/"
Output: "/home/foo"
Explanation: The double slash // is collapsed to a single /, so the path is equivalent to /home/foo.
Example 4:
Input: path = "/a/./b/../../c/"
Output: "/c"
Explanation: The sequence of operations simplifies to /c.
- /a adds "a" to the path.
- /./ stays in the same directory (ignore ".").
- /b adds "b" to the path (current path is /a/b).
- /../ moves one level up (removes "b", path becomes /a).
- /../ again moves one level up (removes "a", path becomes /).
- /c adds "c" to the path. The final simplified path is /c.

These examples illustrate how to handle trailing slashes, multiple slashes, "." (current directory), and ".." (parent directory) operations.

Hints

Use Delimiters: The path components are separated by the slash ('/') character. Splitting the input string by '/' is a helpful first step to isolate each part (directory names or special symbols). Consider how consecutive slashes or trailing slashes affect the split (you may get empty strings which you can ignore).
Stack Analogy: The problem naturally lends itself to a stack structure . As you traverse the path from left to right, treat each directory name as something to “push” onto a stack. When you encounter "..", it means you need to pop (go up to the parent directory). This LIFO behavior (last in, first out) matches how nested paths work (the last added directory is the first to be removed when going up).
Skip Current Directory: Whenever you see "." or an empty component (which can occur due to //), it means “stay in the same directory,” so you can safely skip those. They don't affect the path.
Boundary Conditions: Think about what happens at the root. If the stack is empty (you’re at root) and you see "..", you should simply ignore it (you can’t go above root). Make sure your solution accounts for this so it doesn’t try to pop from an empty stack.
Manual Parsing (Alternative): If you want to avoid using extra space for splitting the string, you can parse the path manually. Iterate through the characters of the path with pointers or indices to extract directory names. This approach eliminates the overhead of creating an array of components. It’s a bit more involved, but it follows the same logic of pushing and popping directory names when you see normal names or "..".

Try to reason through the problem using these hints before looking at the solutions. Consider walking through a sample path by hand, applying each rule step by step.

Multiple Approaches with Code

We will discuss two approaches to solve this problem:

A Stack-Based Approach (optimal and most straightforward using a stack or list to simulate a stack).
A Naive Iterative Approach (parsing the path manually without explicitly using a stack data structure).

For each approach, we provide a detailed explanation, followed by implementations in Python and Java. Both implementations include a main method to demonstrate the solution with example inputs.

Stack-Based Approach (Optimal Solution using a Stack)

Explanation:
This approach uses a stack to build the simplified path. The idea is to push directory names onto the stack and pop them when ".." is encountered. Here’s how it works step by step:

Split the Path: First, split the input string by '/'. This gives us a list of path components (strings). For example, "/home//foo/" would split into ["", "home", "", "foo", ""]. Each element can be:
- An empty string ("") if there were consecutive slashes or a slash at the start/end.
- A single dot (".") indicating the current directory.
- A double dot ("..") indicating moving up to the parent directory.
- A normal directory name (e.g., "home", "foo", etc.).
Initialize an empty stack (list): We will use a list as a stack to store directory names.
Process each component: Iterate through the list of components obtained from the split:
- If the component is "" (empty) or ".", do nothing (skip it) – it has no effect on the path.
- If the component is "..", pop the last directory from the stack (if the stack is not empty). This represents moving up one level. If the stack is empty, it means we're at root and there's nothing to pop, so we ignore "..".
- Otherwise (the component is a normal directory name), push the component onto the stack. This means we go into that directory.
Construct the result: After processing all components, the stack will contain the directory names that are in the simplified path (from root to target). Join these with "/" in between, and prepend a leading slash "/" at the beginning to form the canonical path.
- If the stack is empty, the result should be just "/" (root). Otherwise, join the stack contents with "/" and prefix with /.
- Note that joining with "/" automatically ensures no trailing slash at the end (since we only put separators between directory names). The rules of canonical path (no trailing slash, single slashes between directories) are satisfied by this construction.

Using this method, each path component is processed in constant time relative to its length, and each component is pushed or popped at most once. This makes the solution efficient.

Let’s walk through a quick example to solidify the approach:
Suppose path = "/a/./b/../c/".

Splitting by '/' gives components: ["", "a", ".", "b", "..", "c", ""].
Start with an empty stack.
- "" (first component, empty due to leading slash) → skip.
- "a" → push "a" (stack now ["a"]).
- "." → skip (current directory, no change, stack still ["a"]).
- "b" → push "b" (stack now ["a", "b"]).
- ".." → pop last directory (pop "b", stack back to ["a"]).
- "c" → push "c" (stack now ["a", "c"]).
- "" (last component, empty due to trailing slash) → skip.
Stack contains ["a", "c"]. Join with / and add leading slash → "/a/c". This matches the simplified path. (If we started from root, went into a, then c, skipping the b because of the "..", the final path is /a/c.)

Python Implementation (Stack-Based Approach):

Python3

. . . .

Java Implementation (Stack-Based Approach):

Java

. . . .

Explanation of the Code: In both Python and Java versions, we split the input path by "\" and iterate through each component. We maintain a list (stack) where we push directory names and pop them for "..". Finally, we construct the simplified path from the remaining directories in the stack. The main method (or the if __name__ == "__main__": block in Python) demonstrates the function with a few test paths, including the examples given. The output confirms that the logic produces the expected simplified paths.

Naive Approach (Iteratively Handling Components without an Explicit Stack)

Explanation:
This approach achieves the same end result without explicitly using a stack data structure. We will manually parse the path string and handle each part as we encounter it. The idea is to iterate through the path character by character to extract directory names and apply the rules on the fly. Essentially, we simulate the stack operations using variables and string manipulation. This approach avoids using split(), which may save some overhead, and shows how you could handle the path in one pass using two pointers (or indices). The trade-off is a bit more complex logic compared to the straightforward split method.

How it works:

Initialize an empty list result_dirs to accumulate valid directory names (this will serve the role of the stack to hold path components). Also, initialize an index i to 0 to traverse the string.
Iterate through the string using i (the current position). We'll use a second index j to find the end of the current directory name:
- First, skip over any '/' characters at the current position (to handle multiple slashes). Move i forward while path[i] is '/'. After this, either i reaches the end of the string or path[i] is the start of a directory name (or special token).
- If we've reached the end of the string after skipping slashes, break out of the loop (we're done).
- Otherwise, set j = i and advance j until we either reach the end of the string or encounter a '/'. Now, path[i:j] is one complete component (between slashes).
- Extract this substring as part = path[i:j]. This is the next directory name or "." or ".." token.
- Apply the rules to part:
  - If part is "" (empty) or ".", do nothing (skip it).
  - If part is "..", remove the last directory from result_dirs (if it’s not empty). If result_dirs is empty, ignore ".." (trying to go up from root does nothing).
  - Otherwise, part is a normal directory name, so append it to result_dirs.
- Set i = j to continue scanning from the end of this component (which is at a slash or end of string). This prepares for the next iteration to handle the next component.
After the loop, construct the simplified path string: if result_dirs is empty, return "/" (root). Otherwise, join all entries in result_dirs with "/" and prepend a "/" at the beginning. This yields the canonical path.

This approach effectively does the same push/pop operations as the stack method, but it parses the input in one pass without using the built-in split function or a formal stack. The list result_dirs acts like the stack by using append and pop operations for directory names. The logic ensures that we correctly handle multiple slashes and boundaries.

Python Implementation (Naive Iterative Approach):

Python3

. . . .

Java Implementation (Naive Iterative Approach):

Java

. . . .

Explanation of the Code: The Python and Java implementations above manually parse the path string. We use two indices (i and j) to find each directory name between slashes. For each component found, we apply the logic: ignore "" and ".", pop for "..", and append for normal names. The final path is constructed by joining the collected directory names. The provided main methods run the function on some test inputs (the same examples as before) to verify that the output is correct. This approach produces the same results as the stack-based method.

Complexity Analysis

Time Complexity: Both approaches run in linear time, i.e. O(n), where n is the length of the input path string. We process each character of the input at most once.
- In the Stack-Based Approach, splitting the string by '/' is O(n), and then iterating through components is another O(n) in the worst case, so overall O(n).
- In the Iterative Approach, we traverse the string with index pointers in a single pass, which is also O(n). There is no nested loop that depends on n (the inner loops move the index j forward without resetting i backwards, so each character is still processed once).
Space Complexity: Both approaches use O(n) extra space in the worst case.
- The stack approach allocates an array of components from the split (which in worst case could be on the order of n components if the path is like /a/b/c/...) and a stack list to hold the directory names (also at most n components in worst case, e.g., path has no ".." or "."). The output string itself also takes up to O(n) space.
- The iterative approach avoids the extra array from splitting, but it still uses a list result_dirs to collect components (worst case O(n) components) and builds the output string of length O(n).
In summary, both solutions are efficient, running in linear time and using linear space. The iterative approach saves the overhead of creating the split array, but this is a constant factor improvement; both are optimal in terms of Big-O complexity for this problem.

Common Mistakes

When solving this problem, users often run into a few pitfalls:

Not handling multiple slashes correctly: Forgetting to skip empty components resulting from consecutive slashes can lead to incorrect results. For example, if you don’t handle "" from "//", you might end up pushing empty strings to the stack or adding extra slashes in the result. Always ignore "" components that arise from splitting or parsing.
Ignoring boundary conditions for "..": A frequent mistake is to blindly pop on ".." without checking if there is something to pop. If the path tries to go above the root (e.g., the input is "/../"), you should not pop from an empty stack (this would represent going beyond the root directory). Ensure that you only pop when the stack is non-empty.
Including "." in the result: The "." components should be discarded entirely. If you mistakenly include them in the output or treat them as directory names, the result will be wrong. Make sure to skip ".".
Leaving a trailing slash: After constructing the result path, be careful not to add an extra slash at the end. The problem specifically requires no trailing slash in the canonical path. Construct the output by joining with "/" appropriately, or handle the string so that you don't end with an extra /. (Our approaches naturally avoid this by only adding separators between directories, and starting with a single / at the beginning.)
Misinterpreting special names: Remember that only "." and ".." have special meanings. A name like "..." or "..something" is not special and should be treated as a regular directory name. A mistake here could be to treat any occurrence of two dots as going up, which would be wrong. Only exactly ".." should trigger a pop.

By being mindful of these issues, you can avoid the common errors. Testing your solution on edge cases (like paths that are at root, or have lots of ".." or "//") will help catch these mistakes.

Edge Cases

Consider the following edge cases to ensure your solution handles them correctly:

Root Only: Input path is just "/". The simplified path should obviously be "/". Make sure your code doesn’t accidentally drop the root or produce an empty string.
Trailing Slashes: Paths like "/abc/" or "/abc/def///" should simplify to "/abc" and "/abc/def" respectively, with no trailing slash. The algorithm should naturally handle this by ignoring empty segments at the end.
Multiple Consecutive Slashes: Input containing sequences like "//" or "///" (e.g. "/home//foo/bar///baz"). These should be treated as single separators. The output should compress multiple slashes into one (e.g. "/home/foo/bar/baz"). Ensure that your splitting or parsing logic skips over empty segments.
Parent References at Root: Paths that try to go up from root, such as "/../" or "/../../folder". No matter how many ".." are at the beginning, the result cannot go above root – it should remain at "/" or just go into "/folder" in the second example ("/../../folder" should simplify to "/folder"). Check that popping from an empty stack is handled safely by ignoring ".." in that scenario .
Complex Relative Movements: A path that has a mix of current and parent directory references, like "/a/./b/./../c/" or "/a//b/../..//c/.". These should simplify correctly (both examples simplify to "/c"). It’s good to test such combinations to be confident in the logic.
Names with Dots: Directory names that contain dots but are not solely "." or "..", e.g. "/.../test/.." or "/.hidden/../visible":
- "/.../test/.." should simplify to "/..." (the "..." is a valid directory name, and then going up one removes "test" leaving "...").
- "/.hidden/../visible" should simplify to "/visible" (".hidden" is a directory name starting with a dot, not the same as ".").
  Ensure that your code distinguishes these correctly.

By carefully checking these cases, you can verify that your solution works for all scenarios a Unix path might include.

Alternative Variations

This problem is about simplifying an absolute path. Variations of this problem could involve different settings or additional requirements:

Relative Paths: You might encounter a variation where the path is not guaranteed to start at root. For example, given a current working directory and another path (which could be relative or absolute), determine the resulting path. This is analogous to how the shell command cd (change directory) works. You would need to handle cases where the input path might not start with /, meaning you start from the current directory and then simplify. The solution approach would be similar – you could initialize your stack with the current directory’s components and then process the new path.
Windows-style Paths: Another variation could be simplifying Windows file system paths, which use a different format (e.g., "C:\\Users\\Documents\\..\\File.txt" or using "\\" as a separator). The core idea remains the same (handling ".." and "."), but the separators and root representation differ (drive letters like C: instead of a single / root). The solution would adapt the parsing to account for backslashes and perhaps drive letters.
Path Normalization in Libraries: In real-world scenarios, languages have library functions to normalize paths (e.g., Python’s os.path.normpath or Java’s Path.normalize() in NIO). A variation of the question might be to implement such a function from scratch, which is essentially what we do in the Simplify Path problem.
Simplify URL Paths: A related idea is simplifying URL paths or web routes which might contain segments like . or .. (though not common in URLs except maybe in relative URL resolution). The logic would be very similar, treating "/" as separators and .. as navigation up one level.
Extended Operations: Some file systems have other notations (for example, ~ for home directory in Unix shells, or environment variables in paths). A more complex variation could ask you to expand those as well. This goes beyond the LeetCode problem, but the concept of parsing and handling tokens remains relevant.

In interviews, a common follow-up to this problem is indeed the relative path resolution (like implementing cd behavior). If you feel comfortable with Simplify Path, that variation would be a good next step to try on your own: start with a base path and an input path that could be relative, and produce the normalized absolute path.

Working on similar problems can reinforce the concepts used in solving Simplify Path. Here are a few related problems and scenarios:

1598. Crawler Log Folder (LeetCode) – Easy: This is a simplified version of the path navigation problem. You are given a list of operations (like "../" for parent, "./" for current directory, or folder names) and you need to find the current folder depth. It basically uses the same logic (increment depth for a name, decrement for "..", ignore "."), which is conceptually a stack operation. It’s a good warm-up for Simplify Path.
388. Longest Absolute File Path (LeetCode) – Medium: In this problem, you are given a string representation of a file system (with newline '\n' and tab '\t' characters indicating hierarchy) and need to find the length of the longest file path. It requires using a stack to keep track of directory depths while parsing the string. This problem also reinforces using stacks for managing path-like structures and is a bit different angle on file paths.
71. Simplify Path (LeetCode) – The problem we just discussed is itself a classic. If you haven’t actually coded it yet (and just read this explanation), try writing it from scratch without looking at the solution to solidify your understanding.
Canonical Path (Various platforms) – Some coding challenges or interview questions are essentially the same task of normalizing a file path. Practice with different examples or even implement the solution in another programming language to deepen your familiarity.
Stack-based string problems: Other problems like “Decode String” (LeetCode 394) or “Remove K Digits” (LeetCode 402) use stacks to build or simplify strings based on certain rules. While not about file paths, they will give you practice in using stack operations to process sequences of characters or tokens, which is a transferable skill from this problem.

71. Simplify Path - Detailed Explanation

Problem Statement

Hints

Multiple Approaches with Code

Stack-Based Approach (Optimal Solution using a Stack)

Naive Approach (Iteratively Handling Components without an Explicit Stack)

Complexity Analysis

Common Mistakes

Edge Cases

Alternative Variations

Related Problems for Further Practice