DSA Sliding Window

The sliding window technique looks at a small section of a list, called the window, and slides that section along the data one step at a time. The window reuses most of its previous work, so the program avoids recalculating everything from scratch.

Think about looking through a train window. You see only a short stretch of scenery at any moment. As the train moves, one tree leaves the view and a new tree enters. You never need to rebuild the whole picture. You only update what changed.

The Problem It Solves

Suppose a shop records daily sales: [3, 5, 2, 8, 1, 4]. The owner wants the best total for any 3 consecutive days. A beginner adds up every group of 3 days separately. Each group repeats work that the previous group already did. A sliding window removes that repetition.

Fixed-Size Window

The window keeps the same length at all times. Each slide subtracts the item that leaves and adds the item that enters.

Example: Maximum Sum of k Items

def max_sum(numbers, k):
    window = sum(numbers[:k])
    best = window
    for i in range(k, len(numbers)):
        window += numbers[i]
        window -= numbers[i - k]
        best = max(best, window)
    return best

print(max_sum([3, 5, 2, 8, 1, 4], 3))   # 15

[3, 5, 2] 8, 1, 4     sum = 10
 3 [5, 2, 8] 1, 4     sum = 10 - 3 + 8 = 15
 3, 5 [2, 8, 1] 4     sum = 15 - 5 + 1 = 11
 3, 5, 2 [8, 1, 4]    sum = 11 - 2 + 4 = 13

Best sum = 15

Each item enters the window once and leaves once. The total work stays at O(n), compared with O(n × k) for the repeated-sum approach.

Variable-Size Window

The window grows and shrinks to satisfy a condition. A right pointer expands the window. A left pointer shrinks it when the condition breaks.

Example: Longest Substring Without Repeating Characters

Given the text "abcabcbb", find the longest stretch where no letter repeats.

def longest_unique(text):
    seen = set()
    left = 0
    best = 0
    for right in range(len(text)):
        while text[right] in seen:
            seen.remove(text[left])
            left += 1
        seen.add(text[right])
        best = max(best, right - left + 1)
    return best

print(longest_unique("abcabcbb"))   # 3

Text: a b c a b c b b

[a]            window "a"     size 1
[a b]          window "ab"    size 2
[a b c]        window "abc"   size 3
a is repeated, so shrink from the left
  [b c a]      window "bca"   size 3
  [c a b]      window "cab"   size 3

Best size = 3

The set remembers which letters sit inside the window. Looking up a letter in a set takes O(1) time.

Example: Smallest Subarray With a Target Sum

Find the shortest run of positive numbers whose sum reaches at least a target value.

def smallest_run(numbers, target):
    left = 0
    total = 0
    best = float("inf")
    for right in range(len(numbers)):
        total += numbers[right]
        while total >= target:
            best = min(best, right - left + 1)
            total -= numbers[left]
            left += 1
    return 0 if best == float("inf") else best

print(smallest_run([2, 3, 1, 2, 4, 3], 7))   # 2

The run [4, 3] sums to 7 and has length 2. No shorter run reaches 7.

Spotting a Sliding Window Problem

• The question mentions a subarray or substring.
• The items must sit next to each other.
• The goal asks for a maximum, minimum, longest, or shortest result.
• A brute-force answer would check every possible section.

Fixed Window vs Variable Window

• Fixed window: the problem names the size k, so the window never changes length.
• Variable window: the problem names a condition, so the window stretches and shrinks to match it.

Complexity Summary

• Time: O(n). Each pointer moves across the list once.
• Space: O(1) for number sums, or O(k) when a set or dictionary tracks the window.

Common Mistakes

Beginners often forget to remove the outgoing item, which inflates the window total. Another frequent slip involves moving the left pointer before updating the result. Draw the window on paper for a tiny list and trace each slide by hand. A short trace exposes off-by-one errors quickly.

Key Points

• A window is a continuous section of the data.
• Sliding updates the result by removing one item and adding one item.
• Fixed windows keep a set length, and variable windows adjust to a condition.
• The technique turns O(n²) work into O(n) work.
• Sets and dictionaries help track the contents of a variable window.