Simplify Path - Solution & Explanation

Problem Overview: You receive an absolute Unix-style path such as /a/./b/../../c/ and must convert it into its canonical form. The canonical path removes redundant slashes, ignores . (current directory), and correctly handles .. (move to parent directory).

Approach 1: Using Stack Data Structure (Time: O(n), Space: O(n))

The most common solution processes directory segments using a stack. Split the input path by '/' and iterate through each token. Ignore empty strings and . because they represent the current directory. When encountering .., pop the last directory from the stack if one exists. Otherwise, push valid directory names onto the stack.

This works because the stack naturally models navigation through directories: pushing represents moving deeper into a folder, while popping represents returning to the parent directory. After processing all segments, join the stack contents with '/' and prepend a leading slash to build the canonical path. Parsing the string takes O(n) time where n is the path length, and the stack stores at most n characters overall, giving O(n) space.

Approach 2: Optimized String Handling (Time: O(n), Space: O(n))

This version avoids explicit stack APIs and relies on efficient string parsing with a dynamic list of path components. Scan the path character by character and build directory tokens manually. When a slash is encountered, process the collected token: ignore ., remove the last stored directory for .., or append the token if it represents a valid directory name.

The key idea is that you still maintain logical stack behavior, but operations happen directly on a list or string builder rather than a dedicated stack structure. This reduces overhead from repeated splits and can be faster for very long paths. The algorithm still touches each character once, resulting in O(n) time and O(n) auxiliary space for stored directories.

Recommended for interviews: The stack approach is what interviewers usually expect because it clearly demonstrates understanding of directory traversal rules and the natural LIFO behavior required for handling ... Showing the stack-based logic first proves correctness and clarity. The optimized parsing version demonstrates deeper understanding of string processing and performance tradeoffs.