Remove Sub-Folders from the Filesystem

main.md

Question

Approach

I first sorted the list of folders in lexicographical order. This way, all potential parent folders come before their subfolders. Then, I iterated through the sorted list and maintained a result list. For each folder, I checked whether it starts with the last added folder in the result list followed by a /. If it does, that means it's a subfolder and should be skipped. Else, I added it to the result.

Implementation

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        result = []

        for path in folder:
            if not result or not path.startswith(result[-1] + "/"):
                result.append(path)
        
        return result

Complexities

• Time: O(n log n)
• Space: O(n)