LeetCode 1598 - Crawler Log Folder

In this problem, we are simulating navigation inside a file system. The system starts at the main folder, and we are giv

leetcodeeasyarraystringstack

LeetCode Problem 1598

Difficulty: 🟢 Easy
Topics: Array, String, Stack

Solution

Problem Understanding

In this problem, we are simulating navigation inside a file system. The system starts at the main folder, and we are given a sequence of folder navigation operations. Each operation changes the current directory in one of three ways.

The operation "../" means moving up to the parent directory. However, if we are already at the main folder, we cannot go any higher, so we stay where we are.

The operation "./" means staying in the current folder. It does not change the directory depth.

Any operation of the form "x/" means moving into a child folder named x. The problem guarantees that such folders always exist, so we do not need to validate folder names or handle invalid navigation.

The goal is to determine how many "../" operations are required to return to the main folder after all operations have been processed. In other words, we need to compute the current folder depth after simulating all commands.

The input is an array of strings called logs. Each string represents one navigation operation. The output is a single integer representing the minimum number of parent-folder moves needed to get back to the root directory.

The constraints are small:

  • 1 <= logs.length <= 1000
  • Each log string has length between 2 and 10

Since the input size is modest, even less efficient approaches would work, but the problem is clearly designed for a straightforward linear scan.

Several edge cases are important:

  • Multiple "../" operations while already at the root folder should never make the depth negative.
  • "./" operations should not change the state at all.
  • Consecutive child-folder operations increase nesting depth.
  • The final depth itself is the answer because each "../" reduces depth by exactly one.

Approaches

Brute Force Approach

A brute-force approach would explicitly simulate the file system path using a stack of folder names.

Whenever we encounter a child folder like "d1/", we push the folder name onto the stack. When we encounter "../", we pop from the stack if it is not empty. When we encounter "./", we do nothing.

At the end, the size of the stack represents the current directory depth, which is also the number of operations needed to return to the root.

This approach is correct because the stack accurately models the folder hierarchy. Every child-folder operation adds one level, and every parent-folder operation removes one level.

However, storing actual folder names is unnecessary because the problem only asks for the depth, not the full path.

Optimal Approach

The key observation is that we only care about the current depth, not the names of the folders themselves.

Instead of maintaining a stack of folder names, we can simply keep an integer variable called depth.

  • "x/" increases depth by 1
  • "../" decreases depth by 1, but never below 0
  • "./" leaves depth unchanged

After processing all operations, depth directly represents the number of steps needed to return to the main folder.

This approach is simpler and uses constant extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Uses a stack to store folder names
Optimal O(n) O(1) Tracks only the current depth

Algorithm Walkthrough

  1. Initialize a variable depth to 0.

This variable represents how many levels deep we currently are relative to the main folder. 2. Iterate through each operation in logs.

We process the operations one by one in the order they occur. 3. If the operation is "../":

  • Check whether depth > 0
  • If true, decrement depth by 1

We cannot move above the main folder, so depth is never allowed to become negative. 4. If the operation is "./":

  • Do nothing

This operation means staying in the same directory. 5. Otherwise, the operation must be a child-folder move like "d1/":

  • Increment depth by 1

Moving into a child folder increases nesting depth. 6. After processing all operations, return depth.

Each "../" operation reduces depth by exactly one, so the current depth equals the minimum number of operations needed to return to the root.

Why it works

The algorithm maintains the invariant that depth always equals the current distance from the main folder.

  • Entering a child folder increases this distance by one.
  • Moving to a parent folder decreases it by one, unless already at the root.
  • Staying in the same folder leaves it unchanged.

Because every operation updates depth exactly according to the folder navigation rules, the final value of depth is precisely the number of "../" operations needed to return to the main folder.

Python Solution

from typing import List

class Solution:
    def minOperations(self, logs: List[str]) -> int:
        depth = 0

        for operation in logs:
            if operation == "../":
                if depth > 0:
                    depth -= 1
            elif operation == "./":
                continue
            else:
                depth += 1

        return depth

The implementation starts by initializing depth to zero because we begin in the main folder.

The loop processes each log entry one at a time. If the operation is "../", we attempt to move upward. We first check whether depth is positive to avoid going above the root directory.

If the operation is "./", we simply continue because the current folder does not change.

All remaining operations are child-folder moves such as "d1/" or "abc/". In those cases, we increment depth because we move one level deeper into the file system.

Finally, the function returns depth, which represents the number of parent-folder operations required to return to the main folder.

Go Solution

func minOperations(logs []string) int {
    depth := 0

    for _, operation := range logs {
        if operation == "../" {
            if depth > 0 {
                depth--
            }
        } else if operation == "./" {
            continue
        } else {
            depth++
        }
    }

    return depth
}

The Go implementation follows the same logic as the Python version. The main difference is syntax.

Go uses a for _, operation := range logs loop to iterate through the slice. The depth variable is an integer initialized to zero.

No special handling for integer overflow is needed because the constraints are very small. The implementation also does not require slices or stacks because only the current depth matters.

Worked Examples

Example 1

logs = ["d1/","d2/","../","d21/","./"]
Step Operation Action Depth
Start - Begin at main folder 0
1 "d1/" Move into child folder 1
2 "d2/" Move into child folder 2
3 "../" Move to parent folder 1
4 "d21/" Move into child folder 2
5 "./" Stay in current folder 2

Final answer: 2

We are two levels deep, so we need two "../" operations to return to the main folder.

Example 2

logs = ["d1/","d2/","./","d3/","../","d31/"]
Step Operation Action Depth
Start - Begin at main folder 0
1 "d1/" Move into child folder 1
2 "d2/" Move into child folder 2
3 "./" Stay in current folder 2
4 "d3/" Move into child folder 3
5 "../" Move to parent folder 2
6 "d31/" Move into child folder 3

Final answer: 3

Example 3

logs = ["d1/","../","../","../"]
Step Operation Action Depth
Start - Begin at main folder 0
1 "d1/" Move into child folder 1
2 "../" Move to parent folder 0
3 "../" Already at root, stay there 0
4 "../" Already at root, stay there 0

Final answer: 0

Complexity Analysis

Measure Complexity Explanation
Time O(n) We process each log entry exactly once
Space O(1) Only a single integer variable is used

The algorithm performs one pass through the logs array. Each operation requires constant time work, so the total runtime is linear in the number of logs.

The space usage is constant because we only store the current depth counter. No additional data structures proportional to input size are needed.

Test Cases

from typing import List

class Solution:
    def minOperations(self, logs: List[str]) -> int:
        depth = 0

        for operation in logs:
            if operation == "../":
                if depth > 0:
                    depth -= 1
            elif operation == "./":
                continue
            else:
                depth += 1

        return depth

solution = Solution()

assert solution.minOperations(
    ["d1/", "d2/", "../", "d21/", "./"]
) == 2  # Example 1

assert solution.minOperations(
    ["d1/", "d2/", "./", "d3/", "../", "d31/"]
) == 3  # Example 2

assert solution.minOperations(
    ["d1/", "../", "../", "../"]
) == 0  # Example 3

assert solution.minOperations(
    ["./", "./", "./"]
) == 0  # Only stay operations

assert solution.minOperations(
    ["d1/", "d2/", "d3/"]
) == 3  # Only moving deeper

assert solution.minOperations(
    ["../", "../", "../"]
) == 0  # Cannot go above root

assert solution.minOperations(
    ["d1/", "../", "d2/", "../"]
) == 0  # Return to root repeatedly

assert solution.minOperations(
    ["d1/", "./", "./", "d2/", "../"]
) == 1  # Mixed operations

assert solution.minOperations(
    ["x/", "y/", "z/", "../", "../", "../"]
) == 0  # Back to root exactly

assert solution.minOperations(
    ["a/", "b/", "../", "c/", "d/", "../", "./"]
) == 2  # Complex mixed sequence
Test Why
["d1/", "d2/", "../", "d21/", "./"] Validates example 1
["d1/", "d2/", "./", "d3/", "../", "d31/"] Validates example 2
["d1/", "../", "../", "../"] Ensures depth never becomes negative
["./", "./", "./"] Verifies no-op operations
["d1/", "d2/", "d3/"] Tests continuous descent
["../", "../", "../"] Tests repeated parent moves at root
["d1/", "../", "d2/", "../"] Tests repeated return to root
["d1/", "./", "./", "d2/", "../"] Tests mixed navigation
["x/", "y/", "z/", "../", "../", "../"] Ensures exact balancing works
["a/", "b/", "../", "c/", "d/", "../", "./"] Tests a longer mixed sequence

Edge Cases

Repeated Parent Operations at the Root

An important edge case occurs when the logs contain multiple "../" operations while already in the main folder.

For example:

["../", "../", "../"]

A naive implementation might allow the depth to become negative, which would incorrectly represent moving above the root directory. The problem explicitly states that this is not allowed.

The implementation handles this correctly by decrementing depth only if depth > 0.

Only Current Directory Operations

Another edge case is when every operation is "./".

For example:

["./", "./", "./"]

These operations should not affect the directory depth at all. A buggy implementation might accidentally count them as movement operations.

The solution correctly ignores these operations entirely.

Alternating Between Child and Parent Directories

A sequence that repeatedly enters and exits folders can expose logic errors in state management.

For example:

["d1/", "../", "d2/", "../"]

The correct final answer is 0 because every child-folder move is balanced by a parent-folder move.

The implementation handles this naturally because depth increases and decreases symmetrically according to the navigation rules.