Two-sum and the dict trick

From lesson 9-2: a loop over n items with a dict lookup inside costs O(n) in total. Dict lookups hash straight to the value in O(1) on average, so the loop count is the only thing that grows.

Every problem in this capstone exploits that single fact, trading a little memory for a lookup table that removes a rescan. This is also the bridge into the Data Structures course, where the same trade shows up again and again.

The interview classic

This unit is the bridge from Python fluency to the Data Structures course and to real coding interviews: three patterns, each a direct application of unit 9's cost model, that together crack a large share of easy and medium interview questions.

Two-sum: given a list of numbers and a target, return the indexes of the two numbers that add up to the target.

two_sum([2, 7, 11, 15], 9)   # [0, 1] because 2 + 7 == 9

The obvious solution checks every pair with two nested loops, O(n²) as you learned in lesson 9-2. The fluent solution makes one pass with a dict: for each number, compute its complement target - n. If the complement was seen earlier, done. Otherwise record the number's index and move on.

Each step is one O(1) dict lookup plus one O(1) insert, so the whole thing is O(n). The pattern to memorize: trade memory (a dict of what you have seen) for speed (no rescanning).

Walking through two_sum

The seen dict maps each number already visited to the index where it appeared. Trace the first call as the numbers arrive: 2 goes in with index 0, then 7 arrives, its complement 2 is already in seen, and the pair of indexes comes straight back.

def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [seen[complement], i]
        seen[n] = i
    return []

print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 9, 4, 7], 11))
print(two_sum([1, 2], 99))

Output

[0, 1]
[2, 3]
[]

enumerate is the lesson 9-1 idiom handing over the index and the value together, which matters here because the answer is a pair of positions rather than a pair of values.

The brute-force alternative compares every number against every other number, costing O(n²). This version makes one pass and lets the dict remember the past for it, so it is O(n) with O(n) extra memory. The final call returns an empty list, the agreed signal that no pair sums to the target.

first_unique

first_unique(text) returns the first character that appears exactly once, or "-" when every character repeats. It counts everything first with Counter from lesson 6-1, then scans the original string in order.

from collections import Counter

def first_unique(text):
    counts = Counter(text)
    for ch in text:
        if counts[ch] == 1:
            return ch
    return "-"

print(first_unique("swiss"))
print(first_unique("aabb"))

Output

w
-

The two-pass structure is the key insight. Counter(text) builds all the counts in O(n), and the second loop walks the string in its original order so the first character it finds with a count of 1 is genuinely the first unique one. Iterating over the Counter instead would answer a different question, since its order reflects first appearance rather than the positions you care about.

In "swiss" the letters s and i repeat or appear early, and w is the first with a count of exactly 1. In "aabb" nothing is unique, so the loop finishes and the return "-" after it supplies the fallback.

has_pair_with_sum

This is a simpler cousin of two_sum. It only answers True or False, so no indexes are needed and a set of seen values replaces the dict. The one-pass complement idea is identical: test target - n against seen, then add n.

def has_pair_with_sum(nums, target):
    seen = set()
    for n in nums:
        if target - n in seen:
            return True
        seen.add(n)
    return False

print(has_pair_with_sum([4, 1, 9], 10))
print(has_pair_with_sum([4, 1, 9], 8))

Output

True
False

seen.add(n) comes after the check, following exactly the same ordering rule as two_sum. Because only a yes-or-no answer is required, a set is the honest data structure here: it stores the values without the index baggage a dict would carry.

For the first call, 1 + 9 = 10, so it returns True as soon as 9 arrives and finds 1 waiting. For the second, no two of the three numbers reach 8, so the loop runs out and return False at the bottom is the answer.

Why the insert comes after the check

In two_sum, storing seen[n] = i after checking the complement is what stops a number from matching itself.

Consider a target of 8 and an input containing a single 4. If the insert came first, then on that same iteration the complement 8 - 4 would be 4, the lookup would find the entry just written, and the function would return the same index twice as though it had found a pair.

Checking the past and only then joining it keeps the invariant that seen holds strictly earlier positions. Small ordering details like this one are exactly what interviewers probe, because they separate having memorized the shape of a solution from understanding why it is correct.