algorithm - Output a map of sets of elements that are disjoint in every other list of elements from a Map of lists -

i have map of lists, each list has integers. output map of sets of elements disjoint in every other list of elements.

for ex: below map of lists

list 1 - 1,2,3,4,5

list 2 - 3,4,5,6,7,8

list 3 - 1,2,3,5,6,7,8

intersection of lists - 3,5 output should map of lists (excluding 3, 5)

list 1 - 1,2,4

list 2 - 4,6,7,8

list 3 - 1,2,6,7,8

i have solution using 2 loops has o(n*n) complexity. trying find optimal solution. pointers appreciated.

can represent different sets using hashtables. way computing overall intersection o(m) m total number of elements across sets.

then, need compute set difference between original sets , computed intersection. again, done fast using hashtables o(k*n) k number of elements in overall intersection , n number of sets.

the structure of algorithm use 2 non-nested loops. first compute intersection of sets, second rid of redundant elements in sets.

you find running example in c++ live on coliru.

#include <vector> #include <iostream> #include <algorithm> #include <unordered_set>  // complexity: o(min(set1.size(), set2.size())) template <typename t> std::unordered_set<t> intersection(std::unordered_set<t> const& set1, std::unordered_set<t> const& set2) {     if (set2.size() < set1.size()) {         return intersection(set2, set1);     } else {         std::unordered_set<t> inter;         (auto const& el1 : set1) {             if (std::find(set2.cbegin(), set2.cend(), el1) != set2.cend()) {                 inter.emplace(el1);             }         }         return inter;     } }  using int_hashset = std::unordered_set<int>;  int main() {     std::vector<int_hashset> input_sets = {{1, 2, 3, 4, 5},                                            {3, 4, 5, 6, 7, 8},                                            {3, 5, 6, 7, 8}};      auto inter_set = *input_sets.cbegin();     // complexity: o(number of elements)     (auto = input_sets.cbegin()+1; input_sets.cend() != it; ++it) {         inter_set = intersection(inter_set, *it);     }     (auto const& : inter_set) {         std::cout << "elem in overall intersection: " << << '\n';     }      // o(n*inter_set.size())     (auto& input_set : input_sets) {         // o(inter_set.size())         (auto el : inter_set) {             input_set.erase(el);         }     }      int = 0;     (auto const& input_set : input_sets) {         ++i;         (auto el : input_set) {             std::cout << "element in set " << << ": " << el << '\n';         }     }     return 0; } 

note: amortized complexity. complexity rise if have lot of collisions inside sets.