Skip to main content

Stack

Simplify Path Solution In C++/Python/Java/JS

Simplify Path Problem Statement

You are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplified canonical path.

The rules of a Unix-style file system are as follows:

1. A single period '.' represents the current directory.
2. A double period '..' represents the previous/parent directory.
3. Multiple consecutive slashes such as '//' and '///' are treated as a single slash '/'.

Any sequence of periods that does not match the rules above should be treated as a valid directory or file name. For example, '...' and '....' are valid directory or file names.

The simplified canonical path should follow these rules:

1. The path must start with a single slash '/'.
2. Directories within the path must be separated by exactly one slash '/'.
3. The path must not end with a slash '/', unless it is the root directory.
4. The path must not have any single or double periods ('.' and '..') used to denote current or parent directories.

Return the simplified canonical path.
simplify-path-Problem Description
simplify-path-Examples

Example

Input: path = "/home/"
Output: "/home"
Explanation: The trailing slash should be removed.

Input: path = "/home//foo/"
Output: "/home/foo"
Explanation: Multiple consecutive slashes are replaced by a single one.

Input: path = "/home/user/Documents/../Pictures"
Output: "/home/user/Pictures"
Explanation: A double period ".." refers to the directory up a level (the parent directory).

Input: path = "/../"
Output: "/"
Explanation: Going one level up from the root directory is not possible.

Input: path = "/.../a/../b/c/../d/./"
Output: "/.../b/d"
Explanation: "..." is a valid name for a directory in this problem.

Constraints

  • 1 <= path.length <= 3000
  • path consists of English letters, digits, period '.', slash '/' or '_'.
  • path is a valid absolute Unix path.
💡
Try Solving "Simplify Path" Yourself First !!
The Simplify Path solution requires visualization of the flow of output rather than just Brute Force method.
We must first note down the rules and take examples and see how following those rules help us get the right output. Let's see how we can figure out the working algorithm !!

How to Solve Simplify Path ?

Intuition

Let's first note down the rules briefly.

1. '.' → current directory
2. '..' → Previous directory
3. '// /' → Multiple slashes as single slash.
4. 'multiple dots (....)' → Directory/file name

Let's take an example and understand how the "Simplify Path Algorithm" works.
suppose string s = "/learn/yard///simplify/./../.../../path".
In s, "learn","yard","simplify","...","path" are all directory names.

This means the '/'s used in the string is to just separate the directories. Let's remove the '/'s present since it's not going to impact the answer.

For the first three words, the directory looks like

When we come across the '.', this clearly tells to remain in the same directory.

Next when we come across the '..' this tells us to jump to the previous directory, so we need to move from "simplify" directory to "yard" directory.

But next comes '...' which will be treated as a directory, do the '...' directory comes inside "yard" directory.

Next, when we encounter a '..', again we will be going to the previous directory.

Next comes the "path" directory so, it will be included inside the "yard" directory.

So, the final answer for "Simplify Path" looks like

We understood how the algorithm will work, now let's see how to proceed programmatically.

So, we observed that every time we encountered a word, it was a directory so we put it into the record, whenever we encountered '..' we removed the most recent directory.
Most recent was removed ?? Does it gives the intuition of using a Stack data structure.

Yes, it's a stack.
So, we will be pushing the directory names onto the stack. When we encounter a "..", we pop out the top of stack.

Simplify Path Algorithm

We will first spit the string from the '/'s
We will use a stack, if we encounter any string other than "/",".","..", we will push it to the top of stack.
If we encounter "..", we will pop out from the stack.
Then , we will just pop the strings one by one from the stack and append it with a "/" and return the resultant string.

Let's see how we can code it up!!

Approach

Step 1: Split the Path: Split the given path string by '/' to obtain individual components.
Store them in an array called components.

Initialize a Stack: Create an empty stack st to store valid directory names.

Process Each Component:
Iterate through components:

  • Ignore empty strings and "." since they don’t affect the path.
  • If ".." appears and the stack is not empty, pop the top element (move up one directory).
  • Otherwise, push valid directory names onto the stack.

Build the Simplified Path:

  • Use a StringBuilder to construct the result.
  • Pop each element from the stack and prepend it with '/'.

Return the Result: If the stack is empty, return "/". Otherwise, return the constructed path string.

Let us understand this with the help of a video.

0:00
/1:30

simplify-path-Optimal-Animation

Dry-Run

s = "/a/b///c/./../.../.././d/../e"
Output:- "/a/b/e"

  1. Splitting the Path
    Using path.split("/"), we get the components:
    ["", "a", "b", "", "", "c", ".", "..", "...", "..", ".", "d", "..", "e"]
  2. Processing Each Component using Stack
    The stack (st) starts empty.
    • "" → Ignore (empty)
    • "a" → Push "a" → st = ["a"]
    • "b" → Push "b" → st = ["a", "b"]
    • "" → Ignore (empty)
    • "" → Ignore (empty)
    • "c" → Push "c" → st = ["a", "b", "c"]
    • "." → Ignore (current directory)
    • ".." → Pop "c" → st = ["a", "b"]
    • "..." → Push "..." (valid directory name) → st = ["a", "b", "..."]
    • ".." → Pop "..." → st = ["a", "b"]
    • "." → Ignore (current directory)
    • "d" → Push "d" → st = ["a", "b", "d"]
    • ".." → Pop "d" → st = ["a", "b"]
    • "e" → Push "e" → st = ["a", "b", "e"]
  4. Building the Result
    The stack contains: ["a", "b", "e"]
    Construct the path from the stack: "/a/b/e"

Final Output: "/a/b/e"

Simplify Path solution

Let's now see the Simplify Path solution in Java, C++, Python and JavaScript.

Simplify Path Code in all Languages.
1. Simplify Path Solution Code in C++ Try on Compiler 
// C++ Implementation
#include <iostream>
#include <stack>
#include <sstream>
using namespace std;

string simplifyPath(string path) {
    // Use a stack to store valid directory names
    stack<string> st;
    stringstream ss(path);
    string token;
    
    // Split path by '/'
    while (getline(ss, token, '/')) {
        if (token == "" || token == ".") {
            continue;
        }
        if (token == "..") {
            if (!st.empty()) {
                st.pop();
            }
        } else {
            st.push(token);
        }
    }
    
    // Build the simplified path
    string res = "";
    while (!st.empty()) {
        res = "/" + st.top() + res;
        st.pop();
    }
    return res.empty() ? "/" : res;
}

int main() {
    string path;
    cout << "Enter the path: ";
    cin >> path;
    cout << "Simplified Path: " << simplifyPath(path) << endl;
    return 0;
}

2. Simplify Path Solution Code in Java Try on Compiler 
import java.util.*;

class Solution {
    
    public String simplifyPath(String path) {
        // Split the path by '/' to get individual components
        String[] components = path.split("/");
        
        // Stack to store valid directory names
        Stack<String> st = new Stack<>();

        // Iterate through each component in the path
        for (String comp : components) {
            // Ignore empty components and '.' which refers to the current directory
            if (comp.equals("") || comp.equals(".")) {
                continue;
            }

            // If the component is '..', pop from the stack if it's not empty (going back a directory)
            if (comp.equals("..")) {
                if (!st.isEmpty()) {
                    st.pop();
                }
            } else {
                // Push valid directory names onto the stack
                st.push(comp);
            }
        }

        // Build the simplified path from stack contents
        StringBuilder sb = new StringBuilder();
        while (!st.isEmpty()) {
            sb.insert(0, "/" + st.pop());
        }

        // Return '/' if the stack is empty (root directory), otherwise return the built path
        return sb.length() == 0 ? "/" : sb.toString();        
    }

    public static void main(String[] args) {
        // Scanner to take user input
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter the path:");
        String path = scanner.nextLine();
        
        // Create instance of Solution and simplify the given path
        Solution solution = new Solution();
        String simplifiedPath = solution.simplifyPath(path);
        
        // Print the simplified path
        System.out.println("Simplified Path: " + simplifiedPath);
        
        // Close the scanner
        scanner.close();
    }
}

3. Simplify Path Solution Code in Python Try on Compiler 
# Python Implementation
def simplify_path(path: str) -> str:
    # Use a stack to store valid directory names
    stack = []
    components = path.split('/')
    
    for comp in components:
        if comp == "" or comp == ".":
            continue
        if comp == "..":
            if stack:
                stack.pop()
        else:
            stack.append(comp)
    
    return "/" + "/".join(stack) if stack else "/"

if __name__ == "__main__":
    path = input("Enter the path: ")
    print("Simplified Path:", simplify_path(path))

4. Simplify Path Solution Code in JavaScript Try on Compiler 
// JavaScript Implementation
const fs = require('fs');

function simplifyPath(path) {
    let stack = [];
    let components = path.split('/');
    
    for (let comp of components) {
        if (comp === "" || comp === ".") {
            continue;
        }
        if (comp === "..") {
            if (stack.length) {
                stack.pop();
            }
        } else {
            stack.push(comp);
        }
    }
    
    return "/" + stack.join('/') || "/";
}

const path = fs.readFileSync(0, 'utf-8').trim();
console.log("Simplified Path:", simplifyPath(path));

Complexity Analysis of the problem

Let's now analyse the Time and Space Complexity for the algorithm we figured out !!

Time Complexity: O(n)

Splitting the Input Path (path.split("/") equivalent in all languages)
This takes O(N) time, where N is the length of the input string.

Iterating Through Components
We iterate over at most N components, performing constant-time operations (push, pop, or continue).
Each operation on the stack is O(1).
The worst case is that all N components are pushed onto the stack. Hence, the total iteration takes O(N) time.

Building the Final Path String
Constructing the output from the stack involves another O(N) operation.

Final Time Complexity The overall time complexity is O(N) + O(N) + O(N) = O(N).

Space Complexity: O(n)

Auxiliary Space Complexity
Auxiliary space refers to extra space used excluding input storage.
Stack Usage

    • In the worst case (e.g., "/a/b/c/d" with no ".." operations), all N components are pushed onto the stack.
    • The maximum size of the stack is O(N).

Output String Construction

    • The final string representation is also O(N) in the worst case.

Final Auxiliary Space Complexity

  • Since both the stack and output string require O(N) space in the worst case, the auxiliary space complexity is O(N).

Total Space Complexity Analysis
Total space complexity includes:

  • Input storage (already given).
  • Auxiliary space (stack and output string).
  • Input storage: The input string takes O(N) space.
  • Auxiliary space: As calculated earlier, the extra space required is O(N).

Final Total Space Complexity: O(N) + O(N) = O(N).

Real World Examples

Command Line Navigation (Shell)

Example Input: cd /home/user/../docs/./reports//2024/
Simplified Path: /home/docs/reports/2024
Use Case: When a user navigates through directories in a terminal, the shell internally simplifies the path before accessing files.

Web URL Routing

Example Input: https://example.com/api/v1/../user//profile/./info
Simplified Path: https://example.com/api/user/profile/info
Use Case: Web servers process URL paths efficiently by removing redundant parts.

Figuring out the Simplify Path solution will help us in building clear and faster intuitive approach for other math-based problem statements.

Similar Problems

  • Evaluate Reverse Polish Notation
  • Basic Calculator II
  • Different Ways to Add Parentheses
  • Expression Add Operators
  • Basic Calculator III
  • The Score of Students Solving Math Expression
  • Minimize Result by Adding Parentheses to Expression