Simplify Path

Problem Statement

Given an absolute file path in a Unix-style file system, return its simplified canonical form.

In a Unix-style file system:

• A single dot . means “stay in the current directory”
• A double dot .. means “go up one level” (to the parent directory)
• Multiple consecutive slashes / are treated as a single slash
• Any trailing slashes are ignored

What to notice first

• The input always starts with a / (it’s an absolute path, not relative).
• You cannot go above the root directory — extra .. at the root should be ignored.
• The output must start with / and have no trailing slash (except if the answer is just /).
• A stack naturally represents a directory hierarchy: push when descending, pop when going up.

Examples

Input	Output	Explanation
/a/./b/../../c/	/c	Start at a, stay at a (.), go back to root (..), then descend to c
/a/../../b/../c//.//	/c	Go up twice from a (to root and beyond, but capped), descend to b, go up, descend to c
/a//b////c/d//././/..	/a/b/c	Multiple slashes treated as one, dots ignored, go up from d to c
/	/	Root directory stays root
/../	/	Cannot go above root, so result is /
/a/	/a	Trailing slash is removed

Constraints

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

Real-World Applications

Where this pattern appears

• File browser normalization — simplify user-entered paths for consistent lookup in a file system.
• URL path resolution — browsers canonicalize paths to prevent directory traversal attacks (e.g., /static/../../secrets → /secrets).
• Build tool path handling — compile systems resolve relative includes (e.g., #include "../config.h") into absolute references.
• Symbolic link flattening — OS kernels simplify paths to detect circular dependencies before following links.
• API endpoint routing — web servers normalize request paths to route correctly (e.g., /api//v1/../v2/users → /api/v2/users).

Complexity Comparison

Approach	Time	Space	Pros	Cons
Stack with Split	O(n)	O(n)	Clean, easy to understand, idiomatic	Allocates intermediate array
String Parsing	O(n)	O(n)	Single pass, no intermediate split	More pointer arithmetic, harder to follow

Both approaches are O(n) time and space. Choose Stack for clarity and interview friendliness, or Parsing if you want to demonstrate low-level string handling.

Which approach should you learn first?

• Pick Stack with Split if you want code that is easy to explain and remember.
• Pick String Parsing if you want to show deep understanding of pointer/index manipulation.
• In practice, most developers use Stack — it is the most readable.

Recommended

Stack with Split

O(n) time · O(n) space

Low-Level Control

String Parsing

O(n) time · O(n) space

Approach 1: Stack with Split (Recommended)

★ Recommended

Split the path by /, filter out empty strings and . (current directory), use a stack to represent the directory hierarchy. When you encounter .., pop from the stack (go up). When you encounter a directory name, push it (go down). Finally, reconstruct the path from the stack.

The key insight is that the stack is a perfect data structure for a directory path: each element is a directory level, and .. is a pop operation.

⏱ Time O(n) Single pass after split 💾 Space O(n) Stack + split array

Step-by-step Example

Input: /a/./b/../../c/

After split by / and filter: ["a", "b", "c"]

Step	Component	Action	Stack State
1	a	Push (descend to a)	["a"]
2	.	Skip (stay in current directory)	["a"]
3	b	Push (descend to b)	["a", "b"]
4	..	Pop (go up to a)	["a"]
5	..	Pop (go up to root)	[]
6	c	Push (descend to c)	["c"]
Final	—	Join with / and prepend /	/c

Animated walkthrough

How the stack solution builds the canonical path

Watch how each directory component is pushed onto the stack, and how .. pops it off. Empty slashes and dots are ignored.

Back Autoplay Next Reset

Step 1 of 8 Target: path

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function simplifyPath(path):
    components = split path by '/' and filter empty + '.'
    stack = []
    for component in components:
        if component == "..":
            if stack is not empty:
                stack.pop()
        else:
            stack.push(component)
    return "/" + join(stack, "/")

Solution Code

Python

simplify_path_stack.py

from typing import List


def simplify_path_stack(path: str) -> str:
    """
    Simplify an absolute path using a stack approach.

    Time: O(n) where n is the length of the path
    Space: O(n) for the stack storing directory names
    """
    # Split path by '/' and filter empty strings
    parts = [part for part in path.split('/') if part and part != '.']

    stack = []
    for part in parts:
        if part == '..':
            # Go up one directory if possible
            if stack:
                stack.pop()
        else:
            # Add directory name to stack
            stack.append(part)

    # Reconstruct the path
    return '/' + '/'.join(stack)


if __name__ == "__main__":
    # Test cases
    print(simplify_path_stack("/a/./b/../../c/"))  # "/c"
    print(simplify_path_stack("/a/../../b/../c//.//"))  # "/c"
    print(simplify_path_stack("/a//b////c/d//././/.."))  # "/a/b/c"
    print(simplify_path_stack("/"))  # "/"
    print(simplify_path_stack("/../"))  # "/"

C++

simplify_path_stack.cpp

#include <iostream>
#include <string>
#include <vector>
#include <sstream>

std::string simplifyPathStack(std::string path) {
    // Split path by '/' and filter empty strings and '.'
    std::vector<std::string> stack;
    std::stringstream ss(path);
    std::string component;

    while (std::getline(ss, component, '/')) {
        if (component.empty() || component == ".") {
            // Skip empty strings and current directory references
            continue;
        } else if (component == "..") {
            // Go up one directory if possible
            if (!stack.empty()) {
                stack.pop_back();
            }
        } else {
            // Add directory name to stack
            stack.push_back(component);
        }
    }

    // Reconstruct the path
    std::string result = "/";
    for (int i = 0; i < (int)stack.size(); i++) {
        if (i > 0) result += "/";
        result += stack[i];
    }

    return result;
}

int main() {
    std::cout << simplifyPathStack("/a/./b/../../c/") << std::endl;  // "/c"
    std::cout << simplifyPathStack("/a/../../b/../c//.//") << std::endl;  // "/c"
    std::cout << simplifyPathStack("/a//b////c/d//././/..") << std::endl;  // "/a/b/c"
    std::cout << simplifyPathStack("/") << std::endl;  // "/"
    std::cout << simplifyPathStack("/../") << std::endl;  // "/"
    return 0;
}

Java

simplify_path_stack.java

import java.util.*;

public class SimplifyPathStack {
    public static String simplifyPath(String path) {
        /**
         * Simplify an absolute path using a stack approach.
         *
         * Time: O(n) where n is the length of the path
         * Space: O(n) for the stack storing directory names
         */
        Stack<String> stack = new Stack<>();
        String[] components = path.split("/");

        for (String component : components) {
            if (component.isEmpty() || component.equals(".")) {
                // Skip empty strings and current directory references
                continue;
            } else if (component.equals("..")) {
                // Go up one directory if possible
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                // Add directory name to stack
                stack.push(component);
            }
        }

        // Reconstruct the path
        StringBuilder result = new StringBuilder("/");
        for (int i = 0; i < stack.size(); i++) {
            if (i > 0) result.append("/");
            result.append(stack.get(i));
        }

        return result.toString();
    }

    public static void main(String[] args) {
        System.out.println(simplifyPath("/a/./b/../../c/"));  // "/c"
        System.out.println(simplifyPath("/a/../../b/../c//.//"));  // "/c"
        System.out.println(simplifyPath("/a//b////c/d//././/.."));  // "/a/b/c"
        System.out.println(simplifyPath("/"));  // "/"
        System.out.println(simplifyPath("/../"));  // "/"
    }
}

JavaScript

simplify_path_stack.js

/**
 * Simplify an absolute path using a stack approach.
 *
 * Time: O(n) where n is the length of the path
 * Space: O(n) for the stack storing directory names
 *
 * @param {string} path - The absolute file path to simplify
 * @returns {string} - The simplified path
 */
function simplifyPathStack(path) {
    // Split path by '/' and filter empty strings and '.'
    const components = path.split('/').filter(c => c && c !== '.');
    const stack = [];

    for (const component of components) {
        if (component === '..') {
            // Go up one directory if possible
            if (stack.length > 0) {
                stack.pop();
            }
        } else {
            // Add directory name to stack
            stack.push(component);
        }
    }

    // Reconstruct the path
    return '/' + stack.join('/');
}

// Test cases
console.log(simplifyPathStack("/a/./b/../../c/"));  // "/c"
console.log(simplifyPathStack("/a/../../b/../c//.//"));  // "/c"
console.log(simplifyPathStack("/a//b////c/d//././/.."));  // "/a/b/c"
console.log(simplifyPathStack("/"));  // "/"
console.log(simplifyPathStack("/../"));  // "/"

Rust

simplify_path_stack.rs

/**
 * Simplify an absolute path using a stack approach.
 *
 * Time: O(n) where n is the length of the path
 * Space: O(n) for the stack storing directory names
 */
pub fn simplify_path(path: String) -> String {
    let mut stack: Vec<String> = Vec::new();

    for component in path.split('/') {
        if component.is_empty() || component == "." {
            // Skip empty strings and current directory references
            continue;
        } else if component == ".." {
            // Go up one directory if possible
            stack.pop();
        } else {
            // Add directory name to stack
            stack.push(component.to_string());
        }
    }

    // Reconstruct the path
    "/".to_string() + &stack.join("/")
}

fn main() {
    println!("{}", simplify_path("/a/./b/../../c/".to_string()));  // "/c"
    println!("{}", simplify_path("/a/../../b/../c//.//".to_string()));  // "/c"
    println!("{}", simplify_path("/a//b////c/d//././/..".to_string()));  // "/a/b/c"
    println!("{}", simplify_path("/".to_string()));  // "/"
    println!("{}", simplify_path("/../".to_string()));  // "/"
}

Go

simplify_path_stack.go

package main

import (
  "fmt"
  "strings"
)

// SimplifyPathStack simplifies an absolute path using a stack approach.
//
// Time: O(n) where n is the length of the path
// Space: O(n) for the stack storing directory names
func SimplifyPathStack(path string) string {
  // Split path by '/' and filter empty strings
  parts := strings.Split(path, "/")
  stack := []string{}

  for _, part := range parts {
    if part == "" || part == "." {
      // Skip empty strings and current directory references
      continue
    } else if part == ".." {
      // Go up one directory if possible
      if len(stack) > 0 {
        stack = stack[:len(stack)-1]
      }
    } else {
      // Add directory name to stack
      stack = append(stack, part)
    }
  }

  // Reconstruct the path
  return "/" + strings.Join(stack, "/")
}

func main() {
  fmt.Println(SimplifyPathStack("/a/./b/../../c/"))  // "/c"
  fmt.Println(SimplifyPathStack("/a/../../b/../c//.//"))  // "/c"
  fmt.Println(SimplifyPathStack("/a//b////c/d//././/.."))  // "/a/b/c"
  fmt.Println(SimplifyPathStack("/"))  // "/"
  fmt.Println(SimplifyPathStack("/../"))  // "/"
}

Approach 2: String Parsing

🎯 Interview Favourite

Instead of splitting the entire path first, parse it character by character. Extract each component between slashes, then apply the same logic: push directory names onto a string buffer, and handle .. by backing up within the buffer.

This approach uses manual index manipulation and is more efficient in languages with mutable strings.

⏱ Time O(n) Single pass, no split 💾 Space O(n) Result string buffer

Step-by-step Example

Input: /a/../../b/../c//.//

Step	Index	Component	Action	Canonical
Start	0	(none)	Initialize	/
1	1	a	Append a	/a
2	3	..	Backtrack to /	/
3	6	..	Backtrack, but capped at root	/
4	9	b	Append b	/b
5	11	..	Backtrack to /	/
6	14	c	Append c	/c
7	15+	(none)	End of string	/c

Pseudocode

function simplifyPathParsing(path):
    canonical = "/"
    i = 0
    while i < len(path):
        skip all '/'
        if i >= len(path): break
        j = i
        extract component from i to next '/'
        if component == "..":
            remove last component from canonical (backtrack)
        else if component != ".":
            append component to canonical
        i = j
    return canonical

Solution Code

Python

simplify_path_parsing.py

from typing import List


def simplify_path_parsing(path: str) -> str:
    """
    Simplify an absolute path using string parsing.

    Time: O(n) where n is the length of the path
    Space: O(n) for the result string
    """
    # Start with root
    canonical = "/"
    i = 0

    while i < len(path):
        # Skip slashes
        while i < len(path) and path[i] == '/':
            i += 1

        if i >= len(path):
            break

        # Extract the next component
        j = i
        while j < len(path) and path[j] != '/':
            j += 1

        component = path[i:j]

        if component == '..':
            # Go up one level (remove last component from canonical)
            # Find the last '/' and remove everything after it
            last_slash = canonical.rfind('/')
            if last_slash > 0:  # Don't go above root
                canonical = canonical[:last_slash]
        elif component != '.':
            # Add the component to canonical path
            if canonical != '/':
                canonical += '/'
            canonical += component
        # If component == '.', we skip it (stay in current directory)

        i = j

    return canonical


if __name__ == "__main__":
    # Test cases
    print(simplify_path_parsing("/a/./b/../../c/"))  # "/c"
    print(simplify_path_parsing("/a/../../b/../c//.//"))  # "/c"
    print(simplify_path_parsing("/a//b////c/d//././/.."))  # "/a/b/c"
    print(simplify_path_parsing("/"))  # "/"
    print(simplify_path_parsing("/../"))  # "/"

C++

simplify_path_parsing.cpp

#include <iostream>
#include <string>

std::string simplifyPathParsing(std::string path) {
    std::string canonical = "/";
    int i = 0;

    while (i < (int)path.length()) {
        // Skip slashes
        while (i < (int)path.length() && path[i] == '/') {
            i++;
        }

        if (i >= (int)path.length()) {
            break;
        }

        // Extract the next component
        int j = i;
        while (j < (int)path.length() && path[j] != '/') {
            j++;
        }

        std::string component = path.substr(i, j - i);

        if (component == "..") {
            // Go up one level
            int lastSlash = canonical.rfind('/');
            if (lastSlash > 0) {  // Don't go above root
                canonical = canonical.substr(0, lastSlash);
            }
        } else if (component != ".") {
            // Add the component to canonical path
            if (canonical != "/") {
                canonical += "/";
            }
            canonical += component;
        }

        i = j;
    }

    return canonical;
}

int main() {
    std::cout << simplifyPathParsing("/a/./b/../../c/") << std::endl;  // "/c"
    std::cout << simplifyPathParsing("/a/../../b/../c//.//") << std::endl;  // "/c"
    std::cout << simplifyPathParsing("/a//b////c/d//././/..") << std::endl;  // "/a/b/c"
    std::cout << simplifyPathParsing("/") << std::endl;  // "/"
    std::cout << simplifyPathParsing("/../") << std::endl;  // "/"
    return 0;
}

Java

simplify_path_parsing.java

public class SimplifyPathParsing {
    public static String simplifyPath(String path) {
        /**
         * Simplify an absolute path using string parsing.
         *
         * Time: O(n) where n is the length of the path
         * Space: O(n) for the result string
         */
        StringBuilder canonical = new StringBuilder("/");
        int i = 0;

        while (i < path.length()) {
            // Skip slashes
            while (i < path.length() && path.charAt(i) == '/') {
                i++;
            }

            if (i >= path.length()) {
                break;
            }

            // Extract the next component
            int j = i;
            while (j < path.length() && path.charAt(j) != '/') {
                j++;
            }

            String component = path.substring(i, j);

            if (component.equals("..")) {
                // Go up one level
                int len = canonical.length();
                if (len > 1) {  // Don't go above root
                    canonical.setLength(canonical.lastIndexOf("/"));
                }
            } else if (!component.equals(".")) {
                // Add the component to canonical path
                if (!canonical.toString().equals("/")) {
                    canonical.append("/");
                }
                canonical.append(component);
            }

            i = j;
        }

        return canonical.toString();
    }

    public static void main(String[] args) {
        System.out.println(simplifyPath("/a/./b/../../c/"));  // "/c"
        System.out.println(simplifyPath("/a/../../b/../c//.//"));  // "/c"
        System.out.println(simplifyPath("/a//b////c/d//././/.."));  // "/a/b/c"
        System.out.println(simplifyPath("/"));  // "/"
        System.out.println(simplifyPath("/../"));  // "/"
    }
}

JavaScript

simplify_path_parsing.js

/**
 * Simplify an absolute path using string parsing.
 *
 * Time: O(n) where n is the length of the path
 * Space: O(n) for the result string
 *
 * @param {string} path - The absolute file path to simplify
 * @returns {string} - The simplified path
 */
function simplifyPathParsing(path) {
    let canonical = "/";
    let i = 0;

    while (i < path.length) {
        // Skip slashes
        while (i < path.length && path[i] === '/') {
            i++;
        }

        if (i >= path.length) {
            break;
        }

        // Extract the next component
        let j = i;
        while (j < path.length && path[j] !== '/') {
            j++;
        }

        const component = path.substring(i, j);

        if (component === '..') {
            // Go up one level
            const lastSlash = canonical.lastIndexOf('/');
            if (lastSlash > 0) {  // Don't go above root
                canonical = canonical.substring(0, lastSlash);
            }
        } else if (component !== '.') {
            // Add the component to canonical path
            if (canonical !== '/') {
                canonical += '/';
            }
            canonical += component;
        }

        i = j;
    }

    return canonical;
}

// Test cases
console.log(simplifyPathParsing("/a/./b/../../c/"));  // "/c"
console.log(simplifyPathParsing("/a/../../b/../c//.//"));  // "/c"
console.log(simplifyPathParsing("/a//b////c/d//././/.."));  // "/a/b/c"
console.log(simplifyPathParsing("/"));  // "/"
console.log(simplifyPathParsing("/../"));  // "/"

Rust

simplify_path_parsing.rs

/**
 * Simplify an absolute path using string parsing.
 *
 * Time: O(n) where n is the length of the path
 * Space: O(n) for the result string
 */
pub fn simplify_path(path: String) -> String {
    let mut canonical = String::from("/");
    let mut i = 0;
    let chars: Vec<char> = path.chars().collect();

    while i < chars.len() {
        // Skip slashes
        while i < chars.len() && chars[i] == '/' {
            i += 1;
        }

        if i >= chars.len() {
            break;
        }

        // Extract the next component
        let mut j = i;
        while j < chars.len() && chars[j] != '/' {
            j += 1;
        }

        let component: String = chars[i..j].iter().collect();

        if component == ".." {
            // Go up one level
            if canonical.len() > 1 {
                if let Some(last_slash) = canonical[..canonical.len() - 1].rfind('/') {
                    canonical.truncate(last_slash);
                }
            }
        } else if component != "." {
            // Add the component to canonical path
            if canonical != "/" {
                canonical.push('/');
            }
            canonical.push_str(&component);
        }

        i = j;
    }

    canonical
}

fn main() {
    println!("{}", simplify_path("/a/./b/../../c/".to_string()));  // "/c"
    println!("{}", simplify_path("/a/../../b/../c//.//".to_string()));  // "/c"
    println!("{}", simplify_path("/a//b////c/d//././/..".to_string()));  // "/a/b/c"
    println!("{}", simplify_path("/".to_string()));  // "/"
    println!("{}", simplify_path("/../".to_string()));  // "/"
}

Go

simplify_path_parsing.go

package main

import (
  "fmt"
  "strings"
)

// SimplifyPathParsing simplifies an absolute path using string parsing.
//
// Time: O(n) where n is the length of the path
// Space: O(n) for the result string
func SimplifyPathParsing(path string) string {
  canonical := "/"
  i := 0

  for i < len(path) {
    // Skip slashes
    for i < len(path) && path[i] == '/' {
      i++
    }

    if i >= len(path) {
      break
    }

    // Extract the next component
    j := i
    for j < len(path) && path[j] != '/' {
      j++
    }

    component := path[i:j]

    if component == ".." {
      // Go up one level
      lastSlash := strings.LastIndex(canonical[:len(canonical)-1], "/")
      if lastSlash >= 0 {  // Don't go above root
        canonical = canonical[:lastSlash+1]
      } else if canonical != "/" {
        canonical = "/"
      }
    } else if component != "." {
      // Add the component to canonical path
      if canonical != "/" {
        canonical += "/"
      }
      canonical += component
    }

    i = j
  }

  return canonical
}

func main() {
  fmt.Println(SimplifyPathParsing("/a/./b/../../c/"))  // "/c"
  fmt.Println(SimplifyPathParsing("/a/../../b/../c//.//"))  // "/c"
  fmt.Println(SimplifyPathParsing("/a//b////c/d//././/.."))  // "/a/b/c"
  fmt.Println(SimplifyPathParsing("/"))  // "/"
  fmt.Println(SimplifyPathParsing("/../"))  // "/"
}

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

simplify_path_space_optimized.py

"""
Solution for Simplify Path
"""

def solve():
    """Implementation for approach 3 of Simplify Path"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

simplify_path_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Simplify Path
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

SimplifyPathSpaceOptimized.java

/**
 * Solution for Simplify Path
 * Approach 3
 */
public class SimplifyPathSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

simplify_path_space_optimized.js

/**
 * Solution for Simplify Path
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

simplify_path_space_optimized.rs

/// Solution for Simplify Path
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

simplify_path_space_optimized.go

package main

import "fmt"

// Solution for Simplify Path
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Forgetting that .. at root does nothing. Always check that the stack/canonical path is not empty before popping. If you are already at root, an extra .. should not change anything.
• Trailing slashes in output. The output must not have a trailing / unless the answer is exactly /. Make sure your join/reconstruction logic handles this.
• Confusing . with ... A single dot means “stay here” (do nothing), while double-dot means “go to parent” (pop/backtrack).
• Not handling multiple consecutive slashes. The input may have /a//b///c, which should be treated as /a/b/c. Split by / naturally handles this by creating empty strings, which we filter out.
• Off-by-one errors in string parsing. If parsing manually, be careful with loop bounds and the positions of slashes.

Interview Tips

Key trade-offs to discuss

• Why Stack over manual parsing? It is clearer, easier to explain, and less prone to index errors. Most real-world code uses this.
• When to use parsing over split? If memory is constrained or you are optimizing for zero intermediate allocations (rare in interviews, but good to mention).
• Edge case — root directory. Clarify with the interviewer: can the input be /// (multiple slashes at root)? The problem statement says it’s a valid path, so assume / is the only possible root-only input.
• Follow-up — canonical URLs. After solving this, discuss how you would apply the same logic to URL paths (which have a scheme and domain prefix).
• Alternative approach — deque or reverse processing. Some solutions use a deque and process from the end, but the stack approach is simpler to understand.

Related Problems

• Valid Number ↗ Hard #65
• Valid Parentheses ↗ Easy #20
• Evaluate Reverse Polish Notation ↗ Medium #150
• Longest Valid Parentheses ↗ Hard #32

← Previous
#70 Climbing Stairs Next
#72 Edit Distance →