71. Simplify Path - Solution & Explanation

Q: Is Simplify Path easy or hard?

Simplify Path is generally classified as a medium difficulty problem. The algorithm itself is straightforward, but many candidates struggle with edge cases such as consecutive slashes, '.' directories, and handling '..' when the stack is empty.

Q: Simplify Path Python/Java solution

In both Python and Java, the typical solution splits the path string by '/' and processes tokens using a stack or list. Python often uses a list as a stack, while Java commonly uses Stack or ArrayDeque. Both implementations achieve O(n) time and O(n) space complexity.

Q: How to solve Simplify Path in O(n)?

Split the path string using '/' and iterate through each segment once. Push valid directory names onto a stack, pop when encountering '..', and ignore '.' or empty segments. After processing all tokens, join the remaining stack elements with '/' to construct the canonical path.

Q: What is the best approach for Simplify Path?

The stack-based approach is considered the best solution. It processes each directory segment and uses push and pop operations to simulate moving into directories and returning to parent directories. This approach runs in O(n) time and O(n) space where n is the length of the path string.

Q: Is Simplify Path asked at Google/Amazon/Meta?

Simplify Path appears frequently in technical interviews at companies like Amazon, Google, and Meta because it tests string parsing, stack usage, and careful handling of edge cases such as repeated slashes and parent directory traversal.

Q: What data structure is used in Simplify Path?

A stack is the primary data structure used to track directory traversal. It allows efficient push operations when entering directories and pop operations when handling '..', which represents moving to the parent directory.

Q: What is the time complexity of Simplify Path?

The optimal solution runs in O(n) time because each character or path segment is processed once. Space complexity is O(n) in the worst case when all path segments are valid directories that must be stored before reconstructing the final canonical path.

The problem

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:

A single period '.' represents the current directory.
A double period '..' represents the previous/parent directory.
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:

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

Return the simplified canonical path.

Example 1:

Input: path = "/home/"

Output: "/home"

Explanation:

The trailing slash should be removed.

Example 2:

Input: path = "/home//foo/"

Output: "/home/foo"

Explanation:

Multiple consecutive slashes are replaced by a single one.

Example 3:

Input: path = "/home/user/Documents/../Pictures"

Output: "/home/user/Pictures"

Explanation:

A double period ".." refers to the directory up a level (the parent directory).

Example 4:

Input: path = "/../"

Output: "/"

Explanation:

Going one level up from the root directory is not possible.

Example 5:

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.

Approach overview

Problem Overview: You receive a Unix-style absolute file path such as /a/./b/../../c/. The task is to convert it into its canonical form by removing redundant slashes, resolving . (current directory), and correctly handling .. (parent directory).

The challenge is correctly interpreting directory traversal rules while preserving valid folder names. This is primarily a string parsing problem combined with a structure that tracks directory history.

Approach 1: Using Stack Data Structure (O(n) time, O(n) space)

The most common solution uses a stack to simulate directory navigation. Split the path by the '/' delimiter and process each token sequentially. When you encounter a normal directory name, push it onto the stack. If the token is .., pop from the stack if it's not empty because it means moving to the parent directory. Ignore . and empty tokens produced by consecutive slashes. After processing all components, rebuild the canonical path by joining stack elements with '/'. Each path segment is processed once, giving O(n) time complexity where n is the length of the path string, and the stack may store up to O(n) characters in the worst case.

This approach mirrors how operating systems internally resolve paths. The stack cleanly models forward navigation (push) and backward navigation (pop). Because of its clarity and reliability, this is the solution most engineers write during interviews.

Approach 2: Optimized String Handling (O(n) time, O(n) space)

You can solve the problem without explicitly using a stack structure by processing the string and storing valid directory segments in a dynamic list or array. Iterate through the path while extracting directory names between slashes. For each extracted token, apply the same rules: skip empty strings and ., remove the last stored directory if the token is .., otherwise append the directory to the result list. After processing the full path, concatenate the stored segments with '/' to build the canonical result.

The difference from the stack approach is mostly conceptual. Instead of stack operations, you treat the result container as a dynamic list and manipulate indices. Time complexity remains O(n) because each character is scanned once, and space complexity stays O(n) for storing path segments. This version can feel more natural in languages where array manipulation is lightweight.

Recommended for interviews: The stack-based solution is what most interviewers expect. It clearly communicates the filesystem navigation logic and maps directly to the semantics of .. and directory traversal. Demonstrating the stack approach shows solid understanding of both string parsing and stack-based state tracking, which is exactly what this problem tests.

Approach 1: Using Stack Data Structure

This approach utilizes a stack data structure to process the path components. By splitting the path on the '/' character, we collect the different components of the path. Using a stack helps efficiently manage directory movement due to '..'. For every directory name, it is pushed to the stack, for '..' we pop from the stack, and '.' is simply ignored. After processing all components, we join the names in the stack with '/' to form the simplified canonical path.

Python

def simplifyPath(path):
    stack = []
    components = path.split('/')

    for component in components:
        if component == '..':
            if stack:
                stack.pop()
        elif component != '' and component != '.':
            stack.append(component)

    return '/' + '/'.join(stack)

Java

import java.util.ArrayDeque;
import java.util.Deque;

public class SimplifyPath {
    public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<>();
        String[] components = path.split("/");

        for (String component : components) {
            if (component.equals("..")) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else if (!component.equals(".") && !component.isEmpty()) {
                stack.push(component);
            }
        }

        StringBuilder result = new StringBuilder();
        for (String dir : stack) {
            result.insert(0, "/" + dir);
        }
        return result.length() > 0 ? result.toString() : "/";
    }
}

C++

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

string simplifyPath(string path) {
    vector<string> stack;
    stringstream ss(path);
    string token;

    while (getline(ss, token, '/')) {
        if (token == "..") {
            if (!stack.empty()) {
                stack.pop_back();
            }
        } else if (token != "." && !token.empty()) {
            stack.push_back(token);
        }
    }

    string result;
    for (const string &dir : stack) {
        result += "/" + dir;
    }

    return result.empty() ? "/" : result;
}

JavaScript

function simplifyPath(path) {
  const stack = [];
  const components = path.split('/');

  for (const component of components) {
    if (component === '..') {
      if (stack.length > 0) {
        stack.pop();
      }
    } else if (component !== '.' && component !== '') {
      stack.push(component);
    }
  }

  return '/' + stack.join('/');
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *simplifyPath(char *path) {
    char **stack = (char **)malloc(3010 * sizeof(char *));
    int stackSize = 0;
    char delim[] = "/";
    char *token = strtok(path, delim);
    
    while (token != NULL) {
        if (strcmp(token, "..") == 0) {
            if (stackSize > 0) {
                stackSize--;
            }
        } else if (strcmp(token, ".") != 0 && strlen(token) != 0) {
            stack[stackSize++] = token;
        }
        token = strtok(NULL, delim);
    }
    
    if (stackSize == 0) {
        return "/";
    }
    
    char *result = (char *)malloc(3000 * sizeof(char));
    result[0] = '\0';
    for (int i = 0; i < stackSize; i++) {
        strcat(result, "/");
        strcat(result, stack[i]);
    }
    return result;
}

using System;
using System.Collections.Generic;

public class Solution {
    public string SimplifyPath(string path) {
        Stack<string> stack = new Stack<string>();
        string[] components = path.Split('/', StringSplitOptions.RemoveEmptyEntries);

        foreach (string component in components) {
            if (component == "..") {
                if (stack.Count > 0) {
                    stack.Pop();
                }
            } else if (component != ".") {
                stack.Push(component);
            }
        }

        List<string> result = new List<string>(stack);
        result.Reverse();
        return "/" + string.Join("/", result);
    }
}

The Python approach effectively uses a list as a stack. By splitting the path on '/', and processing each segment, we decide whether to append a directory to the stack, pop the stack, or simply skip certain segments like '.' (current directory) and empty strings. The list is joined with '/' to reconstruct the simplified path.

Complexity

Time Complexity: O(N), where N is the length of the path.
Space Complexity: O(N), since we're using a list that acts as a stack to store the directory components.

Try this approach in the editor

Approach 2: Optimized String Handling

This approach optimizes the simplification process using string handling techniques without explicitly using stack structures. It involves maintaining a result string directly, with an index pointer to simulate stack behavior. Iterating over path components allows addition, removal, or skipping of segments based on path rules, with a focus on reducing stack overhead. Finally, the result string is reconstructed as the simplified path.

Python

def simplifyPath(path):
    result = []
    components = path.split('/')

    for component in components:
        if component == '..':
            if result:
                result.pop()
        elif component and component != '.':
            result.append(component)

    return '/' + '/'.join(result)

Java

public class SimplifyPath {
    public String simplifyPath(String path) {
        StringBuilder result = new StringBuilder();
        String[] components = path.split("/");

        for (String component : components) {
            if (component.equals("..")) {
                int lastSlash = result.lastIndexOf("/");
                if (lastSlash >= 0) result.delete(lastSlash, result.length());
            } else if (!component.equals(".") && !component.isEmpty()) {
                result.append("/").append(component);
            }
        }

        return result.length() > 0 ? result.toString() : "/";
    }
}

C++

#include <string>
using namespace std;

string simplifyPath(string path) {
    string result;
    string temp;
    int length = path.length();
    for (int i = 0; i < length; ++i) {
        if (path[i] == '/') continue;
        int j = i;
        while (j < length && path[j] != '/') ++j;
        temp = path.substr(i, j - i);
        if (temp == "..") {
            if (!result.empty()) result.erase(result.find_last_of('/'));
        } else if (temp != ".") {
            result += '/' + temp;
        }
        i = j - 1;
    }
    return result.empty() ? "/" : result;
}

JavaScript

function simplifyPath(path) {
  let result = [];
  const components = path.split('/').filter(component => component !== '.' && component !== '');

  components.forEach(component => {
    if (component === '..') {
      result.pop();
    } else {
      result.push(component);
    }
  });

  return '/' + result.join('/');
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *simplifyPath(char *path) {
    char result[3010] = {0};
    char temp[3010];
    int len = strlen(path);
    int index = 0;
    
    for (int i = 0; i < len; i++) {
        if (path[i] == '/') continue;
        int j = i;
        while (j < len && path[j] != '/') j++;
        strncpy(temp, path + i, j - i);
        temp[j - i] = '\0';

        if (strcmp(temp, "..") == 0) {
            if (index > 0) {
                while (index > 0 && result[index - 1] != '/') index--;
            }
        } else if (strcmp(temp, ".") != 0) {
            result[index++] = '/';
            strcpy(result + index, temp);
            index += strlen(temp);
        }
        i = j - 1;
    }

    if (index == 0) return "/";
    result[index] = '\0';
    return strdup(result);
}

using System.Text;

public class Solution {
    public string SimplifyPath(string path) {
        StringBuilder result = new StringBuilder();
        string[] components = path.Split(new char[] {'/'}, StringSplitOptions.RemoveEmptyEntries);

        foreach (string component in components) {
            if (component == "..") {
                if (result.Length > 0) {
                    int lastSlashIndex = result.ToString().LastIndexOf('/');
                    result.Remove(lastSlashIndex, result.Length - lastSlashIndex);
                }
            } else if (component != ".") {
                result.Append("/").Append(component);
            }
        }
        return result.Length > 0 ? result.ToString() : "/";
    }
}

The Python method uses a list directly for path components, processing path similarly to the stack approach but more within a string context for simplicity. It maximizes single traversal efficiency to shape canonical path with string methods.

Complexity

Time Complexity: O(N), encompassing entire path processing.
Space Complexity: O(N), constrained to one resultant string list.

Try this approach in the editor

Approach 3: Stack

We first split the path into a number of substrings split by '/'. Then, we traverse each substring and perform the following operations based on the content of the substring:

If the substring is empty or '.', no operation is performed because '.' represents the current directory.
If the substring is '..', the top element of the stack is popped, because '..' represents the parent directory.
If the substring is other strings, the substring is pushed into the stack, because the substring represents the subdirectory of the current directory.

Finally, we concatenate all the elements in the stack from the bottom to the top of the stack to form a string, which is the simplified canonical path.

The time complexity is O(n) and the space complexity is O(n), where n is the length of the path.

TypeScript

function simplifyPath(path: string): string {
    const stk: string[] = [];
    for (const s of path.split('/')) {
        if (s === '' || s === '.') {
            continue;
        }
        if (s === '..') {
            if (stk.length) {
                stk.pop();
            }
        } else {
            stk.push(s);
        }
    }
    return '/' + stk.join('/');
}

func simplifyPath(path string) string {
	var stk []string
	for _, s := range strings.Split(path, "/") {
		if s == "" || s == "." {
			continue
		}
		if s == ".." {
			if len(stk) > 0 {
				stk = stk[0 : len(stk)-1]
			}
		} else {
			stk = append(stk, s)
		}
	}
	return "/" + strings.Join(stk, "/")
}

Rust

impl Solution {
    pub fn simplify_path(path: String) -> String {
        let mut stk = Vec::new();
        for s in path.split('/') {
            match s {
                "" | "." => continue,
                ".." => {
                    stk.pop();
                }
                _ => stk.push(s),
            }
        }
        "/".to_string() + &stk.join("/")
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using Stack Data Structure	Time Complexity: O(N), where N is the length of the path. Space Complexity: O(N), since we're using a list that acts as a stack to store the directory components.
Optimized String Handling	Time Complexity: O(N), encompassing entire path processing. Space Complexity: O(N), constrained to one resultant string list.
Stack	–

Complexity analysis

Approach	Time	Space	When to Use
Stack Data Structure	O(n)	O(n)	Best general solution; clearly models directory traversal and is preferred in interviews
Optimized String Handling	O(n)	O(n)	Useful when implementing directly with arrays or lists without explicit stack structures

Frequently asked questions

Is Simplify Path easy or hard?

Simplify Path is generally classified as a medium difficulty problem. The algorithm itself is straightforward, but many candidates struggle with edge cases such as consecutive slashes, '.' directories, and handling '..' when the stack is empty.

Simplify Path Python/Java solution

In both Python and Java, the typical solution splits the path string by '/' and processes tokens using a stack or list. Python often uses a list as a stack, while Java commonly uses Stack or ArrayDeque. Both implementations achieve O(n) time and O(n) space complexity.

How to solve Simplify Path in O(n)?

Split the path string using '/' and iterate through each segment once. Push valid directory names onto a stack, pop when encountering '..', and ignore '.' or empty segments. After processing all tokens, join the remaining stack elements with '/' to construct the canonical path.

What is the best approach for Simplify Path?

The stack-based approach is considered the best solution. It processes each directory segment and uses push and pop operations to simulate moving into directories and returning to parent directories. This approach runs in O(n) time and O(n) space where n is the length of the path string.

Is Simplify Path asked at Google/Amazon/Meta?

Simplify Path appears frequently in technical interviews at companies like Amazon, Google, and Meta because it tests string parsing, stack usage, and careful handling of edge cases such as repeated slashes and parent directory traversal.

What data structure is used in Simplify Path?

A stack is the primary data structure used to track directory traversal. It allows efficient push operations when entering directories and pop operations when handling '..', which represents moving to the parent directory.

What is the time complexity of Simplify Path?

The optimal solution runs in O(n) time because each character or path segment is processed once. Space complexity is O(n) in the worst case when all path segments are valid directories that must be stored before reconstructing the final canonical path.

Simplify Path solution and explanation

The problem

Approach overview

Approach 1: Using Stack Data Structure

Approach 2: Optimized String Handling

Approach 3: Stack

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Simplify Path solution and explanation

The problem

Approach overview

Approach 1: Using Stack Data Structure

Approach 2: Optimized String Handling

Approach 3: Stack

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems