Remove Sub-Folders from the Filesystem

MEDIUM

Description

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 * 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.

Approaches

Checkout 3 different approaches to solve Remove Sub-Folders from the Filesystem. Click on different approaches to view the approach and algorithm in detail.

Brute Force Comparison

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.

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 Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Remove Sub-Folders from the Filesystem. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Remove Sub-Folders from the Filesystem

Algorithms:

Depth-First Search

Data Structures:

ArrayStringTrie

Companies:

Snowflake |Verkada |