algoadvance

Leetcode 1598. Crawler Log Folder

Problem Statement

You are given a list of strings logs where logs[i] is one of the following:

  1. "../" - Move to the parent folder.
  2. "./" - Remain in the current folder.
  3. "x/" - Move to the child folder named x. This will always be a valid name (containing only alphanumeric characters).

The file system starts in the main folder, which is represented as the root or the starting point ("/").

You need to determine the minimum number of operations required to go back to the main folder after executing all of the log operations.

Clarifying Questions

  1. Are the strings in logs always valid (i.e., do not move above the root directory)?
  2. What is the maximum length of the logs array?

Strategy

We will simulate the traversal of the file system using a counter to keep track of the depth of the current directory:

  1. Start with a depth counter initialized to 0, representing the main folder.
  2. Iterate through each log entry:
    • "../": Decrease the depth by 1 (if depth > 0).
    • "./": No change in depth.
    • "x/": Increase the depth by 1.
  3. The final value of the depth counter will be the minimum number of operations required to return to the main folder.

Code

public class CrawlerLogFolder {
    public int minOperations(String[] logs) {
        int depth = 0;
        
        for (String log : logs) {
            if (log.equals("../")) {
                if (depth > 0) depth--;
            } else if (!log.equals("./")) {
                depth++;
            }
        }
        
        return depth;
    }
    
    public static void main(String[] args) {
        CrawlerLogFolder clf = new CrawlerLogFolder();
        
        String[] logs1 = {"d1/", "d2/", "../", "d21/", "./"};
        System.out.println(clf.minOperations(logs1));  // Output: 2
        
        String[] logs2 = {"d1/", "d2/", "./", "d3/", "../", "d31/"};
        System.out.println(clf.minOperations(logs2));  // Output: 3
        
        String[] logs3 = {"d1/", "../", "../", "../"};
        System.out.println(clf.minOperations(logs3));  // Output: 0
    }
}

Time Complexity

The solution iterates through the logs array exactly once, making its time complexity:

Since we only use a single counter to keep track of the depth, the space complexity is:

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI