Best total over k consecutive days

Sliding window Junior Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Fill the blank

Fill the blank so each step costs O(1).

Python 3.13
sales, k = [3, -1, 4, 1, -5, 9], 3
window = sum(sales[:k])
best = window
for i in range(k, len(sales)):
    window += ____
    best = max(best, window)
print(best)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A sales[i] - sales[i - k]

Right: add the day entering and remove the day leaving.

Totals are 6, 4, 0 and 5, so the first window is the best here.

Why not the others?
  • B sales[i]. Then the window never forgets old days and keeps growing.
  • C sales[i] - sales[i - 1]. That removes the previous day, not the one leaving a window of size k.

30-second answer

Sum the first k days, then slide: add the day entering and subtract the day leaving. Each slide is O(1), so the whole scan is O(n) instead of O(n·k) for re-summing every window. Keep the best total seen. Summing a slice for the first window uses O(k) extra space (an index loop makes it O(1)).

Practise saying it · 30 s. No recording, just a timer

Explain the fixed-size window.

Say your answer out loud, then check which of these points you covered:

  • Sum the first k
  • Add entering, subtract leaving
  • O(n)

Deep dive

The update window += sales[i] - sales[i - k] is the whole fixed-window technique.

Starting best at the first window (not 0) handles all-negative sales correctly.

Prefix sums give the same O(n) and also answer arbitrary range queries.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def best_k_days(sales: list[int], k: int) -> int:
    window = sum(sales[:k])
    best = window
    for i in range(k, len(sales)):
        window += sales[i] - sales[i - k]
        best = max(best, window)
    return best

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun bestKDays(sales: List<Int>, k: Int): Int {
    var window = 0
    for (i in 0 until k) window += sales[i]
    var best = window
    for (i in k until sales.size) {
        window += sales[i] - sales[i - k]
        best = maxOf(best, window)
    }
    return best
}

Common mistakes

  • Initialising best = 0, which is wrong when every total is negative.
  • Off-by-one on the leaving index: it is i - k, not i - k + 1.

Senior take & follow-ups

Say O(n·k) for the naive version and O(n) for the slide, with the reason.

Follow-up questions

Think of your answer first, then open the hint.

  1. What about the best average?

    Show hint

    Same window; divide the best total by k at the end.

  2. What if you need the window's maximum value instead of its total?

    Show hint

    Use a deque of candidates; see the busiest-hour page in this topic.

What each operation costs: Arrays · Deque

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.