Can I solve this simple problem in faster than O(n^2) time?

If you’re looking for all admissible pairs, then the output size may be as large as Theta(n^2), meaning that there won’t be any asymptotically faster algorithm. Trivially, this would happen if for example all of your dictionaries are identical, in which case all pairs of dictionaries overlap (no pair has any non-matching lists, so they vacuously satisfy the requirement).

Note that the O(n^2) complexity of the bruteforce solution assumes that you can test for list intersection in O(1) time, which isn’t actually the case, but you might get pretty close with some precomputation (set/bitset tricks).

Simple Answer: No.

Why? n dictionaries may result in n(n-1)/2 pairs of matching dictionaries. So even for just enumerating the results in the worst case -- ie every dictionary matches with every other dictionary -- you need n(n-1)/2 operations .. Thus O(n^2)

My previous answer had a faulty premise, but thinking on the problem, we may have a solution that yields a O(n) time compleity answer in exchange for space complexity.

• Loop through the list of dictionaries. For each dictionary, instantiate sets that are keyed for each distinct set pick of all the keys:

  • For Dictionary 1, check existence and then instantiate sets "ajbTruecp", "ajbTruecx". Add Dictionary 1 to those sets.

  • For Dictionary 2, check existence and then instantiate sets "ajbFalsecs", "ajbFalsect". Add Dictionary 2 to those sets.

  • For Dictionary 3, check existence of set "ajbTruecx". It exists and Dictionary 1 is contained. Then these two dictionaries overlap. Check existence and instantiate set "ajbTruecz". Add Dictionary 3 to those sets.

Thus, you can work your way through the list of dictionaries and identify overlaps with O(n) time. Your space complexity would depend on the cardinality of the values in the lists.