Find Duplicate File in System solution and explanation
Google
9 more videos on this problem
Find Duplicate File in System | Live Coding with Explanation | Leetcode - 609Algorithms Made Easy · 5:27 · 4K views
Leetcode - Find Duplicate File in System (Python)Timothy H Chang · 7:04 · 2K views
Find Duplicate File in System | Leetcode 609 | Live coding session💡Coding Decoded · 8:15 · 1K views
609. Find Duplicate File in System (Leetcode Medium)Programming Live with Larry · 11:33 · 1K views
Find Duplicate File in System | Leetcode 609 | String Map | Amazon Microsoft Dropbox | Follow UpNaresh Gupta · 14:14 · 1K views
leetcode 609. Find Duplicate File in Systemalgorithm everyday · 8:33 · 1K views
LeetCode - 609. Find Duplicate File in System | Day 18 May ChallengeAditya Mahajan · 9:01 · 943 views
Amazon Coding Interview Question | Leetcode 609 | Find Duplicate File in SystemWorkWithGoogler · 6:22 · 626 views
Find Duplicate File in System | LeetCode 609 | Coders CampCoders Camp · 7:31 · 484 views
609. Find Duplicate File in System "Python" | LeetCodeSugar Coat · 3:50 · 358 views
The problem
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' '.- You may assume no files or directories share the same name in the same directory.
- You may assume each given directory info represents a unique directory. A single blank space separates the directory path and file info.
Follow up:
- Imagine you are given a real file system, how will you search files? DFS or BFS?
- If the file content is very large (GB level), how will you modify your solution?
- If you can only read the file by 1kb each time, how will you modify your solution?
- What is the time complexity of your modified solution? What is the most time-consuming part and memory-consuming part of it? How to optimize?
- How to make sure the duplicated files you find are not false positive?
Approach overview
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.
Approach 1: Using a HashMap or Dictionary
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.
def find_duplicate(paths):
from collections import defaultdict
content_to_paths = defaultdict(list)
for path in paths:
parts = path.split(' ')
directory = parts[0]
for file_info in parts[1:]:
name, content = file_info.split('(')
content = content[:-1] # Remove the closing bracket
content_to_paths[content].append(f"{directory}/{name}")
return [group for group in content_to_paths.values() if len(group) > 1]
# Example Usage:
paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"]
print(find_duplicate(paths))import java.util.*;
public class DuplicateFiles {
public List<List<String>> findDuplicate(String[] paths) {
Map<String, List<String>> contentMap = new HashMap<>();
for (String path : paths) {
String[] parts = path.split(" ");
String root = parts[0];
for (int i = 1; i < parts.length; i++) {
String[] nameContent = parts[i].split("\\(");
String name = nameContent[0];
String content = nameContent[1].substring(0, nameContent[1].length() - 1);
contentMap.computeIfAbsent(content, k -> new ArrayList<>()).add(root + "/" + name);
}
}
List<List<String>> result = new ArrayList<>();
for (List<String> group : contentMap.values()) {
if (group.size() > 1) {
result.add(group);
}
}
return result;
}
}#include <vector>
#include <string>
#include <unordered_map>
#include <sstream>
using namespace std;
vector<vector<string>> findDuplicate(vector<string>& paths) {
unordered_map<string, vector<string>> contentMap;
for (const auto& path : paths) {
stringstream ss(path);
string root;
getline(ss, root, ' ');
string file;
while (getline(ss, file, ' ')) {
auto it = file.find('(');
string name = file.substr(0, it);
string content = file.substr(it + 1, file.size() - it - 2);
contentMap[content].push_back(root + "/" + name);
}
}
vector<vector<string>> result;
for (const auto& pair : contentMap) {
if (pair.second.size() > 1) {
result.push_back(pair.second);
}
}
return result;
}function findDuplicate(paths) {
const contentMap = {};
for (const path of paths) {
const [root, ...fileData] = path.split(' ');
for (const fileInfo of fileData) {
const separatorIndex = fileInfo.indexOf('(');
const name = fileInfo.substring(0, separatorIndex);
const content = fileInfo.substring(separatorIndex + 1, fileInfo.length - 1);
if (!contentMap[content]) {
contentMap[content] = [];
}
contentMap[content].push(`${root}/${name}`);
}
}
return Object.values(contentMap).filter(group => group.length > 1);
}
// Example Usage:
const paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)"];
console.log(findDuplicate(paths));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LENGTH 3000
typedef struct FileNode {
char* path;
struct FileNode* next;
} FileNode;
typedef struct {
char* content;
FileNode* files;
} ContentGroup;
char*** findDuplicate(char** paths, int pathsSize, int* returnSize, int** returnColumnSizes){
// For simplicity, assume the maximum number of unique contents is small
ContentGroup contentGroups[1000];
int contentGroupCount = 0;
for (int i = 0; i < pathsSize; ++i) {
char* path = paths[i];
char* dirName = strtok(path, " ");
char* filePart;
while ((filePart = strtok(NULL, " ")) != NULL) {
// Get file name and content
char* openBracket = strchr(filePart, '(');
*openBracket = '\0';
char* fileName = filePart;
char* content = openBracket + 1;
char* closeBracket = strchr(content, ')');
*closeBracket = '\0';
// Form full path
char* fullPath = (char*)malloc(strlen(dirName) + strlen(fileName) + 2);
sprintf(fullPath, "%s/%s", dirName, fileName);
// Search for this content
int j;
for (j = 0; j < contentGroupCount; ++j) {
if (strcmp(contentGroups[j].content, content) == 0) {
break;
}
}
// If found, append to files
if (j < contentGroupCount) {
FileNode* newNode = (FileNode*)malloc(sizeof(FileNode));
newNode->path = fullPath;
newNode->next = contentGroups[j].files;
contentGroups[j].files = newNode;
} else { // Create new content group
contentGroups[contentGroupCount].content = strdup(content);
FileNode* newNode = (FileNode*)malloc(sizeof(FileNode));
newNode->path = fullPath;
newNode->next = NULL;
contentGroups[contentGroupCount].files = newNode;
++contentGroupCount;
}
}
}
// Allocate return arrays
char*** result = (char***)malloc(contentGroupCount * sizeof(char**));
*returnColumnSizes = (int*)malloc(contentGroupCount * sizeof(int));
*returnSize = 0;
for (int i = 0; i < contentGroupCount; ++i) {
int count = 0;
FileNode* node;
for (node = contentGroups[i].files; node; node = node->next, ++count);
if (count > 1) {
(*returnColumnSizes)[*returnSize] = count;
result[*returnSize] = (char**)malloc(count * sizeof(char*));
node = contentGroups[i].files;
for (int j = 0; j < count; ++j) {
result[*returnSize][j] = node->path;
node = node->next;
}
++(*returnSize);
}
}
// Free the content groups
for (int i = 0; i < contentGroupCount; ++i) {
free(contentGroups[i].content);
FileNode* node = contentGroups[i].files;
while (node) {
FileNode* next = node->next;
// Path pointers are stored in result
free(node);
node = next;
}
}
return result;
}using System;
using System.Collections.Generic;
public class DuplicateFiles
{
public IList<IList<string>> FindDuplicate(string[] paths)
{
var contentMap = new Dictionary<string, List<string>>();
foreach (var path in paths)
{
var parts = path.Split(' ');
var root = parts[0];
for (int i = 1; i < parts.Length; ++i)
{
var nameContent = parts[i].Split('(');
var name = nameContent[0];
var content = nameContent[1].Substring(0, nameContent[1].Length - 1);
if (!contentMap.ContainsKey(content))
{
contentMap[content] = new List<string>();
}
contentMap[content].Add(root + "/" + name);
}
}
var result = new List<IList<string>>();
foreach (var group in contentMap.Values)
{
if (group.Count > 1)
{
result.Add(group);
}
}
return result;
}
}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.
Approach 2: Using Direct String Manipulation and 2D Array
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.
def find_duplicate_with_arrays(paths):
content_dict = {}
for path in paths:
parts = path.split(' ')
dir_path = parts[0]
for file in parts[1:]:
start = file.find('(')
end = file.find(')', start)
name = file[:start]
content = file[start+1:end]
if content not in content_dict:
content_dict[content] = []
content_dict[content].append(f'{dir_path}/{name}')
return [group for group in content_dict.values() if len(group) > 1]
# Example Usage:
paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)"]
print(find_duplicate_with_arrays(paths))import java.util.*;
public class DuplicateWithArrays {
public List<List<String>> findDuplicate(String[] paths) {
Map<String, List<String>> contentMap = new HashMap<>();
for (String path : paths) {
String[] segments = path.split(" ");
String dir = segments[0];
for (int i = 1; i < segments.length; ++i) {
int openPos = segments[i].indexOf('(');
int closePos = segments[i].indexOf(')', openPos);
String name = segments[i].substring(0, openPos);
String content = segments[i].substring(openPos + 1, closePos);
contentMap.computeIfAbsent(content, k -> new ArrayList<>()).add(dir + "/" + name);
}
}
List<List<String>> result = new ArrayList<>();
for (List<String> group : contentMap.values()) {
if (group.size() > 1) {
result.add(group);
}
}
return result;
}
}#include <vector>
#include <string>
#include <unordered_map>
#include <sstream>
using namespace std;
vector<vector<string>> findDuplicateWithArrays(const vector<string>& paths) {
unordered_map<string, vector<string>> contentMap;
for (const string& path : paths) {
istringstream ss(path);
string root;
getline(ss, root, ' ');
string file;
while (getline(ss, file, ' ')) {
size_t openBracket = file.find('(');
string name = file.substr(0, openBracket);
string content = file.substr(openBracket + 1, file.length() - openBracket - 2);
contentMap[content].emplace_back(root + "/" + name);
}
}
vector<vector<string>> result;
for (const auto& elem : contentMap) {
if (elem.second.size() > 1) {
result.push_back(elem.second);
}
}
return result;
}using System;
using System.Collections.Generic;
public class DuplicateWithArrays
{
public IList<IList<string>> FindDuplicate(string[] paths)
{
Dictionary<string, List<string>> contentMap = new Dictionary<string, List<string>>();
foreach (string path in paths)
{
string[] parts = path.Split(' ');
string directory = parts[0];
for (int i = 1; i < parts.Length; i++)
{
int openParenIndex = parts[i].IndexOf('(');
int closeParenIndex = parts[i].IndexOf(')', openParenIndex);
string name = parts[i].Substring(0, openParenIndex);
string content = parts[i].Substring(openParenIndex + 1, closeParenIndex - openParenIndex - 1);
if (!contentMap.ContainsKey(content))
{
contentMap[content] = new List<string>();
}
contentMap[content].Add(directory + "/" + name);
}
}
var result = new List<IList<string>>();
foreach (var pair in contentMap)
{
if (pair.Value.Count > 1)
{
result.Add(pair.Value);
}
}
return result;
}
}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.
Approach 3: Hash Table
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.
function findDuplicate(paths: string[]): string[][] {
const d = new Map<string, string[]>();
for (const p of paths) {
const [root, ...fs] = p.split(' ');
for (const f of fs) {
const [name, content] = f.split(/\(|\)/g).filter(Boolean);
const t = d.get(content) ?? [];
t.push(root + '/' + name);
d.set(content, t);
}
}
return [...d.values()].filter(e => e.length > 1);
}func findDuplicate(paths []string) [][]string {
d := map[string][]string{}
for _, p := range paths {
ps := strings.Split(p, " ")
for i := 1; i < len(ps); i++ {
j := strings.IndexByte(ps[i], '(')
content := ps[i][j+1 : len(ps[i])-1]
name := ps[0] + "/" + ps[i][:j]
d[content] = append(d[content], name)
}
}
ans := [][]string{}
for _, e := range d {
if len(e) > 1 {
ans = append(ans, e)
}
}
return ans
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Find Duplicate File in System easy or hard?
Find Duplicate File in System is classified as Medium difficulty on LeetCode. The parsing logic is straightforward, but correctly extracting file content and grouping paths efficiently with a hash map requires careful implementation.
How to solve Find Duplicate File in System in O(n)?
Parse each directory string, extract file names and their contents, and map the content to a list of full file paths using a dictionary. Because each file is processed once and hash lookups are constant time on average, grouping duplicates happens in linear time relative to the number of files, aside from string parsing cost.
What is the best approach for Find Duplicate File in System?
The most efficient approach uses a hash map where the key is the file content and the value is a list of file paths. As you parse each directory string, extract the content and append the full path to the corresponding list. After processing all files, return only the groups with more than one path. This runs in O(n * L) time where L is the average string length.
What data structure is used in Find Duplicate File in System?
A hash table (dictionary or HashMap) is the primary data structure. It maps file content strings to a list of file paths that contain that content, allowing efficient grouping of duplicates during a single pass through the input.
What is the time complexity of Find Duplicate File in System?
The optimal hash map solution runs in O(n * L) time because each file entry is parsed once and inserted into a dictionary with O(1) average lookup. A brute-force comparison approach requires checking every pair of files, leading to O(n² * L) time.
Find Duplicate File in System Python or Java solution approach
Both Python and Java solutions follow the same idea: parse each directory string, extract the file content, and store the full path in a map keyed by content. In Python this is typically implemented with a dictionary of lists, while Java uses a HashMap<String, List<String>>.
Is Find Duplicate File in System asked at Google or Amazon interviews?
Variants of duplicate detection and file system parsing appear in interviews at companies like Amazon, Google, and Meta. The problem tests practical skills such as string parsing, hash map grouping, and handling structured input formats.