Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Lexicographical sorting puts a parent folder before its descendants and groups those descendants together. Once a parent is retained, every following descendant can be discarded by checking the last retained folder. The path separator is essential: /a is a parent of /a/b, but not of /ab.

Approach

Sort the paths and maintain a result list. Skip a path when it begins with the last retained path followed by /; otherwise append it. Skipped descendants never replace their parent, so deeper descendants are still tested against that parent. Return the retained paths, which contain no folder beneath another retained folder.

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

        for f in folder:
            if stack and f.startswith(stack[-1] + '/'):
                continue
            stack.append(f)

        return stack

Complexity analysis

Let N be the number of paths, P their maximum length, and L their total characters. Worst-case time is O(N log N * P + L) for lexicographic sorting and prefix checks. The result stores O(N) references to existing strings. Beyond that output, sorting may use O(N) workspace and constructing the last retained path plus / uses O(P) temporary string space, for an O(N + P) auxiliary-space bound. Since P <= 100 here, this is effectively O(N).