Skip to main content

Find Duplicate File in System

Problem Description​

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"

Examples​

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 \leq \text{paths.length} \leq 2 \times 10^4
  • 1≤paths[i].length≤30001 \leq paths[i].length \leq 3000
  • 1≤sum(paths[i].length)≤5∗1051 \leq sum(paths[i].length) \leq 5 * 10^5
  • 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.

Solution for Find Duplicate File in System​

Approach 1 Brute Force [Time Limit Exceeded]​

For the brute force solution, firstly we obtain the directory paths, the filenames and file contents separately by appropriately splitting the elements of the pathspathspaths list. While doing so, we keep on creating a list which contains the full path of every file along with the contents of the file. The list contains data in the form

[[file_1_full_path,file_1_contents],[file_2_full_path,file_2_contents]...,[file_n_full_path,file_n_contents]]

Once this is done, we iterate over this list. For every element i chosen from the list, we iterate over the whole list to find another element j whose file contents are the same as the ithi^{th} element. For every such element found, we put the jthj^{th} element's file path in a temporary list l and we also mark the jthj^{th} element as visited so that this element isn't considered again in the future. Thus, when we reach the end of the array for every ithi^{th} element, we obtain a list of file paths in l, which have the same contents as the file corresponding to the ithi^{th} element. If this list isn't empty, it indicates that there exists content duplicate to the ithi^{th} element. Thus, we also need to put the ithi^{th} element's file path in the l.

At the end of each iteration, we put this list l obtained in the resultant list res and reset the list l for finding the duplicates of the next element.

Code in Different Languages​

Written by @Shreyash3087
#include <vector>
#include <string>
#include <sstream>
#include <unordered_map>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<std::string>> findDuplicate(std::vector<std::string>& paths) {
        std::vector<std::pair<std::string, std::string>> list;
        for (const auto& path : paths) {
            std::istringstream iss(path);
            std::string dir;
            iss >> dir;
            std::string file;
            while (iss >> file) {
                auto pos = file.find('(');
                std::string fileName = file.substr(0, pos);
                std::string content = file.substr(pos + 1, file.size() - pos - 2);
                list.emplace_back(dir + "/" + fileName, content);
            }
        }

        std::vector<bool> visited(list.size(), false);
        std::vector<std::vector<std::string>> res;
        for (size_t i = 0; i < list.size() - 1; ++i) {
            if (visited[i]) continue;
            std::vector<std::string> l;
            for (size_t j = i + 1; j < list.size(); ++j) {
                if (list[i].second == list[j].second) {
                    l.push_back(list[j].first);
                    visited[j] = true;
                }
            }
            if (!l.empty()) {
                l.push_back(list[i].first);
                res.push_back(l);
            }
        }
        return res;
    }
};

Complexity Analysis​

Time Complexity: O(n×x+f2×s)O(n \times x + f^2 \times s)​

Reason: Creation of list will take O(n∗x), where n is the number of directories and x is the average string length. Every file is compared with every other file. Let f files are there with average size of s, then files comparision will take O(f2∗s), equals can take O(s). Here, Worst case will be when all files are unique.

Space Complexity: O(n×x)O(n \times x)​

Reason: Size of lists res and list can grow upto n∗x.

Approach 2 Using HashMap​

Algorithm​

In this approach, firstly we obtain the directory paths, the file names and their contents separately by appropriately splitting each string in the given paths list. In order to find the files with duplicate contents, we make use of a HashMap map, which stores the data in the form (contents,list_of_file_paths_with_this_content). Thus, for every file's contents, we check if the same content already exist in the hashmap. If so, we add the current file's path to the list of files corresponding to the current contents. Otherwise, we create a new entry in the map, with the current contents as the key and the value being a list with only one entry(the current file's path).

At the end, we find out the contents corresponding to which atleast two file paths exist. We obtain the resultant list res, which is a list of lists containing these file paths corresponding to the same contents.

Code in Different Languages​

Written by @Shreyash3087
#include <iostream>
#include <vector>
#include <unordered_map>
#include <sstream>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<string>> findDuplicate(vector<string>& paths) {
        unordered_map<string, vector<string>> map;
        for (const string& path : paths) {
            istringstream iss(path);
            vector<string> values((istream_iterator<string>(iss)), istream_iterator<string>());
            for (size_t i = 1; i < values.size(); ++i) {
                size_t pos = values[i].find('(');
                string name = values[i].substr(0, pos);
                string content = values[i].substr(pos + 1, values[i].size() - pos - 2);
                map[content].push_back(values[0] + "/" + name);
            }
        }
        vector<vector<string>> res;
        for (const auto& pair : map) {
            if (pair.second.size() > 1) {
                res.push_back(pair.second);
            }
        }
        return res;
    }
};

Complexity Analysis​

Time Complexity: O(n×x)O(n \times x)​

Reason: n strings of average length x is parsed.

Space Complexity: O(n×x)O(n \times x)​

Reason: map and res size grows upto n∗x.

References​

Authors:

Loading...