Module 1 · Foundations

How to think about algorithms

Beginner 14 min read A method you can repeat on any problem

A data structure is a way of organising data so certain operations are cheap. An algorithm is a precise recipe that turns input into output. Almost every performance problem you will meet is a mismatch between the two: the right steps performed on the wrong organisation. This lesson gives you a repeatable method for attacking a new problem, and shows the single most useful habit in this whole course: checking a fast solution against a slow, obviously correct one.

📚

A library

Finding one book on a single unsorted pile means checking every book: that is the algorithm "scan". Put the same books on shelves sorted by author and you can jump to the right shelf: the data structure changed, so a faster algorithm ("binary search") became possible. Add a card catalogue (an index) and finding a book takes one lookup. Same books, three organisations, three very different costs.

1. A method for any problem

2. Worked example: "two numbers that add up to a target"

Problem. Given a list of order amounts and a target, return the indices of two different orders whose amounts add up to the target, or None.

① Understand

Input: list of ints (maybe 10⁵ of them), an int target. Output: a pair of indices (i, j), i < j. Questions: negatives allowed? Several answers? (Return any one.) Same element twice? (No.)

② Examples

[250, 80, 1200, 170], 250 → (1, 3). [5], 10 → None. [5, 5], 10 → (0, 1). [], 0 → None.

def two_sum_brute(nums, target):
    """Check every pair: n*(n-1)/2 pairs → O(n²) time, O(1) extra space."""
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return (i, j)
    return None

def two_sum_fast(nums, target):
    """Bottleneck: 'is there an earlier number equal to target - x?' was an O(n) scan.
    A dict answers it in O(1) on average → O(n) time, O(n) space."""
    seen = {}                                   # value -> index where we saw it
    for j, x in enumerate(nums):
        need = target - x
        if need in seen:
            return (seen[need], j)
        seen[x] = j
    return None

for nums, target in [([250, 80, 1200, 170], 250), ([5], 10), ([5, 5], 10), ([], 0)]:
    print(nums, target, "->", two_sum_brute(nums, target), two_sum_fast(nums, target))

[250, 80, 1200, 170] 250 -> (1, 3) (1, 3) [5] 10 -> None None [5, 5] 10 -> (0, 1) (0, 1) [] 0 -> None None

The trade-off is typical: spend memory to save time. The dict costs O(n) extra space and turns an O(n²) algorithm into O(n). For 100,000 orders that is 5 billion pair checks versus 100,000 dict lookups.

3. ⑥ The habit that catches bugs: test against the brute force

The brute force is slow but obviously correct. Use it as an oracle: generate thousands of small random inputs and check that the fast version agrees. This finds edge cases you would never think to write by hand.

import random

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return (i, j)
    return None

def two_sum_buggy(nums, target):
    seen = {x: i for i, x in enumerate(nums)}      # builds the dict FIRST...
    for i, x in enumerate(nums):
        if target - x in seen:                     # ...so x can pair with itself!
            return (i, seen[target - x])
    return None

def is_valid(nums, target, answer):
    if answer is None:
        return two_sum_brute(nums, target) is None
    i, j = answer
    return i != j and nums[i] + nums[j] == target

random.seed(7)
for trial in range(10_000):
    nums = [random.randint(-5, 5) for _ in range(random.randint(0, 6))]
    target = random.randint(-10, 10)
    if not is_valid(nums, target, two_sum_buggy(nums, target)):
        print(f"counter-example after {trial + 1} trials: nums={nums} target={target}")
        print("buggy answer:", two_sum_buggy(nums, target), " correct:", two_sum_brute(nums, target))
        break

counter-example after 5 trials: nums=[1, -4, -2] target=-8 buggy answer: (1, 1) correct: None

The buggy version looks reasonable and passes the obvious examples, but it lets a number pair with itself. Random testing found a counter-example in a moment. Notice we check validity rather than comparing exact answers, because several pairs can be correct. Libraries such as Hypothesis automate this style (property-based testing).

4. The vocabulary of this course

Term	Meaning	Example
Abstract data type (ADT)	What operations are offered	"a stack: push, pop, peek"
Data structure	How those operations are implemented in memory	a stack built on a dynamic array or a linked list
Time complexity	How running time grows with input size n	O(n) for a scan
Space complexity	Extra memory used, beyond the input	O(n) for the `seen` dict
Invariant	A statement that stays true at every step	"everything left of `i` is sorted"
Pattern	A reusable technique for a family of problems	two pointers, sliding window, BFS

Recap

Data structure = organisation; algorithm = steps. Changing the organisation changes which steps are cheap.
Understand → examples → brute force → bottleneck → optimise → test.
Trade memory for time is the most common optimisation (two-sum: O(n²) → O(n) with a dict).
Test the fast version against the brute force on thousands of random small inputs.

Checkpoint

1 · Why write a brute-force solution first, even when you know it is too slow?

The brute force defines "correct". Its inner loop usually is the bottleneck to optimise, and comparing against it on random inputs catches subtle bugs.

2 · In the fast two-sum, why do we check need in seen before adding the current number?

With target 10 and a single 5, adding first would find 5 in seen and wrongly return (0, 0). The invariant "seen holds only indices before j" rules that out.