What is the time complexity of Delete Duplicate Folders in System?

The optimal solution has a time complexity of O(N*L).

What is the space complexity of Delete Duplicate Folders in System?

The space complexity is O(N*L).

What data structures are used to solve Delete Duplicate Folders in System?

This problem uses Array, Hash Table, String, Trie, Hash Function. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Delete Duplicate Folders in System?

Insight 1: Representing the file system as a Trie data structure allows efficient traversal and identification of folders based on their paths. Insight 2: The core challenge is defining a robust and efficient way to determine if two folders are identical, which depends on the structure and contents of their subfolders. We can use a unique 'signature' based on children folder name and child signature id to identify identical folder structure

Which companies ask LeetCode 1948. Delete Duplicate Folders in System in interviews?

This problem is frequently asked at Booking.com, Nvidia.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Delete Duplicate Folders in System - LeetCode 1948 Solution

Delete Duplicate Folders in System - Complete Solution Guide

Delete Duplicate Folders in System is LeetCode problem 1948, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 i th 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 t

Detailed Explanation

The problem asks us to identify and delete duplicate folders in a file system represented by a 2D array of paths. Two folders are considered identical if they contain the same set of identical subfolders with the same structure. The deletion process involves marking identical folders and all their subfolders, and then removing them from the file system. The goal is to return a list of the remaining folder paths after the deletion, in any order.

Solution Approach

The provided solution uses a Trie data structure to represent the file system. The algorithm first builds the Trie from the input paths. Then, it recursively calculates a unique signature for each folder based on its subfolders. Identical folders will have the same signature. The solution then identifies folders with duplicate signatures and marks them and their subfolders for deletion. Finally, it traverses the Trie again to collect the paths of the remaining (non-deleted) folders.

Step-by-Step Algorithm

Step 1: **Build the Trie:** Iterate through the input `paths` and construct a Trie data structure. Each node in the Trie represents a folder, and the edges represent the folder hierarchy.
Step 2: **Calculate Signatures:** Recursively traverse the Trie, starting from the root. For each node (folder), calculate a signature based on its children. The signature includes the sorted names of the children folder and their respective signature ids. The sorting ensures the signature is order-independent.
Step 3: **Identify Duplicates:** Store the calculated signatures and their corresponding Trie nodes. Detect folders having the same signature ID. These indicate identical subfolder structure.
Step 4: **Mark for Deletion:** If multiple folders have the same signature (meaning they are duplicates), mark these folders and all their descendant folders in the Trie as `deleted`.
Step 5: **Collect Remaining Paths:** Traverse the Trie again. This time, collect the paths of the folders that are *not* marked as `deleted`. These are the folders that remain after removing the duplicates.
Step 6: **Return Result:** Return the collected paths as a 2D array.

Key Insights

Insight 1: Representing the file system as a Trie data structure allows efficient traversal and identification of folders based on their paths.
Insight 2: The core challenge is defining a robust and efficient way to determine if two folders are identical, which depends on the structure and contents of their subfolders. We can use a unique 'signature' based on children folder name and child signature id to identify identical folder structure
Insight 3: Sorting the subfolders' names before calculating the signature ensures that the order of subfolders doesn't affect the signature, which is crucial for determining identical folders.

Complexity Analysis

Time Complexity: O(N*L)

Space Complexity: O(N*L)

Topics

This problem involves: Array, Hash Table, String, Trie, Hash Function.

Companies

Asked at: Booking.com, Nvidia.

Delete Duplicate Folders in System | LeetCode 1948

Hard

Array Hash Table String Trie Hash Function

Time: O(N*L)Space: O(N*L)

Solution Code

Available in:

import java.util.*;

class Solution {
    public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {
        class TrieNode {
            Map<String, TrieNode> children;
            boolean deleted;

            public TrieNode() {
                this.children = new HashMap<>();
                this.deleted = false;
            }
        }

        TrieNode root = new TrieNode();
        for (List<String> path : paths) {
            TrieNode node = root;
            for (String folder : path) {
                node = node.children.computeIfAbsent(folder, k -> new TrieNode());
            }
        }

        Map<List<Pair<String, Integer>>, Integer> sigToId = new HashMap<>();
        Map<Integer, List<TrieNode>> idToNodes = new HashMap<>();
        int[] nextId = {0}; // Using an array to simulate nonlocal

        class Pair<K, V> {
            K key;
            V value;

            public Pair(K key, V value) {
                this.key = key;
                this.value = value;
            }

            public K getKey() {
                return key;
            }

            public V getValue() {
                return value;
            }

			@Override
			public int hashCode() {
				final int prime = 31;
				int result = 1;
				result = prime * result + ((key == null) ? 0 : key.hashCode());
				result = prime * result + ((value == null) ? 0 : value.hashCode());
				return result;
			}

			@Override
			public boolean equals(Object obj) {
				if (this == obj)
					return true;
				if (obj == null)
					return false;
				if (getClass() != obj.getClass())
					return false;
				Pair other = (Pair) obj;
				if (key == null) {
					if (other.key != null)
						return false;
				} else if (!key.equals(other.key))
					return false;
				if (value == null) {
					if (other.value != null)
						return false;
				} else if (!value.equals(other.value))
					return false;
				return true;
			}
            
        }

        function<Integer, TrieNode> getSignatureId = new function<Integer, TrieNode>() {
            public Integer apply(TrieNode node) {
                List<Pair<String, Integer>> childSigs = new ArrayList<>();
                List<String> sortedKeys = new ArrayList<>(node.children.keySet());
                Collections.sort(sortedKeys);

                for (String name : sortedKeys) {
                    TrieNode child = node.children.get(name);
                    int childId = apply(child);
                    childSigs.add(new Pair<>(name, childId));
                }

                List<Pair<String, Integer>> subSig = childSigs;

                if (!sigToId.containsKey(subSig)) {
                    sigToId.put(subSig, nextId[0]);
                    nextId[0]++;
                }

                int sigId = sigToId.get(subSig);

                if (!subSig.isEmpty()) {
                    idToNodes.computeIfAbsent(sigId, k -> new ArrayList<>()).add(node);
                }

                return sigId;
            }
        };

        getSignatureId.apply(root);

        for (int sigId : idToNodes.keySet()) {
            List<TrieNode> nodes = idToNodes.get(sigId);
            if (nodes.size() > 1) {
                for (TrieNode node : nodes) {
                    node.deleted = true;
                }
            }
        }

        List<List<String>> result = new ArrayList<>();
        function2<Void, TrieNode, List<String>> collectPaths = new function2<Void, TrieNode, List<String>>() {
            public Void apply(TrieNode node, List<String> currentPath) {
                List<String> sortedKeys = new ArrayList<>(node.children.keySet());
                Collections.sort(sortedKeys);

                for (String name : sortedKeys) {
                    TrieNode child = node.children.get(name);
                    if (!child.deleted) {
                        currentPath.add(name);
                        result.add(new ArrayList<>(currentPath));
                        apply(child, currentPath);
                        currentPath.remove(currentPath.size() - 1);
                    }
                }
                return null;
            }
        };

        collectPaths.apply(root, new ArrayList<>());

        return result;
    }

    interface function<R, T> {
        R apply(T arg);
    }

    interface function2<R, T1, T2> {
        R apply(T1 arg1, T2 arg2);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1948: Delete Duplicate Folders in System - Detailed explanation and solution approaches.

Topics

Array Hash Table String Trie Hash Function

Companies

Booking.comNvidia

Stats

Difficulty:Hard

Languages:4

Companies:2

Problem #:1948

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: **Build the Trie:** Iterate through the input `paths` and construct a Trie data structure. Each node in the Trie represents a folder, and the edges represent the folder hierarchy.
2
Step 2: **Calculate Signatures:** Recursively traverse the Trie, starting from the root. For each node (folder), calculate a signature based on its children. The signature includes the sorted names of the children folder and their respective signature ids. The sorting ensures the signature is order-independent.
3
Step 3: **Identify Duplicates:** Store the calculated signatures and their corresponding Trie nodes. Detect folders having the same signature ID. These indicate identical subfolder structure.
4
Step 4: **Mark for Deletion:** If multiple folders have the same signature (meaning they are duplicates), mark these folders and all their descendant folders in the Trie as `deleted`.
5
Step 5: **Collect Remaining Paths:** Traverse the Trie again. This time, collect the paths of the folders that are *not* marked as `deleted`. These are the folders that remain after removing the duplicates.
6
Step 6: **Return Result:** Return the collected paths as a 2D array.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(N*L)

💾

Space Complexity

O(N*L)

📝

Why?

The time complexity is determined by the Trie construction, signature generation, duplicate detection, and the collection of remaining paths. Trie construction is O(N*L) because we iterate each path with length L. The signature generation and tree traversal are also O(N*L) with added cost of sorting children folders to generate signature. The space complexity is dictated by the size of the Trie, which can grow linearly with the total number of folders in all paths.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

String Hashing

Instead of creating a Trie, concatenate the paths into strings and use string hashing to identify potential duplicates. If hash collisions occur, do string comparison.

Time: O(N*L) average case, O(N^2 * L) worst case (due to collision resolution with string comparison), where N is number of paths, L is max length of the path.Space: O(N*L) to store the concatenated path strings.

Trade-offs: Trie structure guarantees identification of identical folders. String Hashing can be faster in cases with relatively few duplicates, but can degrade in worst case.

Graph Traversal and Comparison

Represent the file system as a directed acyclic graph (DAG). Then, use graph traversal algorithms like DFS or BFS to compare subgraphs and identify identical structures. This can be useful if relationships between folders are more complex than a simple hierarchy.

Time: Potentially higher than Trie approach, depending on graph traversal and comparison methods. Can be O(N^2 * L) or worse in some cases.Space: O(N*L) to store the graph representation.

Trade-offs: Graph traversal approaches may be more complex to implement than Trie-based solutions and may not provide significant performance benefits for this particular problem.

✨

Key Insights

1Insight 1: Representing the file system as a Trie data structure allows efficient traversal and identification of folders based on their paths.
2Insight 2: The core challenge is defining a robust and efficient way to determine if two folders are identical, which depends on the structure and contents of their subfolders. We can use a unique 'signature' based on children folder name and child signature id to identify identical folder structure
3Insight 3: Sorting the subfolders' names before calculating the signature ensures that the order of subfolders doesn't affect the signature, which is crucial for determining identical folders.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty file system (empty `paths` input). The algorithm handles this gracefully as the Trie will be empty, and no deletions will occur. The output will be an empty list.
Edge case 2: All folders are unique. The signature calculation will not find any duplicates, so no folders will be marked for deletion. The algorithm will return all input paths in some order.
Edge case 3: Some folders are identical at the root level, with identical subfolders. The algorithm correctly identifies and marks these root-level duplicates and their subfolders.
Edge case 4: Deeply nested identical structures. The recursive signature calculation correctly handles the case where identical structures exist deep within the file system hierarchy.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to sort the children of a folder before calculating the signature. This can lead to different signatures for identical folders if their subfolders are in different orders.

✗Common mistake 2: Not handling the edge case where all folders are unique, leading to incorrect deletion behavior.

✗Common mistake 3: Incorrectly marking subfolders for deletion, resulting in the removal of non-duplicate folders.

✗Common mistake 4: Memory management errors in the C implementation (not freeing allocated memory) can lead to memory leaks.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Detecting and removing duplicate files and folders in cloud storage services like Dropbox or Google Drive to optimize storage usage.

🏦Real-world scenario 2: Identifying and deleting redundant code blocks in large software projects to improve code maintainability and reduce code size.

🎮Real-world scenario 3: Data de-duplication in backup systems: Instead of storing multiple copies of identical data, the system stores only one copy and uses pointers or references to it.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

It's okay to not finish hard problems in interviews. Show your problem-solving process.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 27, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 14

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Delete Duplicate Folders in System"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?