# Remove Sub-Folders from the Filesystem
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/remove-sub-folders-from-the-filesystem)
Canonical: https://scaleengineer.com/dsa/problems/remove-sub-folders-from-the-filesystem
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, String, Trie
**Companies:** [Snowflake](https://scaleengineer.com/companies/snowflake), [Verkada](https://scaleengineer.com/companies/verkada)
---
## Problem
Given a list of folders `folder`, return _the folders after removing all **sub-folders** in those folders_. You may return the answer in **any order**.

If a `folder[i]` is located within another `folder[j]`, it is called a **sub-folder** of it. A sub-folder of `folder[j]` must start with `folder[j]`, followed by a `"/"`. For example, `"/a/b"` is a sub-folder of `"/a"`, but `"/b"` is not a sub-folder of `"/a/b/c"`.

The format of a path is one or more concatenated strings of the form: `'/'` followed by one or more lowercase English letters.

* For example, `"/leetcode"` and `"/leetcode/problems"` are valid paths while an empty string and `"/"` are not.

**Example 1:**

**Input:** folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
**Output:** ["/a","/c/d","/c/f"]
**Explanation:** Folders "/a/b" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.

**Example 2:**

**Input:** folder = ["/a","/a/b/c","/a/b/d"]
**Output:** ["/a"]
**Explanation:** Folders "/a/b/c" and "/a/b/d" will be removed because they are subfolders of "/a".

**Example 3:**

**Input:** folder = ["/a/b/c","/a/b/ca","/a/b/d"]
**Output:** ["/a/b/c","/a/b/ca","/a/b/d"]

**Constraints:**

* `1 <= folder.length <= 4 * 104`
* `2 <= folder[i].length <= 100`
* `folder[i]` contains only lowercase letters and `'/'`.
* `folder[i]` always starts with the character `'/'`.
* Each folder name is **unique**.

# Approaches
## Brute Force Comparison
This approach uses nested loops to compare every folder path against every other folder path. For each pair of folders, it checks if one is a sub-folder of the other. A boolean array is used to mark folders that are identified as sub-folders. Finally, it collects all folders that were not marked.
**Time:** O(N^2 * L), where N is the number of folders and L is the maximum length of a folder path. The nested loops give a factor of N^2, and the `startsWith` string operation takes O(L) time. · **Space:** O(N * L), where N is the number of folders and L is the maximum length of a folder path. The boolean array takes O(N) space. The result list can store up to N folders, each of length up to L, resulting in O(N * L) space in the worst case.
**Pros:** Simple to understand and implement without requiring complex data structures.
**Cons:** Highly inefficient due to the O(N^2) complexity, which will likely result in a 'Time Limit Exceeded' error for large inputs.
### Explanation
The brute-force method is the most straightforward way to solve the problem. We take each folder and compare it with all other folders in the list. To check if `folderA` is a sub-folder of `folderB`, we verify if the string `folderA` starts with the string `folderB` immediately followed by a forward slash `'/'`. We use an auxiliary boolean array, `isSubfolder`, to keep track of which folders need to be removed. If we find that `folder[i]` is a sub-folder of `folder[j]`, we set `isSubfolder[i]` to `true` and can stop checking `folder[i]` against other folders. After all comparisons are done, we construct our final list by including only those folders for which the corresponding `isSubfolder` flag is `false`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> removeSubfolders(String[] folder) {
        int n = folder.length;
        boolean[] isSubfolder = new boolean[n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                
                // Check if folder[i] is a subfolder of folder[j]
                if (folder[i].startsWith(folder[j] + "/")) {
                    isSubfolder[i] = true;
                    break; // Found its parent, no need to check further
                }
            }
        }
        
        List<String> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!isSubfolder[i]) {
                result.add(folder[i]);
            }
        }
        
        return result;
    }
}
```
### Algorithm
- Create a boolean array `isSubfolder` of the same size as the input `folder` array, initialized to `false`.
- Iterate through the `folder` array with an outer loop (index `i`).
- Iterate through the `folder` array with an inner loop (index `j`).
- If `i` and `j` are the same, skip the comparison.
- Check if `folder[i]` is a sub-folder of `folder[j]`. A folder is a sub-folder if its path starts with the other folder's path followed by a `/`. This can be checked using `folder[i].startsWith(folder[j] + "/")`.
- If it is a sub-folder, mark `isSubfolder[i]` as `true` and break the inner loop, as we've confirmed `folder[i]` should be removed.
- After the loops complete, iterate through the `isSubfolder` array.
- If `isSubfolder[k]` is `false`, it means `folder[k]` is not a sub-folder of any other folder, so add it to the result list.
- Return the result list.

## Sorting and Linear Scan
A more efficient approach is to first sort the folder paths lexicographically. After sorting, any sub-folder will appear immediately after its parent folder. This allows us to iterate through the sorted list just once to identify and filter out the sub-folders.
**Time:** O(N * L * log N), where N is the number of folders and L is the average length of a folder path. The sorting of N strings, where each comparison takes O(L), dominates the time complexity. · **Space:** O(N * L), where N is the number of folders and L is the maximum length of a folder path. The space required by the sorting algorithm can be up to O(N) or O(log N) depending on implementation. The result list can take up to O(N * L) space.
**Pros:** Significantly faster than the brute-force approach.; Easy to implement using built-in sorting functions.; Good balance between performance and implementation complexity.
**Cons:** The time complexity is dominated by the sorting step, which is not as optimal as the Trie-based approach.
### Explanation
The key insight for this approach is that sorting the folder paths alphabetically groups related paths together. For instance, `/a`, `/a/b`, and `/a/c` will be adjacent after sorting. This means we can identify sub-folders with a single linear scan over the sorted array.

First, we sort the input array `folder`. Then, we create a result list and add the very first folder, `folder[0]`, as it cannot be a sub-folder of anything that came before it. We then iterate from the second folder onwards. For each folder, we check if it's a sub-folder of the *last* folder we added to our result list. If `currentFolder` starts with `lastAddedFolder + "/"`, it's a sub-folder and we ignore it. Otherwise, it's a new, distinct parent folder, so we add it to our result list and it becomes the new reference for comparison.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<String> removeSubfolders(String[] folder) {
        if (folder == null || folder.length == 0) {
            return new ArrayList<>();
        }
        
        // Sort the folder paths lexicographically
        Arrays.sort(folder);
        
        List<String> result = new ArrayList<>();
        // The first folder is always a root folder in the sorted list
        result.add(folder[0]);
        
        String parent = folder[0];
        
        for (int i = 1; i < folder.length; i++) {
            String current = folder[i];
            // Check if the current folder is a subfolder of the last added parent
            if (!current.startsWith(parent + "/")) {
                result.add(current);
                parent = current;
            }
        }
        
        return result;
    }
}
```
### Algorithm
- Sort the input `folder` array lexicographically. This places parent folders directly before their sub-folders in the sorted list (e.g., `/a` comes before `/a/b`).
- Initialize an empty list `result` and add the first folder from the sorted array, `folder[0]`, to it. This folder is guaranteed to be a top-level folder in the context of the sorted list.
- Iterate through the sorted `folder` array starting from the second element (`i = 1`).
- For each `folder[i]`, compare it with the last folder added to the `result` list, let's call it `parent`.
- Check if `folder[i]` is a sub-folder of `parent` by testing if `folder[i].startsWith(parent + "/")`.
- If it is not a sub-folder, then `folder[i]` is a new top-level folder. Add it to the `result` list and update `parent` to be `folder[i]`.
- If it is a sub-folder, do nothing and proceed to the next folder in the sorted array.
- After the loop finishes, return the `result` list.

## Using a Trie (Prefix Tree)
The most optimal approach utilizes a Trie (Prefix Tree), a data structure well-suited for problems involving string prefixes. We insert all folder paths into the Trie. Each node in the Trie represents a directory name in the path. After building the Trie, we traverse it to collect the paths. The key is that once we find a node that marks the end of a folder, we add it to our results and do not explore its children, as they would all be sub-folders.
**Time:** O(N * L), where N is the number of folders and L is the maximum length of a folder path. Building the Trie involves processing each character of each folder path once, which takes O(N * L). The subsequent DFS traversal also visits each node at most once, which is also bounded by O(N * L). · **Space:** O(N * L), where N is the number of folders and L is the maximum length of a folder path. The space is used to store the Trie. In the worst-case scenario (no shared prefixes), the number of nodes in the Trie is proportional to the total number of characters across all folder paths.
**Pros:** Most efficient time complexity at O(N * L).; Provides a very clean and logical solution for prefix-based problems.
**Cons:** Requires implementing a custom Trie data structure, which is more complex than the sorting approach.; Can have a higher space overhead compared to the sorting approach if paths have few common prefixes.
### Explanation
This approach leverages a Trie to efficiently store and check for prefix relationships between folder paths. We build a Trie where each node represents a directory in a path. For a path like `/a/b`, we would split it into components `"a"` and `"b"`. We then traverse the Trie, starting from the root, creating nodes for `"a"` and then `"b"`.

We augment the `TrieNode` to hold the complete path string. This field is set only on the node that represents the end of a valid folder path from the input list. After inserting all folders into the Trie, we perform a traversal (e.g., DFS). When the traversal reaches a node that has a non-null path string, we've found a parent folder. We add this path to our result list and immediately stop descending further down that branch. This pruning step is what makes the algorithm efficient, as it automatically discards all sub-folders.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    class TrieNode {
        Map<String, TrieNode> children = new HashMap<>();
        String path = null; // Store the full path if this node is an end of a folder
    }

    public List<String> removeSubfolders(String[] folder) {
        TrieNode root = new TrieNode();
        
        // 1. Build the Trie
        for (String path : folder) {
            TrieNode current = root;
            // path.substring(1) to ignore the leading '/'
            String[] components = path.substring(1).split("/");
            for (String component : components) {
                current.children.putIfAbsent(component, new TrieNode());
                current = current.children.get(component);
            }
            current.path = path;
        }
        
        // 2. Traverse the Trie with DFS to find parent folders
        List<String> result = new ArrayList<>();
        dfs(root, result);
        return result;
    }
    
    private void dfs(TrieNode node, List<String> result) {
        if (node == null) {
            return;
        }
        
        // If this node represents a complete folder path
        if (node.path != null) {
            result.add(node.path);
            // Don't explore children, as they are subfolders
            return; 
        }
        
        // If not a complete folder, explore its children
        for (TrieNode child : node.children.values()) {
            dfs(child, result);
        }
    }
}
```
### Algorithm
- Define a `TrieNode` class. Each node should contain a map to its children (e.g., `Map<String, TrieNode>`) and a field to store the full path if the node represents the end of a folder (e.g., `String path`).
- Create a root `TrieNode`.
- Iterate through each `folderPath` in the input array:
  - Split the path by `/` to get its components.
  - Traverse the Trie from the root, creating new nodes for components as needed.
  - When the end of the path is reached, store the full `folderPath` in the `path` field of the final node.
- Initialize an empty `result` list.
- Perform a Depth-First Search (DFS) or Breadth-First Search (BFS) on the Trie starting from the root.
- During the traversal, if a node is encountered where its `path` field is not null, it signifies a valid, non-sub-folder path. Add this path to the `result` list.
- Crucially, do not traverse to the children of such a node, as any paths they represent would be sub-folders.
- If a node's `path` field is null, continue the traversal to its children.
- Return the `result` list.

# Solutions
### Java

```java
class Solution {
public
  List<String> removeSubfolders(String[] folder) {
    Arrays.sort(folder);
    List<String> ans = new ArrayList<>();
    ans.add(folder[0]);
    for (int i = 1; i < folder.length; ++i) {
      int m = ans.get(ans.size() - 1).length();
      int n = folder[i].length();
      if (m >= n ||
          !(ans.get(ans.size() - 1).equals(folder[i].substring(0, m)) &&
            folder[i].charAt(m) == '/')) {
        ans.add(folder[i]);
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
function removeSubfolders ( folder ) { let s = folder [ 1 ]; return folder . sort (). filter ( x => ! x . startsWith ( s + ' / ' ) && ( s = x )); }
```

### CPP

```cpp
class Solution {
public:
  vector<string> removeSubfolders(vector<string> &folder) {
    sort(folder.begin(), folder.end());
    vector<string> ans = {folder[0]};
    for (int i = 1; i < folder.size(); ++i) {
      int m = ans.back().size();
      int n = folder[i].size();
      if (m >= n ||
          !(ans.back() == folder[i].substr(0, m) && folder[i][m] == '/')) {
        ans.emplace_back(folder[i]);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]: folder . sort() ans = [folder[0]] for f in folder[1:]: m, n = len(ans[- 1]), len(f) if m >= n or not (ans[- 1] == f[: m] and f[m] == '/'): ans . append(f) return ans

```