Sliding Window

Sliding Window

Eliminate repeated recalculation. Slide a window across the array — add new element, remove old. O(n×k) → O(n).

Fixed Size Window — Max Sum of k Elements
Window Sum: 0
Press Animate to start.

Fixed Window Key Insight

When window slides one step right:
Add arr[right] (new element entering) and subtract arr[right - k] (left element leaving). The left index is always right - k — no need for a separate left variable!
Common Mistake
Computing sum from scratch each step = O(n×k). Using add/subtract = O(n). Always slide, never recompute.
Variable Window — Longest Substring Without Repeats
Window chars in set: {}
Best: 0
Press Animate to start.

Variable Window Strategy

The Two-Pointer Dance
Right pointer: always moves forward (expand). Left pointer: moves forward only when condition is violated (shrink). Current window size = right - left + 1.
When to Shrink
When your condition breaks: "sum exceeds k", "duplicate char found", "more than k distinct chars", etc. Keep shrinking (left++) until condition is restored.
Bug Alert
Never let left > right. If you need a guard, add if left < right before shrinking.

Fixed Window Template

def max_sum_k(arr, k):
    # Build first window
    window = sum(arr[:k])
    best = window

    # Slide: add right element, remove left
    for right in range(k, len(arr)):
        window += arr[right]       # enters
        window -= arr[right - k]   # leaves (left = right-k)
        best = max(best, window)
    return best

Variable Window Template

def length_of_longest(s):
    seen = set()
    left = 0; best = 0
    for right in range(len(s)):
        # shrink from left until no duplicate
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        best = max(best, right - left + 1)
    return best

# Min subarray length with sum >= target
def min_sub_len(target, nums):
    left = total = 0; best = float('inf')
    for right in range(len(nums)):
        total += nums[right]
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]; left += 1
    return best if best != float('inf') else 0

LeetCode Problems

  • EasyMaximum Average Subarray IFixed window
  • MediumLongest Substring Without RepeatingVariable window + Set
  • MediumMinimum Size Subarray SumVariable window, shrink when valid
  • MediumLongest Repeating Character ReplacementVariable window, count max freq
  • MediumPermutation in StringFixed window + Counter
  • HardMinimum Window SubstringVariable window + Counter
  • HardSliding Window MaximumFixed window + Monotonic deque