medium Problem 6 Simplify Path

Problem Statement

Given an absolute file path in a Unix-style file system, simplify it by converting ".." to the previous directory and removing any "." or multiple slashes. The resulting string should represent the shortest absolute path.

Examples

Example 1

Input: path = "/a//b////c/d//././/.."
Expected Output: "/a/b/c"
Explanation:
- Convert multiple slashes (//) into single slashes (/).
- "." refers to the current directory and is ignored.
- ".." moves up one directory, so "d" is removed.
- The simplified path is "/a/b/c".

Example 2

Input: path = "/../"
Expected Output: "/"
Explanation:
- ".." moves up one directory, but we are already at the root ("/"), so nothing happens.
- The final simplified path remains "/".

Example 3

Input: path = "/home//foo/"
Expected Output: "/home/foo"
Explanation:
- Convert multiple slashes (//) into single slashes (/).
- The final simplified path is "/home/foo".

Constraints:

1 <= path.length <= 3000
path consists of English letters, digits, period '.', slash '/' or '_'.
path is a valid absolute Unix path.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Simplify Path (problem)

1. Why / judgment

Unix path simplification is stack parsing of segments: directories push, .. pops (not below root), ./empty ignored.

2. Worked complexity / trace (K11)

"/a//b////c/d//././/.." → /a/b/c; "/../" → /; "/home//foo/" → /home/foo. Θ(n) scan.

3. Pattern + when-NOT (K12)

Name: SEGMENT STACK PATH

Recognition: absolute path; . .. // tokens.

When-NOT: Not regex-only. Not queue. Not NGE mono stack. Relative paths need cwd seed.

4. Edge hand-run (K13)

"/../" never above root. "/a/./b/../../c/" → /c. trailing slash dropped.

5. Interviewer follow-ups

Q1. Why stack?
A: Parent directory is most recent segment — LIFO.

Q2. Empty stack after pops?
A: Emit "/" root.

Q3. Complexity?
A: O(n) split+scan; O(n) stack space.

✅ Solution Simplify Path

Problem Statement

Examples

Example 1

Input: path = "/a//b////c/d//././/.."
Expected Output: "/a/b/c"
Explanation:
- Convert multiple slashes (//) into single slashes (/).
- "." refers to the current directory and is ignored.
- ".." moves up one directory, so "d" is removed.
- The simplified path is "/a/b/c".

Example 2

Input: path = "/../"
Expected Output: "/"
Explanation:
- ".." moves up one directory, but we are already at the root ("/"), so nothing happens.
- The final simplified path remains "/".

Example 3

Input: path = "/home//foo/"
Expected Output: "/home/foo"
Explanation:
- Convert multiple slashes (//) into single slashes (/).
- The final simplified path is "/home/foo".

Constraints:

1 <= path.length <= 3000
path consists of English letters, digits, period '.', slash '/' or '_'.
path is a valid absolute Unix path.

Solution

To simplify the path, we'll use a stack to track the directories we're currently in. We'll split the input path into components by the "/" character, then process each component one by one. If a component is "..", we go to the previous directory by popping the top of the stack. If a component is "." or an empty string, we do nothing. Otherwise, we push the component into the stack as a new directory.

Step-by-Step Algorithm

Split the input path by the "/" character into an array of components.
Initialize an empty stack.
For each component in the array:
- If the component is "..", pop the top of the stack (if it's not already empty).
- Else if the component is "." or an empty string, do nothing.
- Else, push the component into the stack as a new directory.
Merge all elements in the stack into a string by reversing the order and joining them with the '/' character. Ensure the final path starts with '/' to represent an absolute path.

Algorithm walkthrough

Initialize a Stack: A Stack<String> is created to store components of the simplified path.
Split the Path: The input path "/a//b////c/d//././/.." is split using "/" as the delimiter. The resulting parts are: ["", "a", "", "b", "", "", "", "c", "d", "", ".", "", ".", "", "", ".."]. Empty strings and dots (".") represent the current directory and will be ignored in further processing.
Process Each Part:
- First Part (""): It's empty, so it's ignored.
- Second Part ("a"): It's a directory name and is pushed onto the stack.
- Third Part (""): Ignored.
- Fourth Part ("b"): Another directory name, pushed onto the stack.
- Next Several Parts ("", "", ""): All empty, so ignored.
- Part "c": A directory name, pushed onto the stack.
- Part "d": Another directory name, pushed onto the stack.
- Part ".": Represents the current directory, ignored.
- Part "." (again): Again, represents the current directory, ignored.
- Last Part (".."): Represents moving up one directory. It pops "d" from the stack.
After processing, the stack contains: ["a", "b", "c"].
Reconstruct Simplified Path: Next, create the resulting string by joining all stack elements with the '/' character in reverse order.
- After processing the stack, the string contains "/a/b/c".
Return the Result:
- For the given input, the output is "/a/b/c".

Code

Here is the code for this algorithm:

java

import java.util.*;

public class Solution {

  public String simplifyPath(String path) {
    // Create a stack to store the simplified path components
    Stack<String> stack = new Stack<>();

    // Split the input path string using '/' as a delimiter
    for (String p : path.split("/")) {
      if (p.equals("..")) {
        // If the component is '..', pop the last component from the stack
        if (!stack.isEmpty()) {
          stack.pop();
        }
      } else if (!p.isEmpty() && !p.equals(".")) {
        // If the component is not empty and not '.', push it onto the stack
        stack.push(p);
      }
    }

    // If the result is empty, return '/', otherwise return the simplified path
    return "/" + String.join("/", stack);
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    // Test cases
    System.out.println(sol.simplifyPath("/a//b////c/d//././/..")); // Expected output: "/a/b/c"
    System.out.println(sol.simplifyPath("/../")); // Expected output: "/"
    System.out.println(sol.simplifyPath("/home//foo/")); // Expected output: "/home/foo"
  }
}

Complexity Analysis

Time Complexity

Splitting the path: The input string path is split using / as the delimiter, which takes time, where N is the length of the input string path. This creates an array of strings representing the components of the path.
Processing the components: The algorithm processes each component of the path array. For each component, it either pushes it onto the stack, pops an element from the stack, or skips the component if it is . or empty. Since each component is processed at most once, this takes time in total.
Building the result: After processing all components, the algorithm reconstructs the simplified path by concatenating the elements in the stack. This also takes time.

Overall time complexity: , where N is the length of the input string path.

Space Complexity

Stack space: The stack stores the components of the simplified path. In the worst case, the stack contains all components of the path, which requires space.
Result string space: The result string is used to store the final result which also takes space, as it holds the result of the same size as the input string (in the worst case).

Overall space complexity: .

🎯 STRICT STANDOUT — Solution Simplify Path

1. Why / judgment

split on '/'; skip empty and '.'; pop on '..' if non-empty; push names; join with leading '/'.

2. Worked complexity / trace (K11)

"/a//b////c/d//././/.." → push a,b,c,d; .. pops d → [a,b,c] → "/a/b/c".
"/../" → pop noop → "/". Θ(n) time/space.

3. Pattern + when-NOT (K12)

Name: PATH SEGMENT STACK

Recognition: canonicalize absolute Unix path.

When-NOT: Windows/URL differ. Symlinks out of scope. Iterative stack preferred over recursion on segments.

4. Edge hand-run (K13)

only "/": empty stack → "/". "/a/b/.." → /a. multiple .. beyond root stay at root.

5. Interviewer follow-ups

Q1. Why guard pop on ..?
A: Root has no parent.

Q2. String.join on Stack order?
A: Java Stack iteration is bottom→top — correct for path join.

Q3. Security note?
A: Canonicalization necessary but not sufficient against all traversal attacks.

🧩 Pattern · Stack

Recognize it: Matching / nesting, or “next greater / smaller” → LIFO, or a monotonic stack.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Problem 6 Simplify Path? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Problem 6 Simplify Path** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Problem 6 Simplify Path** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Problem 6 Simplify Path**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Problem 6 Simplify Path**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Problem 3 Decimal to Binary Conver Problem 7 Remove All Adjacent Dupl →