Remove Sub-Folders from the Filesystem

Medium
1751.

Remove Sub-Folders from the Filesystem

Remove Sub-Folders from the Filesystem is a medium coding problem on arrays, strings and depth-first search, asked in Amazon, Google and Meta interviews.

You are given a list of distinct folder paths folder. Remove every folder that is a sub-folder of another folder in the list, and return the folders that remain sorted in lexicographic order (plain character-code order, in which '/' comes before every letter).

Folder x is a sub-folder of folder y when x starts with y followed by a '/'. For example "/a/b" is a sub-folder of "/a", but "/b" is not a sub-folder of "/a/b/c", and "/ab" is not a sub-folder of "/a".

A path is one or more segments, each a '/' followed by one or more lowercase letters.

Example 1

Input
folder = ["/kai","/kai/ro","/code/x","/code/x/y","/code/z"]
Output
["/code/x","/code/z","/kai"]
Explanation
`"/kai/ro"` lives inside `"/kai"` and `"/code/x/y"` inside `"/code/x"`.

Example 2

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

Example 3

Input
folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output
["/a/b/c","/a/b/ca","/a/b/d"]
Explanation
`"/a/b/ca"` starts with `"/a/b/c"` but not with `"/a/b/c/"`.

Constraints

  • 1 <= folder.length <= 4 * 10^4
  • 2 <= folder[i].length <= 100
  • folder[i] contains only lowercase letters and '/'
  • folder[i] always starts with the character '/'
  • each folder name is unique
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} folder
 * @return {string[]}
 */
var removeSubfolders = function(folder) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Remove Sub-Folders from the Filesystem — Problem & Solution

Remove Sub-Folders from the Filesystem solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Remove Sub-Folders from the Filesystem is a medium coding problem on arrays, strings and depth-first search, asked in Amazon, Google and Meta interviews.

Problem statement

You are given a list of distinct folder paths folder. Remove every folder that is a sub-folder of another folder in the list, and return the folders that remain sorted in lexicographic order (plain character-code order, in which '/' comes before every letter).

Folder x is a sub-folder of folder y when x starts with y followed by a '/'. For example "/a/b" is a sub-folder of "/a", but "/b" is not a sub-folder of "/a/b/c", and "/ab" is not a sub-folder of "/a".

A path is one or more segments, each a '/' followed by one or more lowercase letters.

Example 1

Input: folder = ["/kai","/kai/ro","/code/x","/code/x/y","/code/z"]
Output: ["/code/x","/code/z","/kai"]
Explanation: `"/kai/ro"` lives inside `"/kai"` and `"/code/x/y"` inside `"/code/x"`.

Example 2

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

Example 3

Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]
Explanation: `"/a/b/ca"` starts with `"/a/b/c"` but not with `"/a/b/c/"`.

Constraints

  • 1 <= folder.length <= 4 * 10^4
  • 2 <= folder[i].length <= 100
  • folder[i] contains only lowercase letters and '/'
  • folder[i] always starts with the character '/'
  • each folder name is unique

Hints for Remove Sub-Folders from the Filesystem

  1. Hint 1

    After sorting, every sub-folder comes right after its parent (or after another sub-folder of the same parent).

  2. Hint 2

    So walk the sorted list and remember the last folder you kept.

  3. Hint 3

    A folder is a sub-folder exactly when it starts with that kept folder plus '/' — the slash stops "/ab" from matching "/a".

How to solve Remove Sub-Folders from the Filesystem

Sorting puts every folder's descendants directly after it, so one pass that compares each folder with the most recently kept one decides everything.

Approach

  1. Sort folder lexicographically.
  2. Walk the list; let last be the most recently kept folder.
  3. If the current folder starts with last + '/', skip it; otherwise keep it and make it the new last.
  4. The kept folders are already in sorted order — return them.

Why it works

All strings with prefix y + '/' are contiguous in sorted order and come right after y (any string between y and them would have to share the prefix y too, and '/' sorts before every letter). A folder whose parent is in the list therefore meets a kept ancestor as last before any unrelated folder is kept; a top-level folder never starts with last + '/'.

Complexity

  • Time — O(n · L · log n) for the sort, where L is the path length
  • Space — O(n) for the output

Pitfalls

  • Checking startsWith(last) without the trailing '/' wrongly removes "/ab" after "/a".
  • Compare with the last kept folder, not the previous folder in the list.
  • Sort by character code; a locale-aware sort can order '/' differently.

Reference solution

Python

from typing import List

def removeSubfolders(folder: List[str]) -> List[str]:
    res = []
    for f in sorted(folder):
        if res and f.startswith(res[-1] + "/"):
            continue
        res.append(f)
    return res

Java

public static String[] removeSubfolders(String[] folder) {
    String[] sorted = folder.clone();
    Arrays.sort(sorted);
    List<String> res = new ArrayList<>();
    for (String f : sorted) {
        if (!res.isEmpty() && f.startsWith(res.get(res.size() - 1) + "/")) continue;
        res.add(f);
    }
    return res.toArray(new String[0]);
}

C++

vector<string> removeSubfolders(vector<string>& folder) {
    vector<string> sorted = folder;
    sort(sorted.begin(), sorted.end());
    vector<string> res;
    for (const string& f : sorted) {
        if (!res.empty()) {
            const string& last = res.back();
            if (f.size() > last.size() && f.compare(0, last.size(), last) == 0 && f[last.size()] == '/') continue;
        }
        res.push_back(f);
    }
    return res;
}

JavaScript

var removeSubfolders = function(folder) {
    var sorted = folder.slice().sort();
    var res = [];
    for (var i = 0; i < sorted.length; i++) {
        var f = sorted[i];
        if (res.length) {
            var last = res[res.length - 1] + "/";
            if (f.substring(0, last.length) === last) continue;
        }
        res.push(f);
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings