Sliding Window

No. 12 · SVG · Window frame on a type casefixed size · variable size · Kadane's algorithm

Drag across the window. Click it, then use ← → to step and Space to play.

Two pointers, L and R, mark a window over contiguous elements. Fixed: the window stays k wide; each move adds the new element and drops the oldest. Variable: R keeps expanding to the right, and L moves up to shrink the window whenever it breaks the rule. Either way each pointer only moves forward, at most n times, so the whole scan is O(n) instead of checking every subarray in O(n²). Kadane's algorithm is the same idea with a drastic shrink: keep a running sum of the current window, and if it ever goes negative, drop the whole window and start fresh, because a negative prefix only hurts whatever comes next.

FIG. 12 · The array sits in a type case like on page 1. The red frame is the window: L is the tag above it, R the tag below. A frame turns dashed red when the window breaks the rule and must shrink. The dashed black frame marks the best window so far, and the running values (cur, best, total) are listed on the right. Callout: A the array.

Step 1 / 1
READY
Slides
Extra space
Window
Result
Codemax_sum_k
def max_sum_k(nums, k):            # fixed size k
    cur = sum(nums[:k])
    best = cur
    for R in range(k, len(nums)):
        cur += nums[R] - nums[R - k]   # add the new, drop the oldest
        best = max(best, cur)
    return best

Examples

Variable window · LeetCode 209

target = 7, nums = [2, 3, 1, 2, 4, 3]. For "shortest", the shrink rule flips: grow until the sum reaches the target, then shrink while it still does, recording each length. Answer: 2 ([4, 3]). Trigger: "shortest subarray with sum ≥ …".

O(n) timeO(1) spaceeach pointer moves at most n times
Kadane-style · LeetCode 121

prices = [7, 1, 5, 3, 6, 4]. L is the cheapest buy day so far; a cheaper day restarts the window, just like Kadane drops a negative sum. Answer: 5 (buy at 1, sell at 6).

O(n) timeO(1) spaceone pass, two numbers

Time and space

TechniqueTimeSpaceWhy
Fixed windowO(n)O(1)Each slide is one add and one subtract, instead of re-summing k elements.
Variable windowO(n)O(1), or O(k) with a set or mapR moves n times, L moves at most n times in total (the inner while loop does not make it O(n²)).
Kadane's algorithmO(n)O(1)One pass, two numbers: cur and best.
Brute force: every subarrayO(n²)O(1)n(n + 1)/2 subarrays. The window never revisits a start position.

Why the while loop is still O(n)

It looks nested, but L only ever moves forward and can't pass R. Across the whole run, L moves at most n times in total, so all the inner loops together cost O(n), not O(n) each. That counting argument (amortized, like page 1's dynamic array) is the heart of every sliding window.

Kadane as a window

Kadane keeps the window [start..x] with sum cur. Most windows shrink one step at a time; Kadane's rule is "if the sum is negative, the best window ending later can't include any of it", so L jumps straight past everything. It is also 1-D dynamic programming (page 11): best ending here = max(best ending at the previous element, 0) + x.

Trigger words: when the problem wants a window

Sliding window

  • contiguous subarray
  • substring
  • window of size k
  • longest substring with…
  • shortest substring with…

Fixed size: add one, drop one. Variable: expand R, shrink L while the rule is broken (or, for "shortest", while it holds).

Kadane

  • maximum sum contiguous subarray
  • Maximum Subarray

A running sum that resets when it goes negative.

Template

def max_sum_k(nums, k):            # fixed size k
    cur = sum(nums[:k])
    best = cur
    for R in range(k, len(nums)):
        cur += nums[R] - nums[R - k]   # add the new, drop the oldest
        best = max(best, cur)
    return best

def longest_unique(s):             # variable size
    seen = set()
    L = best = 0
    for R in range(len(s)):
        while s[R] in seen:        # shrink while invalid
            seen.remove(s[L])
            L += 1
        seen.add(s[R])
        best = max(best, R - L + 1)
    return best

# Kadane's algorithm
def max_subarray(nums):
    best = nums[0]                 # not 0: handles all-negative arrays
    cur = 0
    for x in nums:
        cur = max(cur, 0)          # drop a negative running sum
        cur += x
        best = max(best, cur)
    return best