1598. Crawler Log Folder - Explanation

Problem Link

Description

There is a file system that keeps a log each time some user performs a change folder operation.

The operations are described below:

"../" : Move to the parent folder of the current folder. (If you are already in the main folder, remain in the same folder).
"./" : Remain in the same folder.
"x/" : Move to the child folder named x (This folder is guaranteed to always exist).

You are given a list of strings logs where logs[i] is the operation performed by the user at the ith step.

The file system starts in the main folder, then the operations in logs are performed.

Return the minimum number of operations needed to go back to the main folder after the change folder operations.

Example 1:

Input: logs = ["d1/","d2/","../","d21/","./"]

Output: 2

Explanation: After all the log operations, use this change folder operation "../" 2 times and go back to the main folder.

Example 2:

Input: logs = ["d1/","../","../","../"]

Output: 0

Example 3:

Input: logs = ["d1/","d2/","../","d3/","../","d4/","../","d5/"]

Output: 2

Constraints:

1 <= logs.length <= 1000
2 <= logs[i].length <= 10
logs[i] contains lowercase English letters, digits, '.', and '/'.
logs[i] follows the format described in the statement.
Folder names consist of lowercase English letters and digits.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Stack Data Structure - Understanding push/pop operations and how stacks model nested or hierarchical state
String Comparison - Comparing strings for equality to distinguish between different folder operations

1. Stack

Intuition

A file system path can be naturally modeled using a stack. Moving into a folder pushes onto the stack, while moving to the parent folder pops from the stack. The operation "./" does nothing (stay in current folder). At the end, the stack's size represents how deep we are from the main folder, which equals the minimum operations needed to return.

Algorithm

Initialize an empty stack.
For each log operation:
- If it is "../", pop from the stack if it is not empty (move to parent).
- If it is "./", do nothing (stay in current folder).
- Otherwise, push the folder name onto the stack (move into child folder).
Return the size of the stack, representing the depth from the main folder.

class Solution:
    def minOperations(self, logs: List[str]) -> int:
        stack = []
        for log in logs:
            if log == "../":
                if stack:
                    stack.pop()
            elif log != "./":
                stack.append(log)
        return len(stack)

public class Solution {
    public int minOperations(String[] logs) {
        Stack<String> stack = new Stack<>();
        for (String log : logs) {
            if (log.equals("../")) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else if (!log.equals("./")) {
                stack.push(log);
            }
        }
        return stack.size();
    }
}

class Solution {
public:
    int minOperations(vector<string>& logs) {
        stack<string> st;
        for (auto& log : logs) {
            if (log == "../") {
                if (!st.empty()) {
                    st.pop();
                }
            } else if (log != "./") {
                st.push(log);
            }
        }
        return st.size();
    }
};

class Solution {
    /**
     * @param {string[]} logs
     * @return {number}
     */
    minOperations(logs) {
        let stack = [];
        for (let log of logs) {
            if (log === "../") {
                if (stack.length > 0) {
                    stack.pop();
                }
            } else if (log !== "./") {
                stack.push(log);
            }
        }
        return stack.length;
    }
}

public class Solution {
    public int MinOperations(string[] logs) {
        Stack<string> stack = new Stack<string>();
        foreach (string log in logs) {
            if (log == "../") {
                if (stack.Count > 0) {
                    stack.Pop();
                }
            } else if (log != "./") {
                stack.Push(log);
            }
        }
        return stack.Count;
    }
}

func minOperations(logs []string) int {
    stack := []string{}
    for _, log := range logs {
        if log == "../" {
            if len(stack) > 0 {
                stack = stack[:len(stack)-1]
            }
        } else if log != "./" {
            stack = append(stack, log)
        }
    }
    return len(stack)
}

class Solution {
    fun minOperations(logs: Array<String>): Int {
        val stack = ArrayDeque<String>()
        for (log in logs) {
            if (log == "../") {
                if (stack.isNotEmpty()) {
                    stack.removeLast()
                }
            } else if (log != "./") {
                stack.addLast(log)
            }
        }
        return stack.size
    }
}

class Solution {
    func minOperations(_ logs: [String]) -> Int {
        var stack = [String]()
        for log in logs {
            if log == "../" {
                if !stack.isEmpty {
                    stack.removeLast()
                }
            } else if log != "./" {
                stack.append(log)
            }
        }
        return stack.count
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Iteration

Intuition

We do not actually need to store the folder names since we only care about the depth. A simple counter can track how many levels deep we are. Moving into a folder increments the counter, moving to parent decrements it (but never below 0 since we cannot go above the main folder), and "./" leaves it unchanged.

Algorithm

Initialize a depth counter to 0.
For each log operation:
- If it is "./", skip (no change in depth).
- If it is "../", decrement the counter but ensure it does not go below 0.
- Otherwise, increment the counter (moving into a child folder).
Return the counter value as the minimum operations to return to main folder.

class Solution:
    def minOperations(self, logs: List[str]) -> int:
        res = 0
        for log in logs:
            if log == "./":
                continue
            if log == "../":
                res = max(0, res - 1)
            else:
                res += 1
        return res

public class Solution {
    public int minOperations(String[] logs) {
        int res = 0;
        for (String log : logs) {
            if (log.equals("./")) {
                continue;
            }
            if (log.equals("../")) {
                res = Math.max(0, res - 1);
            } else {
                res++;
            }
        }
        return res;
    }
}

class Solution {
public:
    int minOperations(vector<string>& logs) {
        int res = 0;
        for (auto& log : logs) {
            if (log == "./") {
                continue;
            }
            if (log == "../") {
                res = max(0, res - 1);
            } else {
                res++;
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {string[]} logs
     * @return {number}
     */
    minOperations(logs) {
        let res = 0;
        for (let log of logs) {
            if (log === "./") {
                continue;
            }
            if (log === "../") {
                res = Math.max(0, res - 1);
            } else {
                res++;
            }
        }
        return res;
    }
}

public class Solution {
    public int MinOperations(string[] logs) {
        int res = 0;
        foreach (string log in logs) {
            if (log == "./") {
                continue;
            }
            if (log == "../") {
                res = Math.Max(0, res - 1);
            } else {
                res++;
            }
        }
        return res;
    }
}

func minOperations(logs []string) int {
    res := 0
    for _, log := range logs {
        if log == "./" {
            continue
        }
        if log == "../" {
            if res > 0 {
                res--
            }
        } else {
            res++
        }
    }
    return res
}

class Solution {
    fun minOperations(logs: Array<String>): Int {
        var res = 0
        for (log in logs) {
            if (log == "./") {
                continue
            }
            if (log == "../") {
                res = maxOf(0, res - 1)
            } else {
                res++
            }
        }
        return res
    }
}

class Solution {
    func minOperations(_ logs: [String]) -> Int {
        var res = 0
        for log in logs {
            if log == "./" {
                continue
            }
            if log == "../" {
                res = max(0, res - 1)
            } else {
                res += 1
            }
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Allowing Depth to Go Negative

When processing "../", you must ensure the depth does not go below zero. Going above the main folder is impossible, so decrementing when already at depth 0 produces wrong results.

# Wrong: depth can become negative
if log == "../":
    depth -= 1

# Correct: clamp at zero
if log == "../":
    depth = max(0, depth - 1)

Forgetting to Handle the Current Directory Operation

The operation "./" means stay in the current folder and should not change the depth. Treating it like a folder name and incrementing depth is a common mistake.

# Wrong: treating "./" as a folder
if log != "../":
    depth += 1  # This incorrectly increments for "./"

# Correct: explicitly skip "./"
if log == "./":
    continue
elif log == "../":
    depth = max(0, depth - 1)
else:
    depth += 1