Crawler Log Folder

Difficulty: Easy | Acceptance: 71.70% | Paid: No Topics: Array, String, Stack

The Leetcode file system 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 to go back to the main folder after the change folder operations.

• Examples
• Constraints
• Simulation with Counter
• Stack Simulation

Examples

Input: logs = ["d1/","d2/","../","d21/","./"]
Output: 2
Explanation: Use this change folder operation "../" 2 times and go back to the main folder.

Input: logs = ["d1/","d2/","./","d3/","../","d31/"]
Output: 3

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

Constraints

1 <= logs.length <= 10³
2 <= logs[i].length <= 10
logs[i] contains lowercase English letters, digits, '.', and '/'.
logs[i] follows the format described in the problem.

Simulation with Counter

Intuition Since we only need to know the depth relative to the main folder, we can simulate the process using a single integer counter representing the current depth.

Steps

• Initialize a variable depth to 0.
• Iterate through each operation in the logs array.
• If the operation is "../", decrement depth by 1, but ensure it does not go below 0.
• If the operation is "./", do nothing.
• For any other operation (moving into a child folder), increment depth by 1.
• Return the final value of depth.

from typing import List

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

Complexity

• Time: O(n), where n is the number of logs.
• Space: O(1), as we only use a single variable for tracking depth.
• Notes: This is the most space-efficient approach.

Stack Simulation

Intuition We can explicitly simulate the folder structure using a stack. Each time we enter a folder, we push it onto the stack, and each time we move up, we pop from the stack.

Steps

• Initialize an empty stack.
• Iterate through each operation in the logs array.
• If the operation is "../", check if the stack is not empty and pop the top element.
• If the operation is "./", do nothing.
• For any other operation, push the folder name (or a placeholder) onto the stack.
• The size of the stack represents the distance from the main folder. Return the stack size.

from typing import List

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

Complexity

• Time: O(n), where n is the number of logs.
• Space: O(n), in the worst case where we only move into child folders.
• Notes: While conceptually clear, this uses more memory than the counter approach.