Selecting minimal sum of two distinct entries of two dicts with common keys

Can this function simplified? The goal is return one key from each dictionary (both contain the identical keys), so that the sum of the values that belong to the selected keys are minimal (and also the two keys cannot be identical).

a = {1:50, 2:60, 3:30}
b = {1:50, 2:70, 3:40}
def get_double_min(a, b):
a_sorted = sorted(a, key=a.get)
a1, a2 = a_sorted[0], a_sorted[1]
b_sorted = sorted(b, key=b.get)
b1, b2 = b_sorted[0], b_sorted[1]
if a1 != b1:
return a1, b1
if a1 == b1:
sum1 = a[a1] + b[b2]
sum2 = a[a2] + b[b1]
if sum1 < sum2:
return a1, b2
else:
return a2, b1
else:
raise ValueError("error incorrect value")
print get_double_min(a, b)

• Which do you mean? Simplified in terms of lines-of-code, or in terms of complexity ($O(N \log N)$ to $O(N)$)? Apr 16, 2020 at 17:11
• I would be interested in both versions :) Apr 16, 2020 at 17:26

Simplified: Lines-of-Code

Sorting & Extracting

You are sorting lists of values, storing these in variables, and then extracting only the first entries from these lists. You can use an array slice to keep only the first two entries from the sorted lists, and extract these:

    a1, a2 = sorted(a, key=a.get)[:2]
b1, b2 = sorted(b, key=b.get)[:2]


If / Else

You test a1 != b1, and if that is True, you return a value. If not, you again test these values with a1 == b1, and based that, you return different values, or raise an error.

What are the possibilities for a1 != b1 and a1 == b1? Can the first and the second conditions ever both be False? Either they are equal, or they are not equal. Or something very strange is going on. Since the values are keys to a dictionary, tests for equality must be possible and consistent, so this raising of an error looks like it can never be reached.

So you are left with an if and and else case. In the else case, you again have two possibilities, so we can make the whole thing into one if/elif/else statement:

    if a1 != b1:
return a1, b1
elif a[a1] + b[b2] < a[a2] + b[b1]:
return a1, b2
else:
return a2, b1


Simplified: Time Complexity

Python's sorting is an $$\O(N \log N)\$$ time-complexity operation. This is done twice, once for the a dictionary and once for the b dictionary, but that doesn't change the complexity.

After sorting, the two smallest entries are retrieved. You are taking a $$\O(N \log N)\$$ time complexity hit to extract the smallest and the second smallest entries.

Finding the minimum is a $$\O(N)\$$ operation:

    a1 = min(a, key=a.get)
b1 = min(b, key=b.get)


Finding the second smallest can also be done in $$\O(N)\$$ time:

    a2 = min((k for k in a if k != a1), key=a.get)
b2 = min((k for k in b if k != b1), key=b.get)


The above is doing two $$\O(N)\$$ passes over each list. You can also find the lowest two values in a list using only a single pass by iterating over the list and maintaining the smallest and second smallest values (and their keys). Implementation left to student.

Finally, you can use the Python heapq.nsmallest function.

  a1, a2 = heapq.nsmallest(2, a, key=a.get)
b1, b2 = heapq.nsmallest(2, b, key=b.get)

• very nice! didn't know about the heapq library. knowing the right library saves a lot of time and thinking :) Apr 16, 2020 at 18:17