# Crawler Log Folder
**Difficulty:** EASY
[External](https://leetcode.com/problems/crawler-log-folder)
Canonical: https://scaleengineer.com/dsa/problems/crawler-log-folder
**Data structures:** Array, String, Stack
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Flipkart](https://scaleengineer.com/companies/flipkart), [ZS Associates](https://scaleengineer.com/companies/zs-associates), [Mercari](https://scaleengineer.com/companies/mercari)
---
## Problem
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 needed to go back to the main folder after the change folder operations._

**Example 1:**

![](https://assets.glich.co/dsa/crawler-log-folder/image0.png)

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

**Example 2:**

![](https://assets.glich.co/dsa/crawler-log-folder/image1.png)

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

**Example 3:**

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

**Constraints:**

* `1 <= logs.length <= 103`
* `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.

# Approaches
## Simulation using a Stack
This approach simulates the folder navigation process using a stack. Each time we move into a child folder, we push an element onto the stack. When we move to a parent folder, we pop from the stack. The final size of the stack represents the depth from the main folder.
**Time:** O(N), where N is the number of logs. We perform a single pass through the `logs` array, and each stack operation (push, pop, isEmpty) takes constant time on average. · **Space:** O(N) in the worst case. If the log operations consist only of moving into child folders, the stack can grow to a size of N, where N is the number of logs.
**Pros:** Intuitive and easy to understand as it directly models the folder hierarchy.; Correctly handles all cases described in the problem.
**Cons:** Uses extra space to store folder names (or placeholders) in the stack, which is not strictly necessary for this problem.
### Explanation
We can use a `Stack` data structure to keep track of the current path. The main folder can be represented by an empty stack.

We iterate through the `logs` array one by one.
- For an operation like `"x/"`, it signifies moving deeper into the file system. We can simulate this by pushing a placeholder (or the folder name itself) onto the stack.
- For a `"../"` operation, we move up one level. This is simulated by popping an element from the stack, but only if we are not already in the main folder (i.e., the stack is not empty).
- The `"./"` operation means we stay in the current folder, so we do nothing to the stack.

After processing all the logs, the number of elements remaining in the stack is equal to the depth of the current folder from the main folder. This depth is the minimum number of `"../"` operations required to return to the main folder.

```java
import java.util.Stack;

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("./")) {
                // Do nothing
            } else {
                stack.push(log);
            }
        }
        return stack.size();
    }
}
```
### Algorithm
- Initialize an empty `Stack<String>`.
- Loop through each `log` in the input `logs` array.
- If the `log` is `"../"`, check if the stack is not empty. If it's not, `pop()` an element.
- If the `log` is `"./"`, continue to the next log.
- Otherwise (the log is a folder name like `"x/"`), `push()` the log onto the stack.
- After the loop finishes, return the `size()` of the stack.

## Optimized Approach with a Single Counter
This approach improves upon the stack-based simulation by realizing that we only need to track the *depth* of the current folder, not the actual folder names. A simple integer counter can be used for this purpose, leading to a more space-efficient solution.
**Time:** O(N), where N is the number of logs. We iterate through the array once, performing constant time operations for each log. · **Space:** O(1). We only use a single integer variable for the counter, regardless of the input size. This is the most optimal space complexity possible.
**Pros:** Extremely space-efficient, using only constant extra space.; Simple and fast, with a single pass and basic arithmetic operations.
**Cons:** Slightly less direct simulation of the file system compared to the stack, but this is a minor point as it correctly solves the problem.
### Explanation
Instead of using a stack to store the path, we can use a single integer variable, let's call it `depth`, to keep track of how many levels deep we are from the main folder. We initialize `depth` to 0.

We iterate through the `logs` array.
- When we encounter a `"x/"` operation, we are moving one level deeper, so we increment `depth`.
- When we see a `"../"` operation, we are moving one level up. We decrement `depth`, but with a check to ensure it doesn't go below 0, as we cannot go higher than the main folder.
- The `"./"` operation has no effect on the depth, so we ignore it.

After iterating through all the logs, the final value of `depth` is the minimum number of operations needed to return to the main folder.

```java
class Solution {
    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;
    }
}
```
### Algorithm
- Initialize an integer variable `depth` to 0.
- Loop through each `log` in the input `logs` array.
- If the `log` is `"../"`, check if `depth` is greater than 0. If it is, decrement `depth`.
- If the `log` is `"./"`, do nothing.
- Otherwise (the log is a folder name like `"x/"`), increment `depth`.
- After the loop, return the final value of `depth`.

# Solutions
### Java

```java
class Solution { public int minOperations ( String [] logs ) { int ans = 0 ; for ( var v : logs ) { if ( "../" . equals ( v )) { ans = Math . max ( 0 , ans - 1 ); } else if ( v . charAt ( 0 ) != '.' ) { ++ ans ; } } return ans ; } }
```

### JavaScript

```javascript
function minOperations ( logs ) { let ans = 0 ; for ( const x of logs ) { if ( x === ' ../ ' ) { ans && ans -- ; } else if ( x !== ' ./ ' ) { ans ++ ; } } return ans ; }
```

### CPP

```cpp
class Solution { public: int minOperations ( vector < string >& logs ) { int ans = 0 ; for ( auto & v : logs ) { if ( v == "../" ) { ans = max ( 0 , ans - 1 ); } else if ( v [ 0 ] != '.' ) { ++ ans ; } } return ans ; } };
```

### Python

```python
class Solution : def minOperations ( self , logs : List [ str ]) -> int : ans = 0 for v in logs : if v == "../" : ans = max ( 0 , ans - 1 ) elif v [ 0 ] != "." : ans += 1 return ans
```