Sets and dicts for speed

The last step removed hidden loops by remembering something as you go. Very often, what you need to remember is which values you have seen, and then everything depends on how fast you can ask "have I seen this one?"

in on a list and on a set

x in values on a list compares x with the items one by one, from the start: O(n). A set keeps its values in a table, each at a place worked out from the value's hash, a number Python computes from the value. To answer x in seen, Python computes the hash of x and looks in that one place, so the answer takes O(1) on average, however big the set is. A dict finds its keys in the same way. (The worst case, when many values land in the same place, is O(n), and it's rare. The module on hash tables shows how the table works.)

>>> numbers = [4, 8, 15, 16, 23, 42]
>>> 23 in numbers
True
>>> lookup = set(numbers)
>>> 23 in lookup
True
>>> 7 in lookup
False

The answers are the same; the cost isn't. Building set(numbers) costs O(n) time once, and the set takes O(n) extra memory: you trade memory for speed. In a loop over n values, in on a list makes the loop O(n²); on a set, O(n).

One trap: if x in set(numbers): inside the loop builds a new set in every round, which is O(n) again. Build the set once, before the loop.

Duplicates and the first repeated value

set(values) drops repeats, so a list has a duplicate when its set is smaller than the list. To find which value repeats first, keep a set of the values seen so far:

def has_duplicate(values):
    return len(set(values)) != len(values)


def first_repeat(values):
    seen = set()
    for value in values:
        if value in seen:
            return value
        seen.add(value)
    return None


print(has_duplicate([3, 1, 4, 1, 5]))
print(has_duplicate([2, 7, 1, 8]))
print(first_repeat([5, 3, 9, 3, 5]))
print(first_repeat([1, 2, 3]))

True
False
3
None

Each round does one lookup and one add, both O(1) on average, so first_repeat is O(n) time and O(n) memory. With seen = [] and append, it gives the same answers in O(n²).

Counting with Counter

How often does each value appear? You counted with a dict in the dictionaries module. collections.Counter does that loop for you, in one O(n) pass. It's a dict from each value to its count, a value it hasn't seen counts as 0, and most_common(k) gives the k most common values with their counts, the most common first:

>>> from collections import Counter
>>> votes = Counter(["tea", "coffee", "tea", "juice", "tea", "coffee"])
>>> votes["tea"]
3
>>> votes["water"]
0
>>> votes.most_common(2)
[('tea', 3), ('coffee', 2)]

"The k most common values" is a classic interview question. Counting is O(n) on average. Then most_common(k) picks the top k of the m different values in O(m log k) (the module on sorting shows how), and without a k it sorts all of them, O(m log m).

Two values that add up to a target

Is there a pair of values that adds up to target? Comparing every pair is O(n²). Turn the question around: for each value x, the partner it needs is target - x. If that partner is among the values seen so far, there's a pair:

def has_pair(values, target):
    seen = set()
    for x in values:
        if target - x in seen:
            return True
        seen.add(x)
    return False


print(has_pair([8, 3, 11, 5], 16))
print(has_pair([8, 3, 11, 5], 10))
print(has_pair([5], 10))

True
False
False

11 and 5 make 16, and no two values make 10. The order of the two lines in the loop matters: the check comes before the add, so a value never pairs with itself, and the lone 5 doesn't count as 5 + 5.

When you need where the partner is, not just whether it exists, use a dict instead of a set: map each value seen to its index, positions[x] = i, and positions[target - x] gives the partner's index. That's the classic interview question "two sum".

To have each index together with its value, loop with enumerate, in place of for i in range(len(values)) and values[i]:

>>> for i, x in enumerate([8, 3, 11]):
...     print(i, x)
...
0 8
1 3
2 11