We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Remove Sub-Folders from the Filesystem

Difficulty: Medium

Problem Description

Given a list of folders, return the folders after removing all sub-folders in those folders. A folder is considered a sub-folder of another if it starts with the same path followed by a "/".

Key Insights

  • A folder is a sub-folder if it shares the same prefix as another folder followed by a "/".
  • Sorting the folders helps in easily identifying sub-folder relationships.
  • A data structure that can efficiently check prefixes is essential for solution implementation.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the folder paths, where n is the number of folders. The subsequent check for sub-folders is O(n). Space Complexity: O(n) to store the result of non-sub-folder paths.

Solution

To solve this problem, we can follow these steps:

  1. First, sort the list of folder paths. This allows sub-folders to appear immediately after their parent folders.
  2. Iterate through the sorted list and keep track of the last added folder. If the current folder starts with the last added folder plus "/", it is a sub-folder and should be skipped.
  3. If it is not a sub-folder, add it to the result list.

We utilize a list to store the unique folders and ensure that only non-sub-folder paths are included in the final result.

Code Solutions

def removeSubfolders(folder):
    # Sort the folders to ensure parent folders come before sub-folders
    folder.sort()
    result = []
    last_added = ""

    for f in folder:
        # Check if the current folder is a sub-folder of the last added folder
        if not f.startswith(last_added + "/"):
            result.append(f)
            last_added = f  # Update the last added folder

    return result
← Back to All Questions