# Removing key/value pairs in list of dicts

I have a list of dicts that all have the same keys. If a key's value is None in all dicts then I want to remove them (A solution that creates a new dict is fine as well).

I'm concerned about my Big O complexity of 2n2 (correct me if I'm wrong). Are there better solutions to what I have below?

dicts = [{'a': 1, 'b': None, 'c': 4},
{'a': 2, 'b': None, 'c': 3},
{'a': None, 'b': None, 'c': 3}]

expected = [{'a': 1, 'c': 4}, {'a': 2, 'c': 3}, {'a': None, 'c': 3}]

keys = dicts[0].keys()
keep_keys = []

for key in keys:
vals = []
for d in dicts:
if d[key] is not None:
vals.append(d[key])

if len(vals) != 0:
keep_keys.append(key)

for d in dicts:
for k in d.keys():
if k not in keep_keys:
del d[k]

print dicts == expected


Any solution will have to read the values associated to each key of each dictionary; so you won't be able to drop under $\mathcal{O}(n\times{}m)$ where $m$ is the length of each dictionary. This is pretty much what you are doing, but the if k not in keep_keys call slows things a bit as it is $\mathcal{O}(m)$ when it could be $\mathcal{O}(1)$ by using a set or a dictionary.

If you change the keep_keys list into a set you simplify the logic a bit: as soon as you find a key whose value is not None you can add it into the set.

dicts = [{'a': 1, 'b': None, 'c': 4}, {'a': 2, 'b': None, 'c': 3}, {'a': None, 'b': None, 'c': 3}]
expected = [{'a': 1, 'c': 4}, {'a': 2, 'c': 3}, {'a': None, 'c': 3}]

keep_keys = set()

for d in dicts:
for key, value in d.items():
if value is not None:

remove_keys = set(d) - keep_keys

for d in dicts:
for k in remove_keys:
del d[k]

print dicts == expected


This code, as your original one, assume that there is at least one item in dicts; otherwise set(d) will generate an exception as the variable d is not defined yet.

But this code mixes the actual logic with some tests. You should wrap it in a function to ease reusability and put the testing code under an if __name__ == '__main__': clause:

def filter_nones(dictionaries):
if not dictionaries:
return

keep_keys = set()

for dict_ in dictionaries:
for key, value in dict_.iteritems():
if value is not None:

remove_keys = set(dict_) - keep_keys

for dict_ in dictionaries:
for key in remove_keys:
del dict_[key]

if __name__ == '__main__':
dicts = [
{'a': 1, 'b': None, 'c': 4},
{'a': 2, 'b': None, 'c': 3},
{'a': None, 'b': None, 'c': 3},
]
expected = [
{'a': 1, 'c': 4},
{'a': 2, 'c': 3},
{'a': None, 'c': 3},
]

filter_nones(dicts)
print dicts == expected

• This remove_keys = set(d) - keep_keys threw me off for a bit. At first, I thought, "of course, use sets." I think it's noteworthy that instantiating a set with a dict creates a set of that dict's keys. I never knew that! I would have thought set(d.keys()) would have been necessary. How is that possible?
– Mox
Sep 8, 2017 at 13:37
• @Mox This is due to the semantics of a dict. Since you can query 'some key' in dict_ (for instance), this means that, implicitly, a dict is a collection of keys. Check iter(d) in the documentation Sep 8, 2017 at 13:50