Lookup and Pointers

Until now, when a program needed an answer it looked at everything. That is fine for ten values and hopeless for ten million. This lesson is the first about how much work a loop does and three standard ways to do less: remember what you have seen, walk from both ends, and throw away half of what is left.

The worked examples here are different from the lab's on purpose, so that the lab is a chance to use each idea on a new problem.

Counting the work

Take a simple question: does a list contain the same value twice?

def has_repeat_slow(values):
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            if values[i] == values[j]:
                return True
    return False

assert has_repeat_slow([3, 1, 4, 1]) is True

For n values the inner comparison runs up to n(n − 1)/2 times: 45 comparisons for 10 values, about 500,000 for 1,000, and about 5 billion for 100,000. Work that grows with the square of the input is written O(n²). Doubling the input quadruples the time.

Remember what you have seen

The slow version compares every pair because it forgets. A set remembers every value already passed, and asking a set is O(1):

def has_repeat(values):
    seen = set()
    for value in values:
        if value in seen:
            return True
        seen.add(value)
    return False

assert has_repeat([3, 1, 4, 1]) is True
assert has_repeat([3, 1, 4]) is False

One pass, O(n) time. The price is O(n) extra memory for seen. That trade — memory for time — is the most common optimization in programming, and the lab's first exercise (the famous Two Sum) uses it with a dictionary instead of a set, because it needs to remember where each value was.

The order of the two lines inside the loop matters: check first, then add. Adding first would find every value "already seen" — itself.

Walk from both ends

Some questions have structure a single pass can use. Here the list is sorted, possibly with negative numbers, and we want the squares in sorted order:

def sorted_squares(values):
    result = [0] * len(values)
    left, right = 0, len(values) - 1
    for place in range(len(values) - 1, -1, -1):     # fill from the largest end
        if abs(values[left]) > abs(values[right]):
            result[place] = values[left] ** 2
            left += 1
        else:
            result[place] = values[right] ** 2
            right -= 1
    return result

assert sorted_squares([-4, -1, 0, 3, 10]) == [0, 1, 9, 16, 100]

The largest square is always at one of the two ends. Each step takes the bigger end, writes it into the next slot from the back, and moves that pointer inward. Two pointers that move toward each other and never back up touch each position once: O(n) time, where squaring then sorting would be O(n log n).

The invariant that makes it correct:

Every value outside left…right has already been placed, and every value still between the pointers is no larger in absolute size than the ones placed.

When you write a two-pointer loop, say which pointer moves and why that move cannot skip the answer. If you cannot say it, the loop is probably wrong.

Throw away half

In a sorted list you rarely need to look at every value. Binary search checks the middle, and the answer tells you which half cannot contain what you want. Here it finds the integer square root — the largest r with r * r <= n — by searching over possible answers rather than over a list:

def int_sqrt(n):
    lo, hi = 0, n + 1          # the answer is in [lo, hi): lo is possible, hi is not
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if mid * mid <= n:
            lo = mid           # mid works, so the answer is mid or larger
        else:
            hi = mid           # mid is too big, and so is everything above it
    return lo

assert [int_sqrt(n) for n in (0, 1, 8, 9, 10, 99, 100)] == [0, 1, 2, 3, 3, 9, 10]

Each step halves the range, so a range of a million needs about 20 steps: O(log n). The whole difficulty of binary search is the boundaries, and the cure is to write the invariant down before the loop:

lo is always a possible answer, and hi never is.

With that written, every line follows. lo = mid is safe because mid passed the test; hi = mid is safe because it failed. The loop stops when no values remain between them, and lo is the answer.

There are several styles of binary search, and mixing them causes most bugs. The lab's lower bound uses a half-open window, [lo, hi), where hi is one past the last candidate; in that style lo = mid can loop forever, because when one value is left mid equals lo. Pick one style per function and state its invariant in a comment.

Python traps that interviews look for

Three habits make otherwise correct code fail in surprising ways:

• Mutable default arguments. def log(item, into=[]) creates the list once, when def runs, so every call shares it. Use into=None and create the list inside.
• is instead of ==. is asks whether two names refer to the same object; == asks whether two values are equal. Two separate lists with the same contents are == but not is. The right place for is is x is None.
• Changing the caller's data. values.sort() sorts the caller's list in place; sorted(values) returns a new list. A function that quietly reorders its argument surprises whoever calls it next.

Choosing between them

The last row is not a joke: for twenty values the plain loop is fine and clearest. The others matter when the input is large, or when an interviewer asks what happens if it is.

In the lab

The lab asks for Two Sum in one pass with a dictionary, a palindrome check with two pointers (then a phrase version that skips punctuation), and lower bound — the first index whose value is at least a target — with a half-open window. Each exercise draws your loop's state and records a frame per step, so you can replay your own execution. A fourth exercise fixes the three Python traps above in real code. The mastery challenge gives you a sorted problem that names no technique; one of the four questions asks why the dictionary trick you used for Two Sum does not apply to it.