Crawler Log Folder

easy stack simulation

Problem

A file-system crawler starts in the main folder and writes one log entry per move: "x/" means it stepped into child folder x, "../" means it moved up to the parent folder (staying put if it is already in the main folder), and "./" means it stayed where it was. After replaying every log entry, return the minimum number of operations needed to get the crawler back to the main folder.

Inputlogs = ["d1/","d2/","../","d21/","./"]

Output2

The crawler ends inside d1/d21, two levels below main, so it needs two "../" moves to return.

logs (comma-separated, e.g. d1/, ../, ./)

def min_operations(logs):
    depth = 0
    for log in logs:
        if log == "../":
            depth = max(depth - 1, 0)
        elif log != "./":
            depth += 1
    return depth

function minOperations(logs) {
  let depth = 0;
  for (const log of logs) {
    if (log === "../") depth = Math.max(depth - 1, 0);
    else if (log !== "./") depth++;
  }
  return depth;
}

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

int minOperations(vector<string>& logs) {
    int depth = 0;
    for (string& log : logs) {
        if (log == "../") depth = max(depth - 1, 0);
        else if (log != "./") depth++;
    }
    return depth;
}

Explanation

The key insight is that the folder names never matter — only how deep the crawler is. The current path behaves exactly like a stack: entering a folder pushes it, "../" pops the top (unless the stack is already empty, because you cannot go above the main folder), and "./" changes nothing. The answer is simply the stack's height when the logs run out, since each "../" undoes exactly one level.

Because only the height matters, we do not even need to store a real stack. A single integer depth is the stack height: a folder log does depth += 1, an up log does depth = max(depth - 1, 0) so it never drops below the main folder, and a stay log is skipped entirely.

Walk through the default example ["d1/","d2/","../","d21/","./"]. "d1/" pushes d1 (depth 1), "d2/" pushes d2 (depth 2), "../" pops d2 (depth 1), "d21/" pushes d21 (depth 2), and "./" is ignored. The crawler finishes two levels deep.

Why is the final depth the minimum number of operations? Each "../" moves up exactly one level and no operation moves up more than one, so from depth d you need at least d operations — and exactly d of them suffice. For the example that gives the answer 2.

The loop touches every log entry once and does constant work per entry, so the time is linear in the number of logs. Since the simulation keeps only one counter instead of a real stack, the extra space is constant.

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