Hackbright Code Challenges

Smallest Difference: Solution

Smallest Difference: Solution

Problem

Smallest Difference

Challenge

Harder

Concepts

Algorithms, Runtime

Download

smallest-diff-solution.zip


If you sort both lists, you can then compare the smallest items of each list. Find the difference between each smallest item.

If it’s zero, we know we can never do better than that, so we can quit with 0.

Otherwise, remember the smallest-diff seen so far.

Then, for whichever list has the smaller of the two items, move to the next item in that list.

For example, for:

{10, 20, 14, 16, 18}
{30, 23, 54, 33, 96}

We’d sort these into:

{10, 14, 16, 18, 20}
{23, 30, 33, 54, 96}

Then, you’d find the difference between 10 and 23 (13) and remember that our best-so-far. Given that 10 is smaller than 23, we’d move to comparing 14 and 23. This has a difference of 9—an improvement!—so we’d remember that instead.

Fourteen is still less than 23, so we’d move to comparing 16 and 23, and so on.

def smallest_diff(a, b):
    """Return smallest diff between all items in a and b.

        >>> smallest_diff([10, 20, 30, 40], [15, 25, 33, 45])
        3
    """

    # START SOLUTION

    a.sort()
    b.sort()

    best = None  # lowest min so far

    ia = 0  # index to current item in a
    ib = 0  # index to current item in b

    while ia < len(a) and ib < len(b):

        diff = abs(a[ia] - b[ib])

        if diff == 0:
            # Special case: we can do no better than zero, so return 0
            return 0

        if best is None or diff < best:
            best = diff

        # Whichever list currently has smaller item, move to next item
        # in that list.

        if a[ia] > b[ib]:
            ib += 1

        else:
            ia += 1

    return best