Skip to content
CodeItRaw
Two Pointers & Sliding Window

Lesson 4/4

For "the largest sum of k elements in a row", adding up every window from scratch is wasted work. When the window slides one step only two elements change: one comes in, one goes out.

window = sum(values[:k])
best = window
for i in range(k, len(values)):
    window += values[i] - values[i - k]
    best = max(best, window)
return best
The first window is added up once. After that, at each step add the one coming in on the right and take off the one leaving on the left. However long the list, each element is read at most twice.

The window does not have to be a fixed size. For "the shortest run whose sum is at least key" you grow the window on the right; while the condition holds you shrink it from the left and note the length each time. Both ends only ever move forward.

Tasks

Tasks open in order. Solve them all and the next lesson opens.

This lesson's tasks open when the lessons before it are finished. You can read the explanation now.

  1. 01

    Sliding Window

    Function

  2. 02

    Sales Window

    Function

  3. 03

    Shortest Window

    Function

If you would rather not wait for the order, every problem is open without locks: Problem list