Walking a list

You have a week of daily order counts: [12, 30, 7, 25]. Which day was busiest? In SQL you would write SELECT MAX(orders), and in Python you could call max(orders). Both are fine at work.

In an interview, the question is almost never the plain maximum. It is the busiest day, or the biggest jump between two days, or the longest streak of busy days. No built-in function answers those. What answers them is a short loop that walks the list and keeps a few notes, and that loop is the most important program in this course. Every pattern later on, from hash maps to dynamic programming, is this same loop with a smarter notebook.

So we start here, slowly, and we watch every step.

#One item at a time

A for loop takes the items of a list one at a time, in order, and runs the indented lines once for each. Here is the smallest version. The trace below shows the code on one side and every name and value on the other. Press Next to move one line at a time.

▶1orders = [12, 30, 7, 25]
2for x in orders:
3    print(x)
4print("done")

(nothing printed yet)

Three things to notice, because they cause most loop confusion:

• x is a name, not a box in the list. Each pass, Python points x at the next item. Writing x = 0 inside the loop would change what x names, not the list.
• The body is whatever is indented under the for line. Line 4 is not indented, so it runs once, after the loop.
• The loop decides when to stop. You do not count; it runs out of items.

Before you run the next one, predict it.

nums = [3, 1, 4]
for x in nums:
    print(x * 2)
print("end")

#A notebook that remembers

Printing each item is not useful by itself. The useful loops remember something as they go. Total orders for the week: we need one number that grows as we walk.

▶1orders = [12, 30, 7, 25]
2total = 0
3for x in orders:
4    total = total + x
5print(total)

(nothing printed yet)

Read line 4 the way Python does: compute the right side first, then point the name on the left at the answer. total = total + x is not an equation (it would be false); it is an instruction: "the new total is the old total plus x". Python has a shorthand for exactly this, total += x, and you will see both.

The idea that makes loops easy to get right is the promise. At the end of every pass, something is true about the notebook. Here:

Check it against the trace: after two passes, total is 42, and the items visited so far are 12 and 30. When the loop ends, the items visited so far are all of them, so the promise turns into the answer. You will use this argument for every algorithm in this course.

Counting is the same loop with a condition. How many days had more than 20 orders? The notebook is a count, and it only grows when the item passes the test:

count = 0
for x in orders:
    if x > 20:
        count += 1

The promise: after each pass, count is how many visited items were above 20. With [12, 30, 7, 25] that ends at 2.

Now put a counting loop together yourself. The lines are all here, in the wrong order.

#The running maximum

Back to the question we started with: the busiest day. The notebook is one number, best, the largest count seen so far. Each pass asks one question: is this item bigger than the best so far? If yes, it becomes the new best.

Before you step through, guess: how many times does best change on [3, 8, 2, 9, 4]?

▶1def largest(nums):
2    best = nums[0]
3    for x in nums:
4        if x > best:
5            best = x
6    return best

(nothing printed yet)

Here is the whole idea in the four questions this course asks of every algorithm:

Why start at nums[0]? Because the promise must be true before the loop starts, and the only number we can vouch for at that moment is the first. It is tempting to start at 0. That works for order counts, which are never negative, and fails quietly for anything else:

def largest(nums):
    best = 0
    for x in nums:
        if x > best:
            best = x
    return best

One more question an interviewer wants you to ask out loud: what if the list is empty? nums[0] raises an error on []. There is no right answer in the abstract; you ask ("can the list be empty, and what should I return then?") and handle it with one if at the top. Asking is part of the score.

Now write the mirror image yourself.

#When you need the position

Often the question is not the largest value but where it is: which day was busiest? for x in nums hands you the items but not their positions. Two tools give you positions.

range(n) produces the whole numbers 0, 1, ..., n − 1. So range(len(nums)) produces every valid position of nums, and nums[i] reads the item there. Notice that range stops before n: range(4) is 0, 1, 2, 3, which is exactly the positions of a four-item list.

▶1orders = [12, 30, 7, 25]
2best_day = 0
3for i in range(len(orders)):
4    if orders[i] > orders[best_day]:
5        best_day = i
6print(best_day)

(nothing printed yet)

Positions start at 0. "The second day" is position 1. Keep that translation in your head; off-by-one mistakes come from forgetting it.

enumerate gives you both at once. for i, x in enumerate(orders) gives i = 0, x = 12, then i = 1, x = 30, and so on. Use it when you need the position and the item together; it reads better than orders[i] everywhere. (The i, x on the left is unpacking two values into two names; lesson 4 shows how it works.)

Positions also let you look at neighbors. The biggest jump from one day to the next compares orders[i] with orders[i - 1], so the walk must start at position 1, not 0: range(1, len(orders)). range(a, b) starts at a and stops before b.

orders = [12, 30, 7, 25]
for i in range(1, 4):
    print(i, orders[i] - orders[i - 1])

Here is a full problem that uses a running total and builds a new list as it walks. Try it before you open the hints.

#While loops: walking at your own pace

A for loop moves exactly one item per pass. A while loop moves whenever and however you tell it to. It checks a condition before every pass and stops the first time the condition is false.

Use it when the walk is not "every item once": stopping as soon as you find something, or moving two pointers at different speeds (module 4). Here we find the first day with more than 20 orders and stop there:

▶1orders = [12, 7, 30, 25]
2i = 0
3while i < len(orders) and orders[i] <= 20:
4    i += 1
5print(i)

(nothing printed yet)

The order inside the condition matters. i < len(orders) is checked first, and and stops as soon as one side is false. If no day were busy, i would reach 4, the first check would fail, and Python would never try orders[4], which does not exist.

The last problem needs two notebook values at once: the length of the current streak, and the best streak so far. It is a classic warm-up, and warm-ups matter: the research on these rounds says a fast, clean first problem banks time for the harder follow-up.

Last, practice saying it. The words you write here are the words you will say in the room.