Remove Sub-Folders from the Filesystem - Practice Coding Problems

Remove Sub-Folders from the Filesystem - Problem

Given a list of folders, 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.

Input & Output

Example 1 — Basic Case

$ Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]

› Output: ["/a","/c/d","/c/f"]

💡 Note: "/a/b" is a subfolder of "/a" and "/c/d/e" is a subfolder of "/c/d", so they are removed

Example 2 — No Subfolders

$ Input: folder = ["/a","/b","/c"]

› Output: ["/a","/b","/c"]

💡 Note: No folder is a subfolder of another, so all folders are kept

Example 3 — Deep Nesting

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

› Output: ["/a"]

💡 Note: Both "/a/b/c" and "/a/b/d" are subfolders of "/a", so only "/a" remains

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

Visualization

Tap to expand

Understanding the Visualization

Input

List of folder paths with some subfolders

Identify Subfolders

Find folders that are contained within others

Output

Return only the parent folders

Key Takeaway

🎯 Key Insight: Sorting folders alphabetically ensures parent folders appear before their subfolders, enabling efficient O(n log n) detection

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is to sort folders alphabetically so parent folders appear before their subfolders. This allows us to check only against the last added folder instead of all folders. Best approach is sort first with Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Pairs	O(n² × m)	O(1)	Compare every folder with every other folder to detect sub-folder relationships
Sort First - Efficient Detection	O(n log n + n × m)	O(n)	Sort folders alphabetically so parent folders come before their subfolders

Brute Force - Check All Pairs — Algorithm Steps

Iterate through each folder
For each folder, check against all other folders
If current folder is a sub-folder of another, mark it for removal
Return folders that aren't sub-folders

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare Each Pair

Check if one folder is a subfolder of another

Prefix Matching

Use string prefix matching with '/' separator

Filter Results

Keep only folders that aren't subfolders

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    char folders[1000][100];
    int count = 0;
    
    // Parse JSON array manually
    char* token = strtok(line + 1, ",");
    while (token != NULL && count < 1000) {
        // Remove quotes and spaces
        while (*token == ' ' || *token == '"') token++;
        int len = strlen(token);
        while (len > 0 && (token[len-1] == ' ' || token[len-1] == '"' || token[len-1] == ']')) {
            token[len-1] = 0;
            len--;
        }
        strcpy(folders[count], token);
        count++;
        token = strtok(NULL, ",");
    }
    
    char result[1000][100];
    int resultCount = 0;
    
    for (int i = 0; i < count; i++) {
        int isSubfolder = 0;
        for (int j = 0; j < count; j++) {
            if (i != j) {
                char temp[200];
                strcpy(temp, folders[j]);
                strcat(temp, "/");
                if (strncmp(folders[i], temp, strlen(temp)) == 0) {
                    isSubfolder = 1;
                    break;
                }
            }
        }
        if (!isSubfolder) {
            strcpy(result[resultCount], folders[i]);
            resultCount++;
        }
    }
    
    printf("[");
    for (int i = 0; i < resultCount; i++) {
        printf("\"%s\"", result[i]);
        if (i < resultCount - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × m)

Nested loops over n folders, each string comparison takes O(m) time where m is average path length

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for iteration, no extra data structures

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler