Scale Engineer

Remove Sub-Folders from the Filesystem

Med
#1151Time: O(N^2 * L), where N is the number of folders and L is the maximum length of a folder path. The nested loops give a factor of N^2, and the `startsWith` string operation takes O(L) time.Space: O(N * L), where N is the number of folders and L is the maximum length of a folder path. The boolean array takes O(N) space. The result list can store up to N folders, each of length up to L, resulting in O(N * L) space in the worst case.2 companies
Algorithms
Depth-First Search
Data structures
ArrayStringTrie
Companies
SnowflakeVerkada

Prompt

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

 

Example 1:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: Folders "/a/b" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.

Example 2:

Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: Folders "/a/b/c" and "/a/b/d" will be removed because they are subfolders of "/a".

Example 3:

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

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses nested loops to compare every folder path against every other folder path. For each pair of folders, it checks if one is a sub-folder of the other. A boolean array is used to mark folders that are identified as sub-folders. Finally, it collects all folders that were not marked.

Algorithm

  • Create a boolean array isSubfolder of the same size as the input folder array, initialized to false.
  • Iterate through the folder array with an outer loop (index i).
  • Iterate through the folder array with an inner loop (index j).
  • If i and j are the same, skip the comparison.
  • Check if folder[i] is a sub-folder of folder[j]. A folder is a sub-folder if its path starts with the other folder's path followed by a /. This can be checked using folder[i].startsWith(folder[j] + "/").
  • If it is a sub-folder, mark isSubfolder[i] as true and break the inner loop, as we've confirmed folder[i] should be removed.
  • After the loops complete, iterate through the isSubfolder array.
  • If isSubfolder[k] is false, it means folder[k] is not a sub-folder of any other folder, so add it to the result list.
  • Return the result list.

Walkthrough

The brute-force method is the most straightforward way to solve the problem. We take each folder and compare it with all other folders in the list. To check if folderA is a sub-folder of folderB, we verify if the string folderA starts with the string folderB immediately followed by a forward slash '/'. We use an auxiliary boolean array, isSubfolder, to keep track of which folders need to be removed. If we find that folder[i] is a sub-folder of folder[j], we set isSubfolder[i] to true and can stop checking folder[i] against other folders. After all comparisons are done, we construct our final list by including only those folders for which the corresponding isSubfolder flag is false.

import java.util.ArrayList;import java.util.List; class Solution {    public List<String> removeSubfolders(String[] folder) {        int n = folder.length;        boolean[] isSubfolder = new boolean[n];                for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                if (i == j) continue;                                // Check if folder[i] is a subfolder of folder[j]                if (folder[i].startsWith(folder[j] + "/")) {                    isSubfolder[i] = true;                    break; // Found its parent, no need to check further                }            }        }                List<String> result = new ArrayList<>();        for (int i = 0; i < n; i++) {            if (!isSubfolder[i]) {                result.add(folder[i]);            }        }                return result;    }}

Complexity

Time

O(N^2 * L), where N is the number of folders and L is the maximum length of a folder path. The nested loops give a factor of N^2, and the `startsWith` string operation takes O(L) time.

Space

O(N * L), where N is the number of folders and L is the maximum length of a folder path. The boolean array takes O(N) space. The result list can store up to N folders, each of length up to L, resulting in O(N * L) space in the worst case.

Trade-offs

Pros

  • Simple to understand and implement without requiring complex data structures.

Cons

  • Highly inefficient due to the O(N^2) complexity, which will likely result in a 'Time Limit Exceeded' error for large inputs.

Solutions

class Solution {public  List<String> removeSubfolders(String[] folder) {    Arrays.sort(folder);    List<String> ans = new ArrayList<>();    ans.add(folder[0]);    for (int i = 1; i < folder.length; ++i) {      int m = ans.get(ans.size() - 1).length();      int n = folder[i].length();      if (m >= n ||          !(ans.get(ans.size() - 1).equals(folder[i].substring(0, m)) &&            folder[i].charAt(m) == '/')) {        ans.add(folder[i]);      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem