Solving with lists
Apply the four-step problem-solving process to common list problems in Python.
- Apply the four-step process to list problems
- Implement find_max, reverse_list, contains, and count_occurrences in Python
Let's walk the four-step process for a real problem, then put four list functions side by side so you can see how the same thinking applies each time.
Worked example: find the maximum
Understand. Given a list of numbers, return the largest one. Edge case: what if the list is empty? We'll raise an error — an empty list has no maximum.
Examples by hand. [3, 1, 4, 1, 5, 9] → 9. Trace: start at 3. See 1 —
not bigger. See 4 — bigger, keep 4. See 1 — not bigger. See 5 — bigger, keep
5. See 9 — bigger, keep 9. Done.
Brute force. The trace above is the algorithm: walk the list once, track the largest value seen. O(n) — one pass, no inner loop.
Optimise. There's nothing to optimise. A single pass is already optimal: you can't know the maximum without looking at every element at least once.
Four list functions
The <Runnable> block below implements the four functions. Read the comment on
each before running — try to predict the output first.
Python's standard library already has max(), list.reverse(), and in.
These reimplementations exist so you can see the underlying algorithm — once
you understand what max() does internally, you can reason about when it's
fast enough and when you need something different.
What all four have in common
Every function above is O(n): one pass through the list, constant work per element. This is the baseline for list problems. If you find yourself writing a loop inside a loop, stop and ask whether the inner loop is doing redundant work — that's usually the signal to reach for a different data structure.
Where to go next
Next: key-value thinking — the dict pattern that lets you trade a scan for an instant lookup.