Editor

Sliding window in Python

The sliding window technique finds the largest sum of k neighbouring values by moving a window of size k along the list, adding the value that enters and subtracting the one that leaves.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. Add up the first k values once: that is the first window.
  2. Slide the window one step right: add the value that enters, nums[right], and subtract the one that just left, nums[left - 1].
  3. Each slide costs one addition and one subtraction instead of a fresh sum of k values.
  4. Keep the biggest window sum seen so far in best.

What to watch

  • Watch left and right move together, always k - 1 apart.
  • Watch window change by only the bar that enters and the bar that leaves.
  • Watch best settle at 16 once the window covers 6, 8 and 2: no later window beats it.

The code

def max_window_sum(nums, k):
    window = sum(nums[:k])      # sum of the first k values
    best = window
    for right in range(k, len(nums)):
        left = right - k + 1    # the window is nums[left] to nums[right]
        window += nums[right] - nums[left - 1]   # add the new, drop the old
        best = max(best, window)
    return best

data = [3, 1, 6, 8, 2, 4, 1, 5]
print(max_window_sum(data, 3))
Output
16

Open it in the editor