Skip to main content

609 - Find Duplicate File in System

Difficulty: Medium | Pattern: HashMap + String Parsing | Company tags: Dropbox, Google, Amazon

Problem Statement​

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.

The input is a list of strings where each string is: "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ...".

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"]]

Solution: HashMap on Content — O(n × k)​

from collections import defaultdict

def findDuplicate(paths: list[str]) -> list[list[str]]:
    content_to_files = defaultdict(list)
    
    for path in paths:
        parts = path.split()
        directory = parts[0]
        
        for file_info in parts[1:]:
            # Parse "filename(content)"
            paren = file_info.index('(')
            filename = file_info[:paren]
            content = file_info[paren+1:-1]
            
            full_path = directory + '/' + filename
            content_to_files[content].append(full_path)
    
    return [files for files in content_to_files.values() if len(files) > 1]

Dry Run​

paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)"]

After processing:

  • content_to_files["abcd"] = ["root/a/1.txt", "root/c/3.txt"] (2 files → duplicate group)
  • content_to_files["efgh"] = ["root/a/2.txt"] (1 file → not a duplicate)

Result: [["root/a/1.txt","root/c/3.txt"]] ✓

Edge Cases​

  • File content can be empty string: "file.txt()"
  • Same file appearing in multiple paths would be a duplicate
  • Groups with only 1 file → filtered out

Complexity​

  • Time: O(n × k) where n = paths count, k = average files per path
  • Space: O(n × k)