# Find Duplicate File in System
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-duplicate-file-in-system)
Canonical: https://scaleengineer.com/dsa/problems/find-duplicate-file-in-system
**Data structures:** Array, Hash Table, String
**Companies:** [Dropbox](https://scaleengineer.com/companies/dropbox), [Turing](https://scaleengineer.com/companies/turing), [Applied Intuition](https://scaleengineer.com/companies/applied-intuition)
---
## 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 * 104`
* `1 <= paths[i].length <= 3000`
* `1 <= sum(paths[i].length) <= 5 * 105`
* `paths[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?

# Approaches
## Brute-Force Comparison
This approach involves first parsing all the input strings to extract a list of all file paths and their corresponding contents. Then, it iterates through this list, comparing each file with every other file to find duplicates. Files with identical content are grouped together.
**Time:** O(L + M^2 * C), where L is the total length of all input strings, M is the total number of files, and C is the maximum length of a file's content. The O(L) part is for parsing the input. The O(M^2 * C) part is for the nested loop comparing every pair of files. · **Space:** O(L), required to store the list of all file paths and their contents after parsing, where L is the total length of all input strings.
**Pros:** Conceptually simple and straightforward to implement without complex data structures like hash maps.
**Cons:** Highly inefficient due to the nested loop structure, leading to a quadratic time complexity relative to the number of files.; Repeatedly compares file contents, which can be slow if contents are large.
### Explanation
First, we need to process the input `paths` array. We'll iterate through each string, parse it to get the directory path and the individual file information. For each file, we extract its name and content, and construct the full file path. We store these `(full_path, content)` pairs in a list.

After creating this list of all files, we use a nested loop to compare every pair of files. A boolean array `visited` is used to avoid redundant comparisons and to ensure each file belongs to only one group.

The outer loop picks a file that hasn't been visited yet. The inner loop compares this file's content with all subsequent unvisited files. If a match is found, the matching file's path is added to the current group, and it's marked as visited.

If a group contains more than one file path at the end of the inner loop, it's considered a group of duplicates and is added to the final result list.

```java
class Solution {
    class FileInfo {
        String path;
        String content;
        FileInfo(String p, String c) {
            this.path = p;
            this.content = c;
        }
    }

    public List<List<String>> findDuplicate(String[] paths) {
        List<FileInfo> allFiles = new ArrayList<>();
        for (String pathInfo : paths) {
            String[] parts = pathInfo.split(" ");
            String dir = parts[0];
            for (int i = 1; i < parts.length; i++) {
                String file = parts[i];
                int contentStart = file.indexOf('(');
                String fileName = file.substring(0, contentStart);
                String content = file.substring(contentStart + 1, file.length() - 1);
                allFiles.add(new FileInfo(dir + "/" + fileName, content));
            }
        }

        List<List<String>> result = new ArrayList<>();
        boolean[] visited = new boolean[allFiles.size()];
        for (int i = 0; i < allFiles.size(); i++) {
            if (visited[i]) {
                continue;
            }
            List<String> currentGroup = new ArrayList<>();
            currentGroup.add(allFiles.get(i).path);
            
            for (int j = i + 1; j < allFiles.size(); j++) {
                if (!visited[j] && allFiles.get(i).content.equals(allFiles.get(j).content)) {
                    currentGroup.add(allFiles.get(j).path);
                    visited[j] = true;
                }
            }
            
            if (currentGroup.size() > 1) {
                result.add(currentGroup);
            }
        }
        return result;
    }
}
```
### Algorithm
- Create a helper class or a simple data structure (like a Pair) to store `(filePath, content)`.
- Create a list, say `allFiles`, to hold these pairs.
- Iterate through the input `paths` array:
    - a. For each string, parse it to extract the directory path and file information.
    - b. For each file, create a `(filePath, content)` pair and add it to `allFiles`.
- Initialize an empty list `result` to store the groups of duplicate file paths.
- Initialize a boolean array `visited` of the same size as `allFiles`, all set to `false`.
- Iterate from `i = 0` to `allFiles.size() - 1`:
    - a. If `visited[i]` is `true`, skip to the next iteration.
    - b. Create a new list `currentGroup` and add `allFiles.get(i).filePath`.
    - c. Iterate from `j = i + 1` to `allFiles.size() - 1`:
        - d. If `visited[j]` is `false` and the content of file `i` matches the content of file `j`:
            - i. Add `allFiles.get(j).filePath` to `currentGroup`.
            - ii. Set `visited[j] = true`.
    - e. If `currentGroup.size() > 1`, add `currentGroup` to `result`.
- Return `result`.

## HashMap to Group by Content
This is a highly efficient approach that uses a hash map to group files by their content. The file content serves as the key, and the value is a list of file paths that share this content. This avoids redundant comparisons and directly groups duplicates.
**Time:** O(L), where L is the total length of all characters in the input `paths` array. We process each part of the input strings once for parsing and hash map operations. String hashing and equality checks take time proportional to string length, but since we do this for every part of the input, it sums up to O(L). · **Space:** O(L), in the worst-case scenario where all file contents are unique, the hash map will store all file paths and their contents. The total space will be proportional to the total length of the input strings, L.
**Pros:** Very efficient with a linear time complexity relative to the total size of the input.; Scales well with a large number of files.; Directly builds the groups of duplicates without extra comparison steps.
**Cons:** Requires extra space for the hash map, which can be significant if there are many files with large, unique contents.
### Explanation
The core idea is to use a `HashMap<String, List<String>>` where the key is the file content and the value is a list of full file paths having that content.

We iterate through each string in the input `paths` array. For each string, we parse it to extract the directory path and the information for each file within that directory.

For every file, we extract its name and content. The full path is constructed by combining the directory path and the file name.

We then use the file's content as a key to our hash map. If the key already exists, we append the current file's full path to the list associated with that key. If the key doesn't exist, we create a new entry in the map with the content as the key and a new list containing the current file's path as the value.

After processing all files from all input strings, the hash map will contain all the necessary groupings. We then iterate through the values of the map. Any list of paths with a size greater than one represents a group of duplicate files, which we add to our final result list.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<List<String>> findDuplicate(String[] paths) {
        Map<String, List<String>> contentMap = new HashMap<>();
        
        for (String pathInfo : paths) {
            String[] parts = pathInfo.split(" ");
            String directoryPath = parts[0];
            
            for (int i = 1; i < parts.length; i++) {
                String fileInfo = parts[i];
                int openParen = fileInfo.indexOf('(');
                
                String fileName = fileInfo.substring(0, openParen);
                String content = fileInfo.substring(openParen + 1, fileInfo.length() - 1);
                
                String fullPath = directoryPath + "/" + fileName;
                
                contentMap.computeIfAbsent(content, k -> new ArrayList<>()).add(fullPath);
            }
        }
        
        List<List<String>> result = new ArrayList<>();
        for (List<String> pathList : contentMap.values()) {
            if (pathList.size() > 1) {
                result.add(pathList);
            }
        }
        
        return result;
    }
}
```
### Algorithm
- Initialize a `HashMap<String, List<String>> contentMap`.
- Iterate through each string `pathInfo` in the input `paths` array:
    - a. Split `pathInfo` by spaces to get an array of strings, `parts`.
    - b. The first element, `parts[0]`, is the `directoryPath`.
    - c. Iterate through the rest of the `parts` (from index 1 to end):
        - i. Each part is a file string like `"f1.txt(f1_content)"`.
        - ii. Find the index of `'('` to separate the file name and content.
        - iii. Extract `fileName` and `content`.
        - iv. Construct the `fullPath` as `directoryPath + "/" + fileName`.
        - v. Use `contentMap.computeIfAbsent(content, k -> new ArrayList<>()).add(fullPath);` to add the path to the list associated with its content.
- Initialize an empty `List<List<String>> result`.
- Iterate through the values (which are lists of paths) in `contentMap`.
- If a list's size is greater than 1, add it to `result`.
- Return `result`.

# Solutions
### Java

```java
class Solution { public List < List < String >> findDuplicate ( String [] paths ) { Map < String , List < String >> d = new HashMap <>(); for ( String p : paths ) { String [] ps = p . split ( " " ); for ( int i = 1 ; i < ps . length ; ++ i ) { int j = ps [ i ]. indexOf ( '(' ); String content = ps [ i ]. substring ( j + 1 , ps [ i ]. length () - 1 ); String name = ps [ 0 ] + '/' + ps [ i ]. substring ( 0 , j ); d . computeIfAbsent ( content , k -> new ArrayList <>()). add ( name ); } } List < List < String >> ans = new ArrayList <>(); for ( var e : d . values ()) { if ( e . size () > 1 ) { ans . add ( e ); } } return ans ; } }
```

### CPP

```cpp
class Solution { public: vector < vector < string >> findDuplicate ( vector < string >& paths ) { unordered_map < string , vector < string >> d ; for ( auto & p : paths ) { auto ps = split ( p , ' ' ); for ( int i = 1 ; i < ps . size (); ++ i ) { int j = ps [ i ]. find ( '(' ); auto content = ps [ i ]. substr ( j + 1 , ps [ i ]. size () - j - 2 ); auto name = ps [ 0 ] + '/' + ps [ i ]. substr ( 0 , j ); d [ content ]. push_back ( name ); } } vector < vector < string >> ans ; for ( auto & [ _ , e ] : d ) { if ( e . size () > 1 ) { ans . push_back ( e ); } } return ans ; } vector < string > split ( string & s , char c ) { vector < string > res ; stringstream ss ( s ); string t ; while ( getline ( ss , t , c )) { res . push_back ( t ); } return res ; } };
```

### Python

```python
class Solution : def findDuplicate ( self , paths : List [ str ]) -> List [ List [ str ]]: d = defaultdict ( list ) for p in paths : ps = p . split () for f in ps [ 1 :]: i = f . find ( '(' ) name , content = f [: i ], f [ i + 1 : - 1 ] d [ content ]. append ( ps [ 0 ] + '/' + name ) return [ v for v in d . values () if len ( v ) > 1 ]
```