609. Find Duplicate File in System
Model: qwen3.5:9b
Topics: Hash Table,String
FAANG asked: 1
Acceptance rate: 61.2%
Problem Breakdown
The problem asks us to identify duplicate files across a file system represented by an array of strings (paths). Each string describes a directory containing several files with their contents in parentheses. We need to return groups of full paths where the content is identical.
Inputs: A list paths where each element follows the format "directory_path filename1(content) filename2(content)".
Outputs: A list of lists, where each inner list contains file paths sharing the same content string.
Constraints & Edge Cases:
- Directory names and filenames do not contain spaces (implied by space-delimited parsing).
- Content inside parentheses is treated as a unique identifier for duplication checks.
- We must handle cases with no duplicates (return empty outer list) or single files in directories (
m=0). - The total length of all paths is bounded, ensuring linear-time solutions are viable relative to input size.
Intuition
A brute-force approach would be to compare every file’s content against every other file’s content across the entire system. If there are files and each has average length , this comparison takes , which is too slow for large inputs ( paths).
The key insight is that duplication depends solely on content. We can use a Hash Map (Dictionary) to group file paths by their content. By iterating through the input once and mapping content -> list of full_paths, we reduce the complexity significantly. After populating this map, any entry with more than one path in its value indicates duplicates. This transforms an problem into a linear scan relative to total characters read ().
Approach
- Data Structure: Use
collections.defaultdict(list)where the key is the file content string and the value is a list of full paths for files with that content. - Parsing Logic:
- Iterate through each path string in
paths. - Split the string by spaces to separate the directory root from individual file entries (e.g.,
"root/a"vs"1.txt(abcd)"). The first part is always the directory; subsequent parts are files. - For each file entry, extract the filename and content using string slicing based on parentheses positions (
(and)). - Construct the full path by joining the directory root with a
/and the extracted filename (handling cases where the directory might be just “root”).
- Iterate through each path string in
- Grouping: Append the constructed full path to the list corresponding to its content key in the hash map.
- Filtering: After processing all paths, iterate through the values of our dictionary. Collect only those lists that have a length greater than or equal to 2 (indicating at least two files share the same content).
Follow-up Considerations:
- Real File System Search: We would use DFS for deep directory structures if memory is constrained by stack depth, but BFS works well too; however, since we need file contents regardless of location, traversal order matters less than hashing strategy.
- Large Files (GB): Storing full content strings as keys in a hash map consumes excessive memory (). Instead, for large files, we would compute a checksum/hash incrementally or store only the file hashes and paths if exact match isn’t strictly required by storage constraints. If strict equality is needed without loading into RAM fully, chunked hashing (e.g., MD5/SHA256) allows us to verify duplicates with memory overhead per hash value relative to content size.
- Read 1kb at a time: We would accumulate the file’s rolling hash or full checksum as we read chunks. Time complexity remains proportional to bytes read (). The most time-consuming part is I/O and hashing; memory consumption drops significantly if we only store hashes instead of raw content strings, though collision probability must be managed (e.g., double-hashing or verifying a few top candidates with full file comparison).
- False Positives: Hash collisions are rare but possible. To ensure accuracy, one could use strong cryptographic hashes (SHA256) which have negligible collision rates for practical inputs. If memory allows, storing the actual content is safest; if not, verify potential duplicates by reading and comparing a subset of chunks or using double hashing to minimize false positives.
Complexity Analysis
- Time: , where is the total number of characters in all input strings (sum of lengths). We parse each character once for splitting and slicing, and hash operations are proportional to content length.
- Space: , where is the number of unique contents found, and is the average path list size per key (worst case all files duplicate). In a memory-constrained scenario with large file follow-ups, space can be optimized to store only hashes (), reducing it from content-size dependent to constant-per-file overhead.
Solution
from collections import defaultdict
from typing import List
class Solution:
def findDuplicate(self, paths: List[str]) -> List[List[str]]:
# Map content string to list of full file paths
file_map = defaultdict(list)
for path_str in paths:
parts = path_str.split()
# The first part is the directory root (e.g., "root/a")
dir_path = parts[0]
# Iterate over remaining parts which are files with content info
for i in range(1, len(parts)):
entry = parts[i]
# Extract filename and content from format: name(content)
open_paren_idx = entry.find('(')
close_paren_idx = entry.rfind(')')
if open_paren_idx != -1 and close_paren_idx > open_paren_idx:
filename = entry[:open_paren_idx]
content = entry[open_paren_idx + 1 : close_paren_idx]
# Construct full path. Ensure separator is '/'
# Note: Input format implies dir_path does not end with / usually,
# but we append it to match output requirement "dir/file"
full_path = f"{dir_path}/{filename}"
file_map[content].append(full_path)
# Filter groups that have at least 2 files (duplicates found)
return [group for group in file_map.values() if len(group) > 1]
Edge Cases Handled
- No Duplicates: If no content matches,
file_mapvalues will all be length 1. The list comprehension filters these out, returning an empty list[[]]. (Note: LeetCode expects[], not a list containing one empty group). - Single File Directory (
m=0): Logic handles this naturally as the loop over files simply doesn’t execute for that entry string if no file tokens exist after split. - Root Path: If directory is just
"root", constructing path becomesf"{dir_path}/{filename}"which correctly yields"root/filename.txt". - Content with Special Characters: The parsing relies on parentheses as delimiters, so content inside
( )can contain any characters except the closing parenthesis (which ends the token). This adheres to standard constraints for this problem.