Is Remove Sub-Folders from the Filesystem easy or hard?

The problem is rated Medium because the key insight involves recognizing how lexicographic sorting groups parent folders with their subfolders. Once that observation is made, the implementation becomes straightforward.

Remove Sub-Folders from the Filesystem Python/Java solution

Python, Java, C++, and JavaScript implementations usually follow the same strategy: sort the folder list, iterate through it, and skip paths that start with the previous kept folder plus '/'. Trie implementations are also possible in Python and C++ for demonstrating hierarchical parsing.

How to solve Remove Sub-Folders from the Filesystem in O(n)?

Strict O(n) relative to the number of folders is difficult because sorting is typically required. However, a Trie-based approach processes each character of every path once, giving O(T) complexity where T is the total length of all paths. This effectively behaves like linear time with respect to input size.

What is the best approach for Remove Sub-Folders from the Filesystem?

The sorting and prefix-check approach is considered the best practical solution. Sort the folder paths lexicographically and keep a folder only if it is not prefixed by the previously accepted folder plus '/'. This reduces the problem to a single pass after sorting and runs in O(n log n) time.

Is Remove Sub-Folders from the Filesystem asked at Google/Amazon/Meta?

Filesystem path problems and prefix filtering questions frequently appear in interviews at large companies such as Amazon, Google, and Meta. They test string manipulation, sorting strategies, and hierarchical data structures like tries.

What data structure is used in Remove Sub-Folders from the Filesystem?

The most common solution uses arrays and string prefix comparison after sorting the paths. Another approach uses a Trie to represent folder hierarchy, allowing efficient detection of parent folders during insertion.

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

The common optimal solution runs in O(n log n) time due to sorting the folder paths, followed by an O(n) scan to filter subfolders. A Trie-based approach can achieve O(T) time where T is the total number of characters across all folder paths.

Description Hints 2 Solution Video 19:29

1233. Remove Sub-Folders from the Filesystem

Medium78.6% acceptance8 companies

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.

If a folder[i] is located within another folder[j], it is called a sub-folder of it. A sub-folder of folder[j] must start with folder[j], followed by a "/". For example, "/a/b" is a sub-folder of "/a", but "/b" is not a sub-folder of "/a/b/c".

The format of a path is one or more concatenated strings of the form: '/' followed by one or more lowercase English letters.

For example, "/leetcode" and "/leetcode/problems" are valid paths while an empty string and "/" are not.

Example 1:

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.

Example 2:

Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: Folders "/a/b/c" and "/a/b/d" will be removed because they are subfolders of "/a".

Example 3:

Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]

Constraints:

1 <= folder.length <= 4 * 10⁴
2 <= folder[i].length <= 100
folder[i] contains only lowercase letters and '/'.
folder[i] always starts with the character '/'.
Each folder name is unique.

Asked at 8 companies

Verkada Snowflake Nuro

Google Amazon Meta Uber Microsoft

Topics

Hints open one at a time

Hint 1

Sort the folders lexicographically.

Hint 2

Insert the current element in an array and then loop until we get rid of all of their subfolders, repeat this until no element is left.

19:29

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def removeSubfolders(self, folder: List[str]) -> List[str]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

["/a","/a/b","/c/d","/c/d/e","/c/f"]

Input

["/a","/a/b/c","/a/b/d"]

Input

["/a/b/c","/a/b/ca","/a/b/d"]

Your code is saved on this device.Solution