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.

Examples

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

Solution

Method 1 - Using Stack

We can use a stack to simulate the file system navigation process, when we see

  • directory, we push it to the stack
  • “./”, we just continue
  • “../”, we pop from the stack (moves one directory up if possible),

Finally, return the size of the stack to get the minimum number of operations needed to return to the main folder.

Code

Java
class Solution {
    public int minOperations(String[] logs) {
         var stack = new Stack<String>();
        for(var log : logs){
            if(log.equals("../")){
                if(!stack.empty()) {
	                stack.pop();
                }
            }else if(log.equals("./")){
				continue;
            }else{
                stack.push(log);
            }
        }
        return stack.size();
    }
}

Complexity

  • ⏰ Time complexity: O(n) where n is length of logs array
  • 🧺 Space complexity: O(n)

Method 2 - Using depth counter

Here are the steps we can follow:

  • Initialize Depth: Start with depth set to 0.
  • Iterate through Logs: Loop through each log entry in the logs array. Every time, we see
    • normal directory path ⇨ we increase depth
    • "../" ⇨ we decrease depth
    • "./" ⇨ we do nothing
  • Return Depth: The depth indicates the minimum number of operations needed to return to the main folder.

Here is the video explanation explaining the same:

Code

Java
class Solution {
    public int minOperations(String[] logs) {
        int depth = 0;
        for (String s : logs) {
            if (s.equals("../")) {
	            depth = Math.max(0, --depth);
	        }
            else if (s.equals("./")) {
	            continue;
	        }
            else {
	            depth++;
	        }
        }
        return depth;
    }
}

Complexity

  • ⏰ Time complexity: O(n) where n is length of logs array
  • 🧺 Space complexity: O(1)