# 25.10.2024 [1233. Remove Sub-Folders from the Filesystem]

Remove empty subfolders #medium #trie #sort

25.10.2024

1233. Remove Sub-Folders from the Filesystem medium
blog post

youtube

deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/779

Problem TLDR

Remove empty subfolders #medium #trie #sort

Intuition

One way to do this in O(n) is to add everything into a Trie, mark the ends, then scan again and exclude path with more than one end.

Another way, is to sort paths, then naturally, every previous path will be parent of the next if it is a substring of it.

Approach

• Trie with keys of a string is faster in my tests then Trie with keys of individual chars (something with string optimizations)

• the fastest solution for this problem test cases is O(N(logN)), given the bigger constant of the Trie O(N) solution

Complexity

• Time complexity:
  𝑂(𝑛) for Trie, O(nlog(n)) for sort solution

• Space complexity:
  𝑂(𝑛)

Code

    fun removeSubfolders(folder: Array<String>) = buildList<String> {
        folder.sort()
        for (f in folder) if (size < 1 || !f.startsWith(last() + "/")) add(f)
    }

    pub fn remove_subfolders(mut folder: Vec<String>) -> Vec<String> {
        #[derive(Default)] struct Fs(u8, HashMap<String, Fs>);
        let (mut fs, mut res) = (Fs::default(), vec![]);
        for _ in 0..2 { for path in &folder {
            let mut r = &mut fs; let mut count = 0;
            for name in path.split('/').skip(1) {
                r = r.1.entry(name.into()).or_default();
                count += r.0
            }
            if r.0 == 1 && count == 1 { res.push(path.clone()) }
            r.0 = 1
        }}; res
    }

    vector<string> removeSubfolders(vector<string>& folder) {
        sort(begin(folder), end(folder)); vector<string> res;
        for (auto& f: folder) 
            if (!size(res) || f.find(res.back() + "/"))
                res.push_back(f);
        return res;
    }