How hard is LeetCode 1233. Remove Sub-Folders from the Filesystem?

LeetCode 1233. Remove Sub-Folders from the Filesystem is rated Medium on LeetCode.

What is the time complexity of LeetCode 1233. Remove Sub-Folders from the Filesystem?

The Python solution on this page runs in O(n \times \log n \times m).

What is the space complexity of LeetCode 1233. Remove Sub-Folders from the Filesystem?

The Python solution on this page uses O(m) auxiliary space.

What topics does LeetCode 1233. Remove Sub-Folders from the Filesystem cover?

LeetCode 1233. Remove Sub-Folders from the Filesystem is tagged Depth-First Search, Trie, Array and String on LeetCode.

Remove Sub-Folders from the Filesystem — LeetCode 1233 Python Solution

MediumDepth-First SearchTrieArrayString

Problem: #1233
Pattern: Trie
Reading time: 2 min
Source: leetcode.com

The problem

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.

Example

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.

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(n \times \log n \times m)
Space	O(m) auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 1233. Remove Sub-Folders from the Filesystem is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1233. Remove Sub-Folders from the Filesystem?: LeetCode 1233. Remove Sub-Folders from the Filesystem is rated Medium on LeetCode.
What is the time complexity of LeetCode 1233. Remove Sub-Folders from the Filesystem?: The Python solution on this page runs in O(n \times \log n \times m).
What is the space complexity of LeetCode 1233. Remove Sub-Folders from the Filesystem?: The Python solution on this page uses O(m) auxiliary space.
What topics does LeetCode 1233. Remove Sub-Folders from the Filesystem cover?: LeetCode 1233. Remove Sub-Folders from the Filesystem is tagged Depth-First Search, Trie, Array and String on LeetCode.