2.2 Sliding Window

1. What Is a Sliding Window?

A Sliding Window is a special form of Two Pointers (left and right) that frames a contiguous subarray or substring [left .. right] like a physical window frame sliding across a wall of numbers or characters.

2. Why Do We Need Sliding Window & How Does It Work?

The Pain Without Sliding Window (O(N * K) or O(N^2))

Suppose you have 100,000 numbers and want the highest sum of any 1,000 consecutive numbers. If you compute sum(nums[0..999]) and then start from scratch to compute sum(nums[1..1000]), you just re-added nums[1..999] (999 numbers!) for no reason.

How Fixed-Size Sliding Window Works (O(N))

When a window of size K shifts 1 step right:

• Add the 1 new item entering on the right (+ nums[right]).
• Subtract the 1 old item leaving on the left (- nums[right - K]).

How Variable-Size Sliding Window Works (The Caterpillar Rule)

What if the window size isn't fixed—for example, "Find the longest substring with no repeating characters"?

1. Expand right: Step right forward 1 slot and add s[right] to your window state.
2. Shrink left while invalid: If adding s[right] broke the rule (e.g., created a duplicate), step left forward and remove s[left] in a while loop until the window is valid again.
3. Update Best: Compare right - left + 1 against your best answer.

Because both left and right only move forward from 0 to N - 1, every item enters the window once and leaves at most once — O(N) total time!

Step Through the Visual Drawing: How a Window Slides in O(1)

Click Next below to watch how the window drops the outgoing left element and adds the incoming right element without re-summing the middle:

3. Basic Operations & Walkthroughs (All 4 Languages)

# 1. Fixed-Size Window: Maximum sum of any subarray of length k
def max_sum_k(nums: list[int], k: int) -> int:
  win_sum = sum(nums[:k])
  best = win_sum
  for right in range(k, len(nums)):
      win_sum += nums[right] - nums[right - k]
      best = max(best, win_sum)
  return best

# 2. Variable-Size Window: Longest Substring Without Repeating Characters
def length_of_longest_substring(s: str) -> int:
  last_seen = {}
  left = best = 0
  for right, ch in enumerate(s):
      if ch in last_seen and last_seen[ch] >= left:
          left = last_seen[ch] + 1
      last_seen[ch] = right
      best = max(best, right - left + 1)
  return best

left = 0
for right, x in enumerate(nums):
  add_to_window(x)
  while window_breaks_rule():
      remove_from_window(nums[left])
      left += 1
  best = max(best, right - left + 1)

5. Practice On Your Own (Curated Submodule Problems)