Move from brute-force thinking to an efficient approach using stack strategy.
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:
'.' represents the current directory.'..' represents the previous/parent directory.'//' and '///' are treated as a single slash '/'.'...' and '....' are valid directory or file names.The simplified canonical path should follow these rules:
'/'.'/'.'/', unless it is the root directory.'.' 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 <= 3000path consists of English letters, digits, period '.', slash '/' or '_'.path is a valid absolute Unix path.Problem summary: 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
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Stack
"/home/"
"/home//foo/"
"/home/user/Documents/../Pictures"
import java.util.*;
class Solution {
public String simplifyPath(String path) {
Deque<String> stack = new ArrayDeque<>();
for (String part : path.split("/")) {
if (part.isEmpty() || part.equals(".")) continue;
if (part.equals("..")) {
if (!stack.isEmpty()) stack.removeLast();
} else {
stack.addLast(part);
}
}
if (stack.isEmpty()) return "/";
StringBuilder sb = new StringBuilder();
for (String dir : stack) sb.append('/').append(dir);
return sb.toString();
}
}
import "strings"
func simplifyPath(path string) string {
stack := []string{}
for _, part := range strings.Split(path, "/") {
if part == "" || part == "." {
continue
}
if part == ".." {
if len(stack) > 0 {
stack = stack[:len(stack)-1]
}
} else {
stack = append(stack, part)
}
}
return "/" + strings.Join(stack, "/")
}
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
for part in path.split('/'):
if not part or part == '.':
continue
if part == '..':
if stack:
stack.pop()
else:
stack.append(part)
return '/' + '/'.join(stack)
impl Solution {
pub fn simplify_path(path: String) -> String {
let mut stack: Vec<&str> = Vec::new();
for part in path.split('/') {
if part.is_empty() || part == "." {
continue;
}
if part == ".." {
stack.pop();
} else {
stack.push(part);
}
}
if stack.is_empty() {
"/".to_string()
} else {
format!("/{}", stack.join("/"))
}
}
}
function simplifyPath(path: string): string {
const stack: string[] = [];
for (const part of path.split('/')) {
if (part === '' || part === '.') continue;
if (part === '..') {
if (stack.length) stack.pop();
} else {
stack.push(part);
}
}
return '/' + stack.join('/');
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan left (or right) to find the next greater/smaller element. The inner scan can visit up to n elements per outer iteration, giving O(n²) total comparisons. No extra space needed beyond loop variables.
Each element is pushed onto the stack at most once and popped at most once, giving 2n total operations = O(n). The stack itself holds at most n elements in the worst case. The key insight: amortized O(1) per element despite the inner while-loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.