Domain 2MediumMEDIUM

Remove Sub-Folders from the Filesystem

Sort folders lexicographically to process parents before children; iterate and keep only those that do not start with the last kept folder followed by a slash.

Domain: medium•Updated: 2026-09-10
#sorting#string manipulation#O(N log N)#O(1) auxiliary

Problem Breakdown

We are given an array of file system paths (strings starting with /). The goal is to remove any path that is strictly inside another path in the list (a sub-folder). A folder A is a sub-folder of B if and only if B appears as a prefix followed by exactly one slash (/) before the rest of A. For example, /a/b/c is a sub-folder of /a, but not of /ab.

Inputs:

  • A list of strings folder. Each string starts with /.
  • Constraints: 1≤folder.length≤40,0001 \le folder.length \le 40,000, length ≤100\le 100. Unique names.

Outputs:

  • A filtered list containing only the “root” folders (parents), excluding their descendants. Order does not matter for output but sorting helps processing logic.

Intuition

A brute-force approach comparing every pair of folders would be O(N2)O(N^2), which will exceed time limits given N=40,000N=40,000.

Key Insight: If we sort the list lexicographically (ASCII order), parent paths always appear before their children. For instance, /a comes before /a/b, and /a/b comes before /c/d. Once a folder is added to our result set (meaning it’s not inside any previously kept folder in the sorted sequence), all subsequent folders that start with kept_folder + '/' must be its sub-folders. Any folder that does not match this prefix pattern belongs to a different branch or is unrelated, so we keep it as a new root for our result set and update our reference point.

Approach

  1. Sort the input list lexicographically using folder.sort(). This groups parents before children (e.g., /a then /a/b).
  2. Initialize an empty result list to store valid folders.
  3. Iterate through each folder in the sorted list:
    • If the result list is empty, add the current folder immediately.
    • Otherwise, check if the current folder starts with the string of the last added folder followed by a slash (/).
    • If it does match (e.g., last was /a, current is /ab -> No; last was /a, current is /abc -> Yes), skip it as it’s a sub-folder. Note: The check must be startswith(last + "/"). This distinguishes between /a and /ab.
    • If it does not match, add the folder to result. It becomes the new reference for checking subsequent folders in this branch of the tree.
  4. Return result.

Complexity Analysis

  • Time: O(Nlog⁡N⋅L)O(N \log N \cdot L) where NN is number of folders and LL is max string length (for sorting). The iteration takes O(N⋅L)O(N \cdot L). Sorting dominates, fitting well within time limits for 40k items.
  • Space: Python’s list.sort() uses Timsort which requires auxiliary space proportional to the input size in worst-case scenarios (O(N)O(N)), though often optimized. Excluding this and output storage, logic is O(1)O(1). The result list takes O(K)O(K) where K is number of kept folders (worst case NN).

Solution

from typing import List

def remove_sub_folders(folder: List[str]) -> List[str]:
    # Sort lexicographically so parents appear before children
    folder.sort()
    
    result = []
    
    for f in folder:
        if not result or not (f.startswith(result[-1] + "/")):
            result.append(f)
            
    return result

# Example usage / verification logic inside thought process, 
# but function is clean and idiomatic.

Edge Cases Handled

  • Single Folder: Loop runs once, condition not result triggers immediately; returns list with that folder.
  • Non-Matching Prefixes (e.g., /a/b vs /ab/c): String sort places them in order (/a... then /b...). The check startswith(result[-1] + "/") ensures strict path hierarchy matching, preventing false positives like treating /ab as a parent of /abc.
  • Deeply Nested Structures: Sorting guarantees that if we keep the root (e.g., /root/child/grandchild), any subsequent folder starting with ...grandchild/ is skipped. If an unrelated path appears later, it won’t match the prefix and gets added correctly.