Remove Sub-Folders from the Filesystem

Med

#1151Time: 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.2 companies

Algorithms

Depth-First Search

Data structures

Array String Trie

Companies

Snowflake Verkada

Prompt

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 * 10⁴
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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<String> removeSubfolders(String[] folder) {6        int n = folder.length;7        boolean[] isSubfolder = new boolean[n];8        9        for (int i = 0; i < n; i++) {10            for (int j = 0; j < n; j++) {11                if (i == j) continue;12                13                // Check if folder[i] is a subfolder of folder[j]14                if (folder[i].startsWith(folder[j] + "/")) {15                    isSubfolder[i] = true;16                    break; // Found its parent, no need to check further17                }18            }19        }20        21        List<String> result = new ArrayList<>();22        for (int i = 0; i < n; i++) {23            if (!isSubfolder[i]) {24                result.add(folder[i]);25            }26        }27        28        return result;29    }30}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4 5class Solution {6    public List<String> removeSubfolders(String[] folder) {7        if (folder == null || folder.length == 0) {8            return new ArrayList<>();9        }10        11        // Sort the folder paths lexicographically12        Arrays.sort(folder);13        14        List<String> result = new ArrayList<>();15        // The first folder is always a root folder in the sorted list16        result.add(folder[0]);17        18        String parent = folder[0];19        20        for (int i = 1; i < folder.length; i++) {21            String current = folder[i];22            // Check if the current folder is a subfolder of the last added parent23            if (!current.startsWith(parent + "/")) {24                result.add(current);25                parent = current;26            }27        }28        29        return result;30    }31}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.List;4import java.util.Map;5 6class Solution {7    class TrieNode {8        Map<String, TrieNode> children = new HashMap<>();9        String path = null; // Store the full path if this node is an end of a folder10    }11 12    public List<String> removeSubfolders(String[] folder) {13        TrieNode root = new TrieNode();14        15        // 1. Build the Trie16        for (String path : folder) {17            TrieNode current = root;18            // path.substring(1) to ignore the leading '/'19            String[] components = path.substring(1).split("/");20            for (String component : components) {21                current.children.putIfAbsent(component, new TrieNode());22                current = current.children.get(component);23            }24            current.path = path;25        }26        27        // 2. Traverse the Trie with DFS to find parent folders28        List<String> result = new ArrayList<>();29        dfs(root, result);30        return result;31    }32    33    private void dfs(TrieNode node, List<String> result) {34        if (node == null) {35            return;36        }37        38        // If this node represents a complete folder path39        if (node.path != null) {40            result.add(node.path);41            // Don't explore children, as they are subfolders42            return; 43        }44        45        // If not a complete folder, explore its children46        for (TrieNode child : node.children.values()) {47            dfs(child, result);48        }49    }50}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  List<String> removeSubfolders(String[] folder) {4    Arrays.sort(folder);5    List<String> ans = new ArrayList<>();6    ans.add(folder[0]);7    for (int i = 1; i < folder.length; ++i) {8      int m = ans.get(ans.size() - 1).length();9      int n = folder[i].length();10      if (m >= n ||11          !(ans.get(ans.size() - 1).equals(folder[i].substring(0, m)) &&12            folder[i].charAt(m) == '/')) {13        ans.add(folder[i]);14      }15    }16    return ans;17  }18}

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

1class Solution {2public:3  vector<string> removeSubfolders(vector<string> &folder) {4    sort(folder.begin(), folder.end());5    vector<string> ans = {folder[0]};6    for (int i = 1; i < folder.size(); ++i) {7      int m = ans.back().size();8      int n = folder[i].size();9      if (m >= n ||10          !(ans.back() == folder[i].substr(0, m) && folder[i][m] == '/')) {11        ans.emplace_back(folder[i]);12      }13    }14    return ans;15  }16};

1class Solution:2    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

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 problem

Solution

1class Solution {2public3  List<String> removeSubfolders(String[] folder) {4    Arrays.sort(folder);5    List<String> ans = new ArrayList<>();6    ans.add(folder[0]);7    for (int i = 1; i < folder.length; ++i) {8      int m = ans.get(ans.size() - 1).length();9      int n = folder[i].length();10      if (m >= n ||11          !(ans.get(ans.size() - 1).equals(folder[i].substring(0, m)) &&12            folder[i].charAt(m) == '/')) {13        ans.add(folder[i]);14      }15    }16    return ans;17  }18}

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

1class Solution {2public:3  vector<string> removeSubfolders(vector<string> &folder) {4    sort(folder.begin(), folder.end());5    vector<string> ans = {folder[0]};6    for (int i = 1; i < folder.size(); ++i) {7      int m = ans.back().size();8      int n = folder[i].size();9      if (m >= n ||10          !(ans.back() == folder[i].substr(0, m) && folder[i][m] == '/')) {11        ans.emplace_back(folder[i]);12      }13    }14    return ans;15  }16};

1class Solution:2    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

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.