# Delete Duplicate Folders in System **Difficulty:** HARD [External](https://leetcode.com/problems/delete-duplicate-folders-in-system) Canonical: https://scaleengineer.com/dsa/problems/delete-duplicate-folders-in-system **Patterns:** [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function) **Data structures:** Array, Hash Table, String, Trie **Companies:** [Nvidia](https://scaleengineer.com/companies/nvidia), [Booking.com](https://scaleengineer.com/companies/booking.com) --- ## Problem Due to a bug, there are many duplicate folders in a file system. You are given a 2D array `paths`, where `paths[i]` is an array representing an absolute path to the `ith` folder in the file system. * For example, `["one", "two", "three"]` represents the path `"/one/two/three"`. Two folders (not necessarily on the same level) are **identical** if they contain the **same non-empty** set of identical subfolders and underlying subfolder structure. The folders **do not** need to be at the root level to be identical. If two or more folders are **identical**, then **mark** the folders as well as all their subfolders. * For example, folders `"/a"` and `"/b"` in the file structure below are identical. They (as well as their subfolders) should **all** be marked: * `/a` * `/a/x` * `/a/x/y` * `/a/z` * `/b` * `/b/x` * `/b/x/y` * `/b/z` * However, if the file structure also included the path `"/b/w"`, then the folders `"/a"` and `"/b"` would not be identical. Note that `"/a/x"` and `"/b/x"` would still be considered identical even with the added folder. Once all the identical folders and their subfolders have been marked, the file system will **delete** all of them. The file system only runs the deletion once, so any folders that become identical after the initial deletion are not deleted. Return _the 2D array_ `ans` _containing the paths of the **remaining** folders after deleting all the marked folders. The paths may be returned in **any** order_. **Example 1:** ![](https://assets.glich.co/dsa/delete-duplicate-folders-in-system/image0.jpg) **Input:** paths = [["a"],["c"],["d"],["a","b"],["c","b"],["d","a"]] **Output:** [["d"],["d","a"]] **Explanation:** The file structure is as shown. Folders "/a" and "/c" (and their subfolders) are marked for deletion because they both contain an empty folder named "b". **Example 2:** ![](https://assets.glich.co/dsa/delete-duplicate-folders-in-system/image1.jpg) **Input:** paths = [["a"],["c"],["a","b"],["c","b"],["a","b","x"],["a","b","x","y"],["w"],["w","y"]] **Output:** [["c"],["c","b"],["a"],["a","b"]] **Explanation:** The file structure is as shown. Folders "/a/b/x" and "/w" (and their subfolders) are marked for deletion because they both contain an empty folder named "y". Note that folders "/a" and "/c" are identical after the deletion, but they are not deleted because they were not marked beforehand. **Example 3:** ![](https://assets.glich.co/dsa/delete-duplicate-folders-in-system/image2.jpg) **Input:** paths = [["a","b"],["c","d"],["c"],["a"]] **Output:** [["c"],["c","d"],["a"],["a","b"]] **Explanation:** All folders are unique in the file system. Note that the returned array can be in a different order as the order does not matter. **Constraints:** * `1 <= paths.length <= 2 * 104` * `1 <= paths[i].length <= 500` * `1 <= paths[i][j].length <= 10` * `1 <= sum(paths[i][j].length) <= 2 * 105` * `path[i][j]` consists of lowercase English letters. * No two paths lead to the same folder. * For any folder not at the root level, its parent folder will also be in the input. # Approaches ## Trie + String Serialization This approach uses a Trie to model the file system. It then performs a post-order traversal (DFS) to generate a canonical string representation for each folder's structure. These strings are used to count how many folders share the exact same structure. Folders with a structure count greater than one are marked for deletion. A final traversal collects the paths of all folders that are not marked. **Time:** O(S + L_structs), where `S` is the total number of characters in input paths and `L_structs` is the total length of all structure strings. The complexity is dominated by building and hashing these strings. In the worst case, this can be quadratic in the number of folders, e.g., O(T^2). · **Space:** O(S + L_structs), where `S` is the total number of characters in all folder names and `L_structs` is the total length of all generated structure strings. In the worst-case (a deep, chain-like file system), `L_structs` can be O(T^2), where `T` is the total number of folders, making space complexity a major issue. **Pros:** The approach is intuitive and directly models the recursive definition of folder duplication.; It correctly solves the problem for smaller inputs. **Cons:** The serialized structure strings can become very long for deep or wide folder structures, leading to high memory consumption.; String concatenation and hashing of long strings can be slow, potentially causing a 'Time Limit Exceeded' error on large test cases. ### Explanation The core idea is to convert the structure of each folder into a unique, comparable format—a string. 1. **Build a Trie**: First, we parse the input `paths` and build a Trie. The root of the Trie is a dummy node. Each node represents a folder and contains a map to its children. Using a `TreeMap` for children ensures that when we later serialize the structure, the children are always processed in alphabetical order, leading to a canonical representation. 2. **Serialize and Count Structures**: We define a recursive DFS function that performs a post-order traversal. For any given node, it first calls itself on all children to get their structure strings. Then, it constructs the current node's structure string by concatenating its children's names and their structure strings in alphabetical order. For example, `child1_name(child1_structure)child2_name(child2_structure)...`. We use a `HashMap` to store each unique structure string and count its occurrences. We only count structures of non-empty folders, as per the problem description. 3. **Collect Remaining Paths**: After all structure strings and their counts are computed, we perform another DFS traversal (pre-order) to build the final list of paths. When visiting a node, we check if its structure string has a count greater than 1 in our map. If it does, this folder and all its subfolders are considered deleted, so we prune this branch from our traversal. Otherwise, we add the current path to our results and continue exploring its children. ```java import java.util.*; class Solution { class TrieNode { String name; // Use TreeMap to keep children sorted alphabetically for canonical representation Map children = new TreeMap<>(); String structure = ""; // To store serialized structure } public List> deleteDuplicateFolder(List> paths) { TrieNode root = new TrieNode(); // 1. Build the Trie for (List path : paths) { TrieNode curr = root; for (String folder : path) { curr = curr.children.computeIfAbsent(folder, k -> { TrieNode newNode = new TrieNode(); newNode.name = k; return newNode; }); } } // 2. Post-order traversal to compute structure strings and their counts Map structureCounts = new HashMap<>(); computeStructure(root, structureCounts); // 3. Pre-order traversal to collect non-deleted paths List> result = new ArrayList<>(); for (TrieNode child : root.children.values()) { collectPaths(child, new ArrayList<>(), result, structureCounts); } return result; } private String computeStructure(TrieNode node, Map counts) { if (node.children.isEmpty()) { return ""; } StringBuilder sb = new StringBuilder(); for (TrieNode child : node.children.values()) { String childStructure = computeStructure(child, counts); sb.append(child.name).append("(").append(childStructure).append(")"); } node.structure = sb.toString(); // Only non-empty folders can be duplicates based on their content if (!node.structure.isEmpty()) { counts.put(node.structure, counts.getOrDefault(node.structure, 0) + 1); } return node.structure; } private void collectPaths(TrieNode node, List currentPath, List> result, Map counts) { // A folder is deleted if its structure is a duplicate if (counts.getOrDefault(node.structure, 0) > 1) { return; // This folder and its subfolders are deleted } currentPath.add(node.name); result.add(new ArrayList<>(currentPath)); for (TrieNode child : node.children.values()) { collectPaths(child, currentPath, result, counts); } currentPath.remove(currentPath.size() - 1); // Backtrack } } ``` ### Algorithm - **Trie Construction**: Represent the file system hierarchy using a Trie data structure. Each node in the Trie corresponds to a folder. To ensure a canonical representation of subfolders, use a sorted map (like `TreeMap` in Java) to store the children of each node. - **Structure Serialization (Post-order DFS)**: Traverse the Trie in a post-order manner (children before parent). For each node, compute a unique string that represents its subfolder structure. This string is created by concatenating the names of its children and their recursively computed structure strings. For example, a folder with subfolders `b` and `c` (with structures `S_b` and `S_c` respectively) would have a structure string like `b(S_b)c(S_c)`. Store these generated structure strings and their frequencies in a hash map. - **Path Collection (Pre-order DFS)**: Traverse the Trie from the root's children in a pre-order manner to reconstruct the folder paths. For each folder, check its structure string's frequency in the hash map. If the frequency is greater than one, it means the folder is a duplicate, and it (along with its entire subtree) should be deleted. Therefore, we do not add its path to the result and do not traverse further down this branch. Otherwise, add the current path to the result list and continue the traversal to its children. ## Trie + Structure Hashing with IDs This is an optimized approach that also uses a Trie and post-order traversal. However, instead of generating potentially huge strings to represent folder structures, it maps each unique structure to a compact integer ID. This process, sometimes called structure hashing or interning, is significantly more efficient in both time and space. It uses a map to store the canonical representation of a folder's children (a list of child names and their structure IDs) and assigns a unique ID to each. Duplicates are then found by counting these IDs. **Time:** O(S), where `S` is the total number of characters in all folder names. Trie construction takes O(S). The DFS for assigning IDs visits each node once, and the work at each node (map lookups on lists) sums up to O(S) over the entire tree. The final DFS to collect paths also takes O(S). · **Space:** O(S), where `S` is the total number of characters in all folder names. The space is used for the Trie, the `structureToIdMap`, and the `idCounts` map. The total size of keys and values in these maps is proportional to `S`. **Pros:** Highly efficient, with linear time and space complexity with respect to the total input size.; Scales well to large and complex file systems without performance degradation.; Avoids the memory and time overhead of manipulating large strings. **Cons:** The implementation is slightly more complex due to the indirect representation of structures using IDs and custom key objects for the map. ### Explanation This method improves upon the string serialization approach by replacing the heavy string representations with lightweight integer IDs. 1. **Build a Trie**: This step is identical to the first approach. We build a Trie with sorted children maps. 2. **Assign Structure IDs**: We perform a post-order DFS. For a given node, we first recursively get the structure IDs for all its children. The structure of the current node is then defined by a list of `(child_name, child_structure_id)` pairs. This list is canonical because the children are already sorted. We use a `HashMap` to see if we have encountered this exact list of pairs before. - If yes, we reuse the existing ID. - If no, we assign a new, unique ID and store the mapping. This way, identical structures are guaranteed to have the same ID. We also maintain a separate map to count how many times each ID is assigned to a node. 3. **Collect Remaining Paths**: The final step is a pre-order DFS to collect valid paths. When visiting a node, we look up the count for its `structureId`. If the count is greater than 1, the folder is part of a duplicate set and is skipped. Otherwise, its path is valid, added to the results, and its children are visited recursively. This avoids the performance bottleneck of creating, storing, and comparing long strings, making the solution efficient for large inputs. ```java import java.util.*; class Solution { // Using a record for the component of a structure for conciseness and automatic equals/hashCode. // A structure is defined by a list of these components. record StructureComponent(String name, int id) {} class TrieNode { String name; Map children = new TreeMap<>(); int structureId = 0; // 0 for leaves, >0 for non-leaves } int nextId = 1; // Maps a structure (list of child components) to a unique ID Map, Integer> structureToIdMap = new HashMap<>(); // Counts occurrences of each structure ID Map idCounts = new HashMap<>(); public List> deleteDuplicateFolder(List> paths) { TrieNode root = new TrieNode(); // 1. Build the Trie for (List path : paths) { TrieNode curr = root; for (String folder : path) { curr = curr.children.computeIfAbsent(folder, k -> { TrieNode newNode = new TrieNode(); newNode.name = k; return newNode; }); } } // 2. Post-order traversal to assign structure IDs assignStructureIds(root); // 3. Pre-order traversal to collect non-deleted paths List> result = new ArrayList<>(); for (TrieNode child : root.children.values()) { collectPaths(child, new ArrayList<>(), result); } return result; } private int assignStructureIds(TrieNode node) { if (node.children.isEmpty()) { return 0; // A leaf node has a default structure ID 0 } List childStructures = new ArrayList<>(); for (TrieNode child : node.children.values()) { int childId = assignStructureIds(child); childStructures.add(new StructureComponent(child.name, childId)); } // Get or create an ID for this structure int id = structureToIdMap.computeIfAbsent(childStructures, k -> nextId++); node.structureId = id; idCounts.put(id, idCounts.getOrDefault(id, 0) + 1); return id; } private void collectPaths(TrieNode node, List currentPath, List> result) { // A folder is deleted if its structure ID corresponds to a duplicate structure. // ID 0 is for leaves, which cannot be duplicates by this rule. if (node.structureId != 0 && idCounts.getOrDefault(node.structureId, 0) > 1) { return; } currentPath.add(node.name); result.add(new ArrayList<>(currentPath)); for (TrieNode child : node.children.values()) { collectPaths(child, currentPath, result); } currentPath.remove(currentPath.size() - 1); // Backtrack } } ``` ### Algorithm - **Trie Construction**: Same as the previous approach, build a Trie to represent the file system, using a sorted map for children to ensure order. - **Structure Hashing (Post-order DFS)**: Traverse the Trie in a post-order manner. For each node, the goal is to compute a unique ID representing its structure. This structure is defined by the list of its children's names paired with their structure IDs. We use a map (`Map>, Integer>`) to map each unique structure representation to a new integer ID. This avoids creating long strings. We also use another map to count the occurrences of each structure ID. - **Path Collection (Pre-order DFS)**: Traverse the Trie from the root's children. For each folder, check the count of its structure ID. If the count is greater than one, the folder is a duplicate, so we skip it and its subfolders. Otherwise, we add its path to the result and recurse on its children. # Solutions ### Java ```java class Solution { public List> deleteDuplicateFolder(List> paths) { TrieNode root = new TrieNode(); for (List path : paths) { TrieNode curr = root; for (String node : path) { if (!curr.children.containsKey(node)) curr.children.put(node, new TrieNode()); curr = curr.children.get(node); } } Map freq = new HashMap(); construct(root, freq); List> remaining = new ArrayList>(); List path = new ArrayList(); operate(root, freq, remaining, path); return remaining; } public void construct(TrieNode node, Map freq) { if (node.children.isEmpty()) return; List list = new ArrayList(); for (Map.Entry entry : node.children.entrySet()) { String folder = entry.getKey(); TrieNode child = entry.getValue(); construct(child, freq); list.add(folder + "(" + child.serial.toString() + ")"); } Collections.sort(list); for (String str : list) node.serial.append(str); String serialStr = node.serial.toString(); freq.put(serialStr, freq.getOrDefault(serialStr, 0) + 1); } public void operate(TrieNode node, Map freq, List> remaining, List path) { if (freq.getOrDefault(node.serial.toString(), 0) > 1) return; if (!path.isEmpty()) remaining.add(new ArrayList(path)); for (Map.Entry entry : node.children.entrySet()) { String folder = entry.getKey(); TrieNode child = entry.getValue(); path.add(folder); operate(child, freq, remaining, path); path.remove(path.size() - 1); } } } class TrieNode { StringBuffer serial; Map children; public TrieNode() { serial = new StringBuffer(); children = new HashMap(); } } ```