Given a list paths of directory info, including the directory path, and all the files with contents in this directory, return all the duplicate files in the file system in terms of their paths. You may return the answer in any order.
A group of duplicate files consists of at least two files that have the same content.
A single directory info string in the input list has the following format:
"root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"It means there are n files (f1.txt, f2.txt ... fn.txt) with content (f1_content, f2_content ... fn_content) respectively in the directory "root/d1/d2/.../dm". Note that n >= 1 and m >= 0. If m = 0, it means the directory is just the root directory.
The output is a list of groups of duplicate file paths. For each group, it contains all the file paths of the files that have the same content. A file path is a string that has the following format:
"directory_path/file_name.txt"
Example 1:
Input: paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"] Output: [["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]
Example 2:
Input: paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)"] Output: [["root/a/2.txt","root/c/d/4.txt"],["root/a/1.txt","root/c/3.txt"]]
Constraints:
1 <= paths.length <= 2 * 1041 <= paths[i].length <= 30001 <= sum(paths[i].length) <= 5 * 105paths[i] consist of English letters, digits, '/', '.', '(', ')', and ' '.
Follow up:
Problem Overview: Each input string represents a directory followed by multiple files and their contents, formatted like "root/a 1.txt(abcd) 2.txt(efgh)". You need to identify files with identical content and return their full paths grouped together. Only groups with more than one file count as duplicates.
Approach 1: Using a HashMap / Dictionary (O(n * L) time, O(n * L) space)
This approach groups files by their content using a hash map. Iterate through each directory string, split it by spaces to separate the directory path from its files, and parse each file entry to extract the file name and the content inside parentheses. Build the full path using the directory and file name, then insert it into a map where the key is the file content and the value is a list of file paths. Because hash lookups are O(1) on average, grouping happens efficiently while scanning the input once.
After processing all entries, iterate through the map and collect only the lists whose size is greater than one. Those represent files that share identical content. The main cost comes from parsing strings and storing them, giving roughly O(n * L) time where L is the average length of each path string. This method relies heavily on fast hashing and string processing, making it a natural application of a hash table combined with careful string parsing.
Approach 2: Direct String Manipulation with 2D Array Comparison (O(n² * L) time, O(n * L) space)
Another way is to first parse all directory strings and store each file as a pair: [fullPath, content] inside a 2D array. Once every file entry is extracted, compare each file's content with every other file using nested loops. When two files share identical content, place their paths into the same duplicate group.
This approach uses only arrays and direct comparisons instead of hashing. The downside is the quadratic comparison step: for n files, the algorithm performs up to n² content checks. Each comparison may scan the entire string content, making the total cost roughly O(n² * L). While simpler conceptually, it becomes slow for large datasets. It mainly demonstrates how duplicate detection works without additional data structures.
Recommended for interviews: The hash map grouping approach is the expected solution. It demonstrates efficient parsing, use of a dictionary for grouping, and linear scanning of the input. Interviewers want to see that you immediately map file content to paths instead of comparing every pair. The brute-force comparison still helps show baseline reasoning, but the hash-based grouping proves you understand how to reduce quadratic work to near-linear time.
To find duplicate files by their content, we can use a HashMap (or Dictionary). For each directory info string, parse the directory path and the files with their contents. Use the content as the key in the map and store full path of the file as its value. After parsing all inputs, the map keys with more than one value represent duplicate files.
This Python solution uses defaultdict from the collections module to store lists of file paths with the same content. We split each path string into directory and file information, then iterate over each file's name and content to record them in our dictionary. Finally, we filter the dictionary to include only entries that have more than one file path, returning them as groups of duplicates.
Time Complexity: O(n), where n is the total number of characters in all file paths. We iterate over each character once.
Space Complexity: O(n) to store the lists of file paths in the dictionary.
This approach is based on directly processing string data and arranging results using a 2D array. Strings are manipulated to extract directory data, file names, and contents into standalone variables, then append paths to a growing structure. Compared to hash maps, this method uses arrays to aggregate identical files.
By substituting hash maps with straightforward string operations and arrays in Python, this solution mimics hash map behavior to achieve equivalent outcomes. It uses slicing to extract filenames and contents and builds a result by tracking paths directly through array indexing.
Time Complexity: O(n), where n is the total input character count due to one-pass evaluation.
Space Complexity: O(n), maintaining paths and intermediate arrays.
We create a hash table d, where the key is the file content and the value is a list of file paths with the same content.
Next, we iterate over paths. For each path, we split it into the directory path and file information. For each file entry, we extract the file name and file content, and append the file path to the corresponding list in hash table d.
Finally, we return all values in hash table d that have more than one file path.
The time complexity is O(n) and the space complexity is O(n), where n is the length of paths.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Using a HashMap or Dictionary | Time Complexity: O(n), where n is the total number of characters in all file paths. We iterate over each character once. |
| Using Direct String Manipulation and 2D Array | Time Complexity: O(n), where n is the total input character count due to one-pass evaluation. |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap / Dictionary Grouping | O(n * L) | O(n * L) | General case; fastest way to group files by identical content |
| Direct String Comparison with 2D Array | O(n² * L) | O(n * L) | Educational baseline when avoiding hash tables or demonstrating brute-force grouping |
Find Duplicate File in System | Live Coding with Explanation | Leetcode - 609 • Algorithms Made Easy • 4,073 views views
Watch 9 more video solutions →Practice Find Duplicate File in System with our built-in code editor and test cases.
Practice on FleetCode