One Pass, One Accumulator
A single pass through a sequence with an accumulator variable can find the maximum, count matches, or search for a value. · 12 min
Three questions come up over and over: what is the largest value here, how many values meet some test, and is a particular value present at all. Each has the same shape of answer. You keep one extra variable — an accumulator — that remembers what you have found so far. You set it before the loop, update it as you look at each value, and read it once the loop ends. One walk across the sequence, one variable carried along: that single pattern solves finding a maximum, counting matches, and searching.
Guess before you learn
You will scan a list of test scores to find the highest one, carrying a variable best. What should best hold before the loop looks at anything?
Start best at the first value. Starting at 0 quietly breaks the moment every value is negative — the true maximum might be -3, which is less than 0, so 0 would win wrongly. Leaving best undefined crashes on the first comparison. If you picked 0, keep that pencil mark: choosing the starting value is where most maximum bugs are born, and it is the first thing the next section pins down.
9–12
3–5
An accumulator is a variable that remembers what you have found so far. To find the biggest number, start it at the first number. Then look at each number in turn: if this one is bigger, keep it instead. When the list runs out, the accumulator holds the biggest. Counting works the same way: start at 0, and add 1 every time a number passes your test.
6–8
An accumulator is a variable you set before a loop and update inside it, so that after the loop it holds your answer. The pattern has three parts: initialize, update each pass, then read. To find a maximum, set best to the first value, then for each value if value > best: best = value; best ends as the largest. To count, set count = 0, then if value passes the test: count = count + 1. To search, set found = False, then if value == target: found = True. Same three-part shape, one pass across the sequence, three different jobs.
9–12
An accumulator carries a running result across a single loop: you initialize it before the loop, revise it from each element, and read it after. The three staple scans share this skeleton. Maximum: seed best with the first element, then if x > best: best = x. Count: seed count = 0, then if test(x): count += 1. Search: seed found = False, then if x == target: found = True — and you may stop early with break once found. Each visits every element at most once, so the work grows linearly with the length. The subtle part is always the seed: the starting value must be correct for a sequence of any contents, including empty or all-negative.
K–2
You want the tallest kid in line. You hold a picture of the tallest so far. Walk the line. Each time someone taller appears, keep their picture instead. At the end, your picture is the tallest of all.
Undergrad
These scans are folds: a single left-to-right traversal reducing a sequence to one summary under an accumulator, with the loop invariant that the accumulator equals the answer for the prefix seen so far. Maximum folds with the binary max and an identity of negative infinity (or the first element); counting folds with + over a predicate's 0/1; membership folds with logical or, and short-circuits with break for expected O(k) on early hits though O(n) worst case. Correct initialization is choosing the fold's identity element so the invariant holds vacuously before the first step — which is exactly why an empty input demands an explicit decision rather than a silent default.
Postgrad
Formally each scan is a catamorphism over the list: foldl (+) 0 . map pred for counts, foldl max e0 for extrema, any (== t) for membership. Correctness is an invariant argument — acc holds the reduction of the consumed prefix — established at initialization (the monoid identity for that operation) and preserved by the step. The maximum's lack of a total identity in a bounded numeric type forces either negative infinity or first-element seeding and a nonempty precondition; conflating that with 0 is the archetypal defect. Short-circuit search weakens the traversal to existential quantification, licensing early exit while leaving the worst case linear. One traversal, one carried value: the shape generalizes to every streaming aggregate.
accumulator
A variable set before a loop and updated on each pass, so that after the loop it holds the result — a running maximum, a running count, or a found flag.
Take the maximum first. Seed best with the first value so it starts as a real candidate. Then walk the rest: on each value, ask if value > best, and when that is true, replace best with the value. Values that are smaller change nothing. By the time the loop reaches the end, best has climbed to the largest value it ever saw, because any value bigger than the running best became the new best the moment you met it. Read best after the loop, and that is your maximum.
Trace the maximum of [3, 9, 2, 7] — the steps fade as you master them
best = 3
9 > 3 is True, so best = 9
2 > 9 is False, so best stays
7 > 9 is False, so best stays
best
Counting reuses the very same skeleton with a different seed and update. Set count = 0 before the loop — zero is the honest starting count, because you have counted nothing yet. Then on each value, test it, and when it passes, do count = count + 1. Values that fail the test leave the count alone. After the loop, count is how many values passed. Searching is the third variation: seed found = False, and on each value ask if value == target: found = True. If you only need a yes-or-no answer, you may break out the instant you set it.
One pass, one carried variable — that is the engine under a surprising amount of everyday code. The three scans differ only in what the accumulator starts as and how each pass revises it: a running best for the maximum, a running tally for the count, a yes-or-no flag for the search. Get the seed right and the update honest, and the answer is waiting when the loop ends. The final folio turns to what happens when it is not waiting — when the program stops with an error — and how to read that error and fix it on purpose.
Practice — new ink and old, interleaved
1.What does this print?
``
nums = [6, 2, 9, 4]
best = nums[0]
for x in nums:
if x > best:
best = x
print(best)
``
2.score = 72. if score >= 90: g='A' / elif score >= 70: g='B' / elif score >= 50: g='C' / else: g='F'. What is g?
3.What does this print?
``
nums = [1, 2, 3]
nums[0] = 9
print(nums)
``
4.What does this print?
``
total = 0
for i in range(4):
total = total + i
print(total)
``
5.What prints?
``
n = 10
if n % 2 == 0:
print('even')
else:
print('odd')
``
6.Review from folio 1: put these lines in the order they run.
- print("Ready?")
- answer = input()
- print("Go!")
7.For nums = [12, 5, 20, 8], what is len(nums)?
8.How many values are below 5?
``
nums = [3, 8, 1, 5, 4]
count = 0
for x in nums:
if x < 5:
count = count + 1
print(count)
``
9.What is the value of 3 > 1 and 2 > 5?
10.Why does if x = 5: raise an error where if x == 5: does not?