Tracking the Best So Far

Concepts covered: Frequency Counting

Plenty of questions want one winner: the busiest day, the longest streak, the biggest jump. One approach builds a list of every candidate and calls max at the end. A tighter one keeps only the best candidate found so far and updates it as each item passes, so its memory stays the same size whether it reads 10 days or 10 years.

A running maximum that remembers where

minutes = [42, 18, 77, 77, 30]
best = minutes[0]
best_day = 0
for day, m in enumerate(minutes):
    if m > best:
        best = m
        best_day = day
print(best, best_day)

Output:

77 2

Day 2 and day 3 both reach 77, and the strict > keeps the first, printing 77 2. Change it to >= and the later tie replaces the earlier one, printing 77 3. The comparison operator is a decision about ties, so choose it on purpose.

What does this print?

plays = [5, 9, 3, 9, 1]
best = plays[0]
best_hour = 0
for hour, p in enumerate(plays):
    if p >= best:
        best = p
        best_hour = hour
print(best, best_hour)

• 9 3, because >= lets the later 9 replace the earlier one
• 9 1, because the first 9 is kept and the second is ignored
• 5 0, because best starts at plays[0] and never changes
• 9 4, because best_hour tracks the last hour the loop visits

Remembering 2 values at once

The biggest rise in daily listeners, from an earlier day to a later one, depends on a pair of days. Subtracting the overall minimum from the overall maximum gives the wrong answer when the peak comes before the trough. Keep 2 running values instead: lowest, the smallest count seen so far, and best_gain, the largest rise found so far. Each new day is measured against the lowest day before it.

listeners = [120, 160, 95, 140, 88, 130]
lowest = listeners[0]
best_gain = 0
for count in listeners[1:]:
    best_gain = max(best_gain, count - lowest)
    lowest = min(lowest, count)
print(best_gain)
print(max(listeners) - min(listeners))

45
72

The loop prints 45, the rise from 95 on day 2 to 140 on day 3. The naive 72 pairs 160 on day 1 with 88 on day 4, a drop in time order, so that rise never happened.

The starting value is part of the answer

Starting best at 0 looks harmless until every value is negative:

changes = [-5, -2, -9]
best = 0
for c in changes:
    if c > best:
        best = c
print(best)

best = changes[0]
for c in changes[1:]:
    if c > best:
        best = c
print(best)

Output:

0
-2

The first loop reports 0, a value that never appears in the list. Starting from changes[0] makes the first real item the first candidate. On an empty list that start raises IndexError, which is usually right: an empty list has no best value, and a guard clause before the loop can say so in its own words. The rise loop starts best_gain at 0 on purpose, meaning 'no rise found'.

The best run, built from the current run

Some winners are runs, such as the longest stretch of consecutive days with any listening. Keep current, the length of the run that ends today, and longest, the best run so far. A listening day extends current and offers it to longest; a silent day resets current to 0.

days = [30, 0, 12, 45, 9, 0, 5, 8]
current = 0
longest = 0
for m in days:
    if m > 0:
        current += 1
        longest = max(longest, current)
    else:
        current = 0
print(longest)

Output:

3

The winning run is 3 days long. It starts with 12 minutes and 45 minutes and ends on a 9-minute day. The same 2-variable shape finds the largest total over any consecutive run when values can be negative. Now current is the best total of a run ending exactly at this item, and that run has 2 choices: extend the run that ended at the previous item, or start fresh here. A run whose total is negative only drags down whatever follows it, so when current is negative the next run starts over at the new value. That is current = max(value, current + value). The winning run can end at any item, so best = max(best, current) keeps the largest current seen.

About this lesson

This section is part of the Problem Solving: Advanced lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.