Lesson 1 — The Seen Question

~20 minutes · the hashing invariant · Python

Tonight you solve your first problem: Two Sum — the single most-asked interview question in existence, and the fastest win in all of DSA. It looks like one problem, but hiding inside it is the most reusable idea in interview problems. This lesson teaches you that idea, with a name attached, so you can spot it and reuse it forever.

The invariant

Hashing: trade O(n) space to make “have I seen X?” an O(1) question.

That's the whole idea. A huge family of problems is secretly asking, over and over, “have I seen this thing before?” Asked naively — by re-scanning a list — each ask costs O(n). Asked against a hash structure, each ask costs O(1) on average. You pay for that speed with memory: the structure remembering what you've seen can grow to O(n).

What Python gives you

Python has two hash structures built in:

• dict — remembers things with an attached value: seen[7] = 0 (“I saw 7 at index 0”).
• set — remembers only that you saw something: seen.add(7).

Both give you average O(1) insert and O(1) membership (x in seen) — they hash the key straight to its storage slot instead of searching for it (Python wiki: time complexity). That one sentence is all the internals you need for now.

Two Sum: the slow way first

The problem: given a list nums and a target, return the indices of the two numbers that add up to target. The obvious approach is to try every pair:

def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):   # every pair after i
            if nums[i] + nums[j] == target:
                return [i, j]

This works — and it's O(n²): for each element, the inner loop re-scans the rest of the list. What is that inner loop really doing? It's asking, slowly, “is target − nums[i] anywhere in here?” That's a seen question — and we just learned what answers seen questions in O(1).

Two Sum: the hash way

Flip the loop around. Walk the list once; at each element x, ask: have I seen target − x? If yes, the pair is complete. If no, remember x (with its index, in a dict) and move on.

The hash table turns “where is the partner?” into one lookup before the current number is remembered.

def two_sum(nums, target):
    seen = {}                        # number -> index where I saw it
    for i, x in enumerate(nums):
        want = target - x            # the partner x needs
        if want in seen:             # "have I seen want?" — O(1)
            return [seen[want], i]   # yes: pair complete
        seen[x] = i                  # no: remember x, THEN move on

Notice the order: check first, insert after. Insert first and x could match itself (with target = 6 and x = 3, you'd “find” the 3 you just inserted).

Transfer: same question, new costume

Contains Duplicate: does any value appear twice in an array?

Before scrolling: it's the seen question again — but this time you don't need any partner index, only whether you've seen the value. So which structure, and what's the loop? Say your prediction out loud.

def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen: return True    # "have I seen x?"
        seen.add(x)
    return False

What the trade buys you

On a million elements that's roughly a trillion steps versus a million. Memory is the cheapest thing you can spend.

Practice — answer before you scroll past

seen = {}
for i, x in enumerate(nums):
    seen[x] = i
    if target - x in seen:
        return [seen[target - x], i]

Your move (tonight)

Solve these on LeetCode, in order, logging each in your Notion tracker with the cycle — predict → attempt → compare → encode:

1. Two Sum — your first solve. Close this page, write both versions (slow, then hash) from memory, and submit. Getting stuck and un-stuck is the point; peeking back here counts as the “compare” step.
2. Contains Duplicate — you already predicted it above; now write it cold and run it.
3. Valid Anagram — only if energy remains. Hint for the predict step: what would you count, and what structure counts things?

For the encode step, write the invariant at the top of this page in your own words — that line is what revision days will test.

Stuck or curious? Ask your teacher (the agent) — that's what it's for.