Log inSign up
mediumLeetCodeNot Started

Simplify Path

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Stack
Solve on LeetCode
Lesson

Problem Statement

Given an absolute path for a Unix-style file system, which begins with a slash '/', transform this path into its canonical path.

In Unix-style file system context: * A single period '.' refers to the current directory. * A double period '..' refers to the directory up a level. * Multiple consecutive slashes such as '//' are treated as a single slash '/'. * Any other format of periods such as '...' are treated as file/directory names.

The canonical path must 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.

Example 1 · Trailing Slash:

Input: path = "/home/"
Output: "/home"
Explanation: Trailing slash is removed in canonical path.

Example 2 · Multiple Slashes & Up Navigation:

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

Example 3 · Root Boundary Up Navigation:

Input: path = "/home/user/Documents/../Pictures"
Output: "/home/user/Pictures"
Explanation: .. moves up from Documents to user, then down to Pictures.

Example 4 · Root Directory Escapes:

Input: path = "/../"
Output: "/"
Explanation: Going up from root directory stays at root directory.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the directory hierarchy model as a LIFO stack of folder names.
  • Handle root boundary invariants: popping at root stays at root (/.. -> /).
  • Filter multi-slash noise (///) cleanly using tokenization.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Algorithmic Decision Tree:

  • Split string by delimiter '/' into tokens.
  • For each token:
  • If token == "" or token == "." -> continue (skip).
  • If token == ".." -> if stack not empty, stack.pop().
  • Else -> stack.push(token).
  • Join stack elements with '/' and prepend '/'.

Connected Patterns:

Asteroid CollisionDaily TemperaturesBasic Calculator

1. Manual Character-by-Character State Machine

Intuition

Manually iterate through the string with an index pointer, extract directory names between slashes, and push/pop from a stack.

Algorithm

  1. Step 1: Initialize an empty stack st and index i = 0.
  2. Step 2: Loop while i < path.length.
  3. Step 3: Skip all consecutive slashes '/'.
  4. Step 4: Extract token until next slash.
  5. Step 5: Apply folder/parent/current directory rules.
  6. Step 6: Join result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7 std::string simplifyPath(std::string path) {
8 std::vector<std::string> st;
9 int n = path.length();
10 int i = 0;
11 while (i < n) {
12 while (i < n && path[i] == '/') i++;
13 if (i >= n) break;
14 int start = i;
15 while (i < n && path[i] != '/') i++;
16 std::string dir = path.substr(start, i - start);
17 if (dir == ".") continue;
18 if (dir == "..") {
19 if (!st.empty()) st.pop_back();
20 } else {
21 st.push_back(dir);
22 }
23 }
24 std::string res = "";
25 for (const std::string& s : st) {
26 res += "/" + s;
27 }
28 return res.empty() ? "/" : res;
29 }
30};
31
32int main() {
33 Solution solver;
34 std::cout << "Canonical: " << solver.simplifyPath("/home//foo/") << std::endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N) — Single pass over characters extracting tokens without high-level split helpers.
  • Space complexity: O(N) — O(N) space for directory stack.

Why Brute Force Doesn't Scale:

Unneeded copies slow down execution on large path inputs.

Directory stack normalizes 10,000 characters in <2ms.

2. StringStream / Token Split

Intuition

Split the string by '/' into a list of directory names, then iterate through the tokens.

Algorithm

  1. Step 1: Split path by '/'.
  2. Step 2: For each non-empty token:
  3. - If token == ".", ignore.
  4. - If token == "..", pop stack if not empty.
  5. - Else, push token.
  6. Step 3: Join stack with '/'.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <sstream>
5
6class Solution {
7public:
8 std::string simplifyPath(std::string path) {
9 std::stringstream ss(path);
10 std::string token;
11 std::vector<std::string> st;
12 while (std::getline(ss, token, '/')) {
13 if (token == "" || token == ".") continue;
14 if (token == "..") {
15 if (!st.empty()) st.pop_back();
16 } else {
17 st.push_back(token);
18 }
19 }
20 std::string res = "";
21 for (const std::string& dir : st) {
22 res += "/" + dir;
23 }
24 return res.empty() ? "/" : res;
25 }
26};
27
28int main() {
29 Solution solver;
30 std::cout << "Canonical: " << solver.simplifyPath("/a/./b/../../c/") << std::endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N) — Splits string by / and processes tokens sequentially.
  • Space complexity: O(N) — O(N) space for token list and stack.

3. Optimal Linear Directory Stack

Intuition

A LIFO stack naturally mirrors directory level traversal: entering a folder pushes to stack, while .. moves up by popping.

Algorithm

  1. Step 1: Tokenize path by '/'.
  2. Step 2: Initialize an empty directory stack st.
  3. Step 3: Loop through each token: ignore empty and "."; on ".." pop if non-empty; otherwise push folder name.
  4. Step 4: Join remaining stack elements with '/' prefixed by '/'.
  5. Step 5: Return canonical path.

Optimal Directory Stack Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Stack: ['home']
Visual state
Values and pointers at this exact step
stack
TOP
'home'
Push adds to the top · Pop removes from the top
Why this step matters

Stack: [home]

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <sstream>
5
6class Solution {
7public:
8 std::string simplifyPath(std::string path) {
9 std::vector<std::string> stack;
10 std::stringstream ss(path);
11 std::string token;
12
13 while (std::getline(ss, token, '/')) {
14 if (token.empty() || token == ".") {
15 continue;
16 }
17 if (token == "..") {
18 if (!stack.empty()) {
19 stack.pop_back();
20 }
21 } else {
22 stack.push_back(token);
23 }
24 }
25
26 if (stack.empty()) return "/";
27
28 std::string result = "";
29 for (const std::string& dir : stack) {
30 result += "/" + dir;
31 }
32 return result;
33 }
34};
35
36int main() {
37 Solution solver;
38 std::cout << "Canonical: " << solver.simplifyPath("/home/user/Documents/../Pictures") << std::endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N) — Single linear tokenization with each folder pushed and popped at most once.
  • Space complexity: O(N) — O(N) space for building the canonical path string.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Manual Character State MachineO(N)O(N)Index-by-index loop extracting directory substrings.Manual boundary tracking.
2.StringStream / Token SplitO(N)O(N)Split by / into tokens and filter with stack.Token array creation.
3.Optimal Linear Directory StackOptimalO(N)O(N)LIFO folder name stack joined with single slashes.None (Optimal).

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Treating "..." as multiple ".." commands instead of a valid folder name.

Pitfall 2:

Failing to handle multiple consecutive slashes "///".

Pitfall 3:

Popping from an empty stack without checking !stack.empty() on "/..".

Crucial Edge Cases to Validate:

  • Root escape `path = '/../'` — Returns '/'.
  • Multiple consecutive slashes `path = '/a///b//'` — Cleaned to '/a/b'.
  • Trailing slashes `path = '/home/'` — Cleaned to '/home'.
  • File named `...` `path = '/a/.../b'` — Treated as folder name '/a/.../b'.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the tokenization invariant: split by '/' and discard empty tokens "" and ".".
  2. Explain the stack operation: ".." pops (if not at root), and valid names push.
  3. Mention special case names: "..." is a valid folder name, not a navigation command.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What happens when .. is encountered while the stack is already empty (e.g. /../)?

2.How are tokens with three periods ... treated in Unix paths?

Back to DSA Sheet