Getting list of keys in Python dictionary whose dict-values are minimal according to a defined order

Question

I have a dictionary such as:

d = {'a':[0,0], 'b':[0,0], 'c':[0,1], 'd':[1,1]}

There's an order on the values, basically the lexicographic one, such that [0, 0] < [0,1] < [1,1].

I'm interested in retrieving the keys whose values are minimal according to this order. In this case the desired result is:

result = ['a', 'b']

I can do this by (1) getting the values of the dict, (2) converting it to a list L, (3) sorting L with:

L.sort(key = str),

then (4) getting the minimal element m of the sorted L, and finally (5) retrieving the keys whose values are m.

I can think of other variations of this procedure, but they all involve going through the dictionary and comparing things, and they're all perhaps too convoluted.

My question is if there's some simpler, more elegant (and more efficient) way of doing this. Should I be using a different data structure instead of a dictionary in the first place?

Answer 1

The simplest way is to use the min() function to find the minimum value, then select the keys corresponding to that minimum using a list comprehension:

d = {'a': [0, 0], 'b': [0, 0], 'c': [0, 1], 'd': [1, 1]}
min_value = min(d.values())
keys = [key for key, val in d.items() if val == min_value]

This solution has the O(n) time complexity.

You could also use itertools.groupby, although this would require sorting the dictionary by values (and thus runs in O(n log n) time):

from itertools import groupby
keys = next(list(g) for k, g in groupby(sorted(d, key=d.get), key=d.get))