parikshan

maximum-average-subarray-i

Difficulty: Easy  ·  Topic: Sliding Window  ·  Practice it on parikshan: /practice/maximum-average-subarray-i/start

The story

A network operations team at Cloudflare watches request latency in second-by-second buckets. They do not care about a single anomalous second. They care about the worst 30-second window of the day. If the average latency over any 30-second stretch goes above their SLA, the on-call engineer pages. Their dashboard reads from a stream of latency numbers and must compute, every second, the average of the last 30 values, then take the maximum of all those averages.

That is maximum-average-subarray-i. Exact same shape: find the contiguous window of length k whose average is highest.

What's actually being asked

Given an integer array nums of length n and an integer k, find a contiguous subarray of length exactly k whose average is maximum. Print the answer as a floating-point number with five decimal places.

Since k is fixed, "maximum average" and "maximum sum" are the same question; dividing by k is a constant transformation. So we look for the maximum sum of any k-length subarray.

The naive approach

For every starting index i from 0 to n-k, sum nums[i .. i+k-1] and track the maximum. The inner sum is O(k), the outer loop is O(n-k+1), so the total is O(n * k). For n = 10^5 and k = 5 * 10^4, that is 5 billion operations. Will time out.

The key insight

When the window slides one step right, you do not need to recompute the sum from scratch. The new sum is the old sum, minus the element that just left, plus the element that just entered. Two arithmetic operations instead of k. The total work drops to O(n).

This is the fixed-size sliding window pattern, and it is the cleanest expression of it in the whole canon. Every variable-size variant builds on the rhythm you learn here.

Step-by-step approach

  1. Compute the sum of the first k elements. Call it cur. Set best = cur.
  2. For i from k to n-1:
    • cur = cur + nums[i] - nums[i - k].
    • best = max(best, cur).
  3. Print best / k with five decimal places.

Worked example

nums = [1, 12, -5, -6, 50, 3]
k = 4
  • Initial window [1, 12, -5, -6], sum = 2. best = 2.
  • Slide: add nums[4]=50, remove nums[0]=1. New sum = 2 + 50 - 1 = 51. best = 51.
  • Slide: add nums[5]=3, remove nums[1]=12. New sum = 51 + 3 - 12 = 42. best unchanged.
  • End. Max sum = 51, max average = 51 / 4 = 12.75000.

Complexity

  • Time: O(n), one pass.
  • Space: O(1), two integer counters.

The brute force is O(n * k). The sliding window converts the k-factor into a single +/- per slide. That conversion is the whole pattern.

Common pitfalls

  • Returning the maximum sum instead of the maximum average: do not forget the final division by k, and print with exactly five decimal places (f"{ans:.5f}"). Bytes are matched exactly; trailing zeros must be present.
  • Integer division: in Python this is rare, but in C++/Java casting matters. Use a float divisor.
  • Recomputing the sum every iteration: defeats the whole purpose. The slide-by-one update is the optimisation.
  • Off-by-one on the window boundary: the element leaving is nums[i - k], not nums[i - k + 1]. Walk through the indices on paper once and the bug never returns.

Where this shows up in the enterprise

  • Cloudflare / Fastly / Akamai: rolling-window latency and error-rate SLAs.
  • Datadog / New Relic / Splunk: moving-average metrics widgets, every dashboard chart has one.
  • AWS CloudWatch / GCP Monitoring: 5-minute and 15-minute rolling averages on every metric.
  • NYSE / NASDAQ market data: simple moving averages on tick streams for indicator computation.
  • Bloomberg / Refinitiv terminals: rolling N-day price averages on every quote.
  • Strava / Garmin / Whoop: rolling heart-rate and pace averages over the last N samples of a workout.
  • Netflix / Hulu CDN: rolling bandwidth averages to decide adaptive bitrate switches.
  • Twilio / SendGrid: rolling delivery-rate averages per route.

The common thread: a stream, a fixed window, and an aggregate that updates incrementally. That is sliding window.

Variants you'll see elsewhere

  • best-time-to-buy-and-sell-stock: a window of variable length where the "aggregate" is max - min.
  • minimum-size-subarray-sum: variable window growing right, shrinking left, target on the sum.
  • sliding-window-maximum: same fixed window, but the aggregate is max, which needs a monotonic deque.
  • find-all-anagrams-in-a-string: fixed window over a string, the aggregate is a letter frequency map.
  • Streaming statistics: rolling variance, rolling median, rolling top-k.

Each variant changes the aggregate or the window-sizing rule. The walking-pointer rhythm stays.

How parikshan turns this into a learning loop

This problem is the perfect first sliding-window submission on parikshan because the dynamic private tests will include:

  • A k = n test (whole array is the single window, make sure your loop doesn't run zero times).
  • A k = 1 test (every element is its own window).
  • An all-negative array (the maximum average can be negative; do not initialise best to zero).
  • Large n near the constraint limit (proves you implemented the slide-by-one, not the recompute).

If you fail one, you learn the boundary your code missed. The integrity score rewards solving these without taking hints, because the next problem in the cluster reuses the same rhythm. The AI sparring partner in practice mode is the right place to ask "why is the slide-by-one update O(1) and not amortised?" before you sit in exam mode and burn integrity points for the same question.

In the AI-integrated workspace

When an agent generates rolling-aggregate code for a real metrics pipeline, your review reduces to four checks:

  1. Is the initial window computed before the slide loop, or does the loop have a special first-iteration branch? (Either is fine; agents often write the second and introduce off-by-ones.)
  2. Is the slide update add new then remove old, with the correct indices nums[i] and nums[i-k]?
  3. Is the running aggregate using an arithmetic identity that is exact (sum) or one that drifts (running average with division)? Float accumulation of a running average drifts; the sum-then-divide approach does not.
  4. Does the answer record happen after the slide update, not during it?

Engineers who recognise that "rolling average" code paths almost always need a fixed-size sliding window are the ones who catch agent-generated O(n*k) regressions before they hit production. parikshan is built to make that recognition reflex.