Knowledge Guide
Home › DSA › Stack

medium 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

Example 2

Example 3

Constraints:

Try it yourself

Try solving this question here:

✅ Solution 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.

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

  1. Split the input path by the "/" character into an array of components.

  2. Initialize an empty stack.

  3. 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.

  4. 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

Image
Image

  1. Initialize a Stack: A Stack<String> is created to store components of the simplified path.

  2. 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.

  3. 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"].

  4. 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".

  5. 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: .

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

Stuck on 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 **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 **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 **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 **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

← Evaluate Reverse Polish NotationDaily Temperatures →