The Rolling Peak

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4

Problem

A monitoring export hands you per-minute throughput readings in nums, and you want the busiest sustained stretch of exactly k consecutive minutes. Return the highest average over any contiguous block of k readings, which can run negative when traffic dips below baseline. Return None when there are fewer than k readings to fill a single block.

The sweetest stretch in the sequence.

Example 1

Input:

nums = [1,12,-5,-6,50,3], k = 4

Output:

12.75

Example 2

Input:

nums = [-1,-2,-3,-4], k = 2

Output:

-1.5

Worked solution and explanation

What this really is

Strip off the throughput costume and this is the maximum mean over every fixed-width block of the sequence. There is no shortcut scalar hiding here: the winning block is not the largest single reading and not the overall average, so you have to evaluate each of the k-wide windows and compare them. Three things separate a correct answer from a plausible-looking one: guard the short input before you divide, never clamp a negative window up to zero, and land the window on exactly k readings. Miss the sign rule and an all-quiet stretch reports 0 instead of its true negative peak; miss the guard and short input divides by a block that was never filled.

How a senior gets there

Step 1: Guard the short input

Fewer than k readings means no window can ever fill, so bail with None before touching any sums. Resolve this first: get it wrong and your loop bounds underflow on short input.

Step 2: Seed from a real window

Sum the first k readings once and make that your running best. Seeding the best from a real window (not 0, not a negative-infinity guess) is what keeps an all-negative input honest: it returns its least-bad stretch instead of a fabricated zero.

Step 3: Edit, do not rebuild

Stepping the window one slot right means exactly two readings change: the one falling off the left leaves, the new one on the right enters. Add the entering value, subtract the leaving value, and you have the next window sum in two operations instead of k.

Step 4: Divide last

Track the best sum as you slide, then divide by k exactly once at the end. Dividing inside the loop is wasted work since the divisor never changes, and comparing sums instead of averages avoids float noise mid-scan.

The solution

Sliding window with incremental sum update
def max_avg_subarray(nums, k):
    if len(nums) < k:
        return None
    window_sum = sum(nums[:k])
    best_sum = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        if window_sum > best_sum:
            best_sum = window_sum
    return best_sum / k

Common follow-up questions