Remove Sub-Folders from the Filesystem - Leetcode 1233 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
6:07 - Coding Explanation
8:42 - Drawing Explanation
14:19 - Coding Explanation

leetcode 1233

#neetcode #leetcode #python

[AlfredPros]

My no-brainer solution is by sorting the input list by its length since subfolder will always be longer than its root. Then add to a hashset if not exists for each of its subfolders.

def removeSubfolders(self, folder: List[str]) -> List[str]:
roots = set()
folder.sort(key=len)

for i in folder:
temp = i[1:].split("/")
string = ""
found = False
for temp_str in temp:
string += "/" + temp_str
if string in roots:
found = True
break
if found == False:
roots.add(string)

return list(roots)

Adding early stop on the check loop helps the performance a little. On my end, the runtime is 40ms. This is not the optimal solution, but it works.

[greedyfishbones]

homie, the fire nation has attacked with a hard problem, the world needs the avatar. come back for today's daily 🥺

[mmuzzammil]

Im not gonna watch the video until I attempt it myself ;) but I just came to check if you uploaded it and god damn! haha Neetcode is on top of it!

[dekumidoriya-qiis]

another way is to sort the folder and then check while inserting in the trie if the path already exists, it it exists return False else add the path to trie and return True
it improves both time and space

[jamestwosheep]

Thanks for the great explanation for both approaches! One thing I could suggest for improving the Trie approach is after creating the the full Trie structure, dfs through it with an accumulating path array, and each time a node is found where end_of_folder is true, push the current path (as a string) to a result list, and then backtrack. That way you could potentially cut down on repeated work from that prefix_search method.

[nihalbhandary]

You can find if a dir is subdir when adding to the Trie and break out of it. In the end just add all the strings in the trie.

[realisticlevel]

I was able to use a Trie and perform pruning as I was adding folderPaths to the Trie.

[floriankubiak]

Probably the worst designed problem, the description is of an alternate universe's logic.

[pseudounknow]

Very easy solution
23ms

Beats95.00%


class Solution:

def removeSubfolders(self, folder: List[str]) -> List[str]:

# Sort folders lexicographically
folder.sort()
result = []

for f in folder:
# Check if f is a sub-folder of the last added folder
if not result or not f.startswith(result[-1] + '/'):
result.append(f)

return result

[OwenWu-ft]

I was doing this question and got memory limit exceeded and then also time limit exceeded 28/34:

class Solution:
def removeSubfolders(self, folder: List[str]) -> List[str]:
d = defaultdict(list)
for f in folder:
for a in folder:
if a != f:
d[f].append(a)
for k in d:
for a in set(d[k]):
if a.startswith(k + "/"):
if a in folder:
folder.remove(a)
return folder

[pranayramayanapu]

class Solution {
public:
bool substr(string st1, string st2) {
if(st1.length() > st2.length()) return false;
for(int i = 0; i < st1.length(); i++) {
if(st1[i] != st2[i]) return false;
}
if(st2.size() > st1.size() && st2[st1.size()] != '/') return false;
return true;
}

vector<string> folder) {
sort(folder.begin(), folder.end());
vector<string> sol;


if(folder.empty()) return sol;

for(int i = 0; i < folder.size()-1; i++) {
int j = i;
while(i < folder.size()-1 && substr(folder[j], folder[i+1])) {
i++;
}
sol.push_back(folder[j]);
}


if(sol.empty() || !substr(sol.back(), folder.back())) {

}

return sol;
}
};



so i did this which beat 95% in c++

[manoowranjith.a.j]

Simple Hashmap solution :

var removeSubfolders = function (folder) {
let output = []
let map = {}
for (let i = 0; i < folder.length; i++) {
map[folder[i]] = true
}
for (let i = 0; i < folder.length; i++) {
let eachFolder =
let subFolder = ""
let count = 0
for (let k = 0; k < eachFolder.length; k++) {
subFolder += '/' + eachFolder[k]
if (map[subFolder]) {
count++
}
}
if (count == 1) {
output.push(folder[i])
}
}
return output
};

[LonelyElectron]

I tried so hard but got so far, in the end it doesn’t even matter

[subhasisrout]

Would the first solution work if sequence of "/c/d", "/c/d/e" is reversed ? It is not mentioned in the question that order of input would be such that parent folder would come before the child folder.

[Cdaprod]

Let’s see how many people end up wiping their filesystems down to root after this 😂