Scale Engineer

Crawler Log Folder

Easy
#1469Time: 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.4 companies
Data structures
ArrayStringStack
Companies
AtlassianFlipkartZS AssociatesMercari

Prompt

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:

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

Example 2:

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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();    }}

Complexity

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.

Trade-offs

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.

Solutions

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 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem