Remove Sub-Folders from the Filesystem
Understanding the Problem
We have a list of absolute folder paths, and we need to filter out any folder that lives inside another folder from the same list. A folder /a/b is inside /a because the path /a followed by / is a prefix of /a/b. But /a/bc is not inside /a/b, even though /a/b is a string prefix of /a/bc. The / boundary is what distinguishes a real ancestor from an accidental string prefix.
So the question reduces to: for each folder, does any other folder in the list act as its ancestor? If yes, drop it. If no, keep it.
A naive pairwise check works but is slow. We can do better by exploiting the structure of sorted strings or by using a trie.
Key Constraints:
1 <= folder.length <= 4 * 10^4→ With n up to 40,000 folders, an O(n^2) brute force checking every pair would be about 1.6 billion operations in the worst case. That's too slow. We need O(n log n) or O(n) approaches.2 <= folder[i].length <= 100→ Individual paths are short (max 100 characters). A single string comparison costs O(L) where L is at most 100, so the length term stays small.Each folder name is unique→ No two paths are identical, so the only relationship to detect is ancestor-descendant, never equality.
Approach 1: Brute Force (Check Every Pair)
Intuition
For each folder, scan every other folder in the list and check whether that other folder is an ancestor. If any folder in the list is an ancestor, skip the current folder. Otherwise, keep it.
To check whether folder A is an ancestor of folder B, two conditions must hold: B must start with A, and the character at position len(A) in B must be '/'. The second condition is what rules out false matches. Without it, /a/bc would be marked as a sub-folder of /a/b, since /a/bc does start with /a/b.
Algorithm
- Initialize an empty result list.
- For each folder
fin the input list: - Set a flag
isSubFolder = false. - For each other folder
otherin the list: - If
fstarts withotherANDfhas a'/'at positionlen(other), setisSubFolder = trueand break. - If
isSubFolderis still false, addfto the result. - Return the result list.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2 * L). For each of the n folders, we compare it against all other n folders. Each comparison involves a startsWith check that takes up to L characters, where L is the maximum path length (100).
- Space Complexity: O(n). We store the result list, which in the worst case contains all n folders.
The nested loop scans the entire list for every folder. If the folders were sorted first, parent paths would appear before their children, letting us compare each folder against only the most recent root instead of all of them.
Approach 2: Sorting + Prefix Check
Intuition
If you sort the folder paths lexicographically, every sub-folder appears immediately after its parent folder. For example, after sorting ["/a/b", "/a", "/c/d/e", "/c/d", "/c/f"], you get ["/a", "/a/b", "/c/d", "/c/d/e", "/c/f"], where /a/b sits right after /a and /c/d/e sits right after /c/d.
This means a single pass through the sorted list suffices. Keep track of the last folder added to the result. For each new folder, check whether it is a sub-folder of that last added folder. If yes, skip it. If no, it is a new root folder, so add it and update the tracker.
Comparing only against the last added root is enough because of how sorting orders descendants. If /a is a kept root, then any descendant /a/... sorts after /a and before any path that starts with a character greater than the part following /a. A descendant of /a cannot be separated from /a by an unrelated path, because such a path would have to be both greater than /a and less than /a/..., which is impossible: any string that is greater than /a but shares its /a prefix is itself a descendant of /a. So once a non-descendant appears, it becomes the new root, and every descendant of the previous root has already been consumed. The only candidate ancestor for the current folder is therefore the most recent root.
Algorithm
- Sort the folder array lexicographically.
- Add the first folder to the result (it can't be a sub-folder of anything since it's lexicographically smallest).
- For each subsequent folder, check if it starts with the last folder in the result followed by
'/'. - If it does, skip it (it's a sub-folder).
- If it doesn't, add it to the result (it's a new root folder).
- Return the result.
Visualization and Code
Loading animation...
- Time Complexity: O(n L log n). Sorting n strings of length up to L takes O(n L log n). The subsequent single pass takes O(n * L) for the prefix checks. Sorting dominates.
- Space Complexity: O(n). The result list stores up to n folders.
The sorting approach is efficient, but the sort itself costs O(n L log n). Building a tree directly from the path components removes the sort and brings the running time down to linear.
Approach 3: Trie (Optimal)
Intuition
A trie (prefix tree) maps directly onto prefix relationships, and folder paths are a hierarchy of prefixes. Split each folder path by "/" into its components, then insert those components into a trie. Mark the node where a complete folder path ends. After building the trie, collect paths by walking it with DFS, stopping the descent as soon as a node marked as an end-of-folder is reached. Any path below that node is a sub-folder and is skipped.
For example, inserting /a, /a/b, and /c/d: the path /a creates a node a under the root and marks it as an end. During DFS, reaching a (marked as end) collects /a and stops the descent, so the b node below it is never visited and /a/b is excluded.
This works because the path from the root to any node spells out a prefix shared by every path passing through that node. A node marked as an end-of-folder corresponds to a folder in the list, and every node below it represents a path that has that folder as an ancestor. Stopping the DFS at the first marked node on each branch keeps each top-level folder once and discards everything beneath it, which is exactly the sub-folder filter.
Algorithm
- Build a trie where each node represents a path component (not individual characters).
- For each folder, split by
"/"and insert the components into the trie. Mark the final node as an end-of-folder. - Perform a DFS on the trie. When you reach a node marked as end-of-folder, add the current path to the result and do NOT recurse deeper (children are sub-folders).
- Return the collected result.
Visualization and Code
Loading animation...
- Time Complexity: O(n L). Building the trie requires inserting n paths, each of length up to L. The DFS visits each trie node at most once. Both phases are O(n L).
- Space Complexity: O(n L). The trie stores up to n L nodes in the worst case (when no paths share common prefixes). In practice, shared prefixes reduce this significantly.