medium

Simplity Path

To solve the given problem of converting an absolute Unix-style path to its simplified canonical form using JavaScript, we can use a stack to keep track of the directories encountered while processing the path. We will split the input path by slashes ('/') and process each component one by one. Depending on the component, we will take different actions, such as pushing onto the stack, popping from the stack, or ignoring certain components like '.', '..', and empty strings.

Let's implement the solution:

function simplifyPath(path) {
  const components = path.split("/");
  const stack = [];
 
  for (const component of components) {
    if (component === "" || component === ".") {
      // Ignore empty components and single periods
      continue;
    } else if (component === "..") {
      // Go up one directory level by popping from the stack
      stack.pop();
    } else {
      // Push the current directory onto the stack
      stack.push(component);
    }
  }
 
  // Join the simplified components and construct the canonical path
  return "/" + stack.join("/");
}

Let's analyze the time and space complexity of the solution:

Time Complexity:

• The split method takes linear time O(n), where n is the length of the input path.
• The for-loop iterates through the components, and each operation inside the loop (push, pop, continue, etc.) takes constant time O(1).
• Overall, the time complexity is O(n), where n is the length of the input path.

Space Complexity:

• The components array holds all the split components of the path, which takes additional space of O(n).
• The stack can contain at most n/2 elements (in the case of a path like "/a/b/c/d/..."), so the space complexity of the stack is O(n).
• The overall space complexity is O(n).