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.
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
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
def minSubArrayLen(target, nums): # LeetCode 209
L, total = 0, 0
best = float('inf')
for R in range(len(nums)):
total += nums[R]
while total >= target: # valid: try to shrink
best = min(best, R - L + 1)
total -= nums[L]
L += 1
return 0 if best == float('inf') else best
def maxProfit(prices): # LeetCode 121
L, best = 0, 0 # L = cheapest day so far
for R in range(1, len(prices)):
if prices[R] < prices[L]:
L = R # a cheaper buy day: restart the window
else:
best = max(best, prices[R] - prices[L])
return best
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 ≥ …".
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).
| Technique | Time | Space | Why |
|---|---|---|---|
| Fixed window | O(n) | O(1) | Each slide is one add and one subtract, instead of re-summing k elements. |
| Variable window | O(n) | O(1), or O(k) with a set or map | R moves n times, L moves at most n times in total (the inner while loop does not make it O(n²)). |
| Kadane's algorithm | O(n) | O(1) | One pass, two numbers: cur and best. |
| Brute force: every subarray | O(n²) | O(1) | n(n + 1)/2 subarrays. The window never revisits a start position. |
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 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.
Fixed size: add one, drop one. Variable: expand R, shrink L while the rule is broken (or, for "shortest", while it holds).
A running sum that resets when it goes negative.
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