Remove Sub-Folders from the Filesystem — Problem & Solution
Remove Sub-Folders from the Filesystem solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Remove Sub-Folders from the Filesystem is a medium coding problem on arrays, strings and depth-first search, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Depth-First Search, Trie
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a list of distinct folder paths folder. Remove every folder that is a sub-folder of another folder in the list, and return the folders that remain sorted in lexicographic order (plain character-code order, in which '/' comes before every letter).
Folder x is a sub-folder of folder y when x starts with y followed by a '/'. For example "/a/b" is a sub-folder of "/a", but "/b" is not a sub-folder of "/a/b/c", and "/ab" is not a sub-folder of "/a".
A path is one or more segments, each a '/' followed by one or more lowercase letters.
Example 1
Input: folder = ["/kai","/kai/ro","/code/x","/code/x/y","/code/z"]
Output: ["/code/x","/code/z","/kai"]
Explanation: `"/kai/ro"` lives inside `"/kai"` and `"/code/x/y"` inside `"/code/x"`.
Example 2
Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Example 3
Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]
Explanation: `"/a/b/ca"` starts with `"/a/b/c"` but not with `"/a/b/c/"`.
Constraints
1 <= folder.length <= 4 * 10^42 <= folder[i].length <= 100folder[i] contains only lowercase letters and '/'folder[i] always starts with the character '/'each folder name is unique
Hints for Remove Sub-Folders from the Filesystem
Hint 1
After sorting, every sub-folder comes right after its parent (or after another sub-folder of the same parent).
Hint 2
So walk the sorted list and remember the last folder you kept.
Hint 3
A folder is a sub-folder exactly when it starts with that kept folder plus
'/'— the slash stops"/ab"from matching"/a".
How to solve Remove Sub-Folders from the Filesystem
Sorting puts every folder's descendants directly after it, so one pass that compares each folder with the most recently kept one decides everything.
Approach
- Sort
folderlexicographically. - Walk the list; let
lastbe the most recently kept folder. - If the current folder starts with
last + '/', skip it; otherwise keep it and make it the newlast. - The kept folders are already in sorted order — return them.
Why it works
All strings with prefix y + '/' are contiguous in sorted order and come right after y (any string between y and them would have to share the prefix y too, and '/' sorts before every letter). A folder whose parent is in the list therefore meets a kept ancestor as last before any unrelated folder is kept; a top-level folder never starts with last + '/'.
Complexity
- Time —
O(n · L · log n) for the sort, whereLis the path length - Space —
O(n) for the output
Pitfalls
- Checking
startsWith(last)without the trailing'/'wrongly removes"/ab"after"/a". - Compare with the last kept folder, not the previous folder in the list.
- Sort by character code; a locale-aware sort can order
'/'differently.
Reference solution
Python
from typing import List
def removeSubfolders(folder: List[str]) -> List[str]:
res = []
for f in sorted(folder):
if res and f.startswith(res[-1] + "/"):
continue
res.append(f)
return resJava
public static String[] removeSubfolders(String[] folder) {
String[] sorted = folder.clone();
Arrays.sort(sorted);
List<String> res = new ArrayList<>();
for (String f : sorted) {
if (!res.isEmpty() && f.startsWith(res.get(res.size() - 1) + "/")) continue;
res.add(f);
}
return res.toArray(new String[0]);
}C++
vector<string> removeSubfolders(vector<string>& folder) {
vector<string> sorted = folder;
sort(sorted.begin(), sorted.end());
vector<string> res;
for (const string& f : sorted) {
if (!res.empty()) {
const string& last = res.back();
if (f.size() > last.size() && f.compare(0, last.size(), last) == 0 && f[last.size()] == '/') continue;
}
res.push_back(f);
}
return res;
}JavaScript
var removeSubfolders = function(folder) {
var sorted = folder.slice().sort();
var res = [];
for (var i = 0; i < sorted.length; i++) {
var f = sorted[i];
if (res.length) {
var last = res[res.length - 1] + "/";
if (f.substring(0, last.length) === last) continue;
}
res.push(f);
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.