Sliding Window Technique

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 3 Time to complete: ~25 minutes

What Sliding Window Solves
Fixed-Size Window
Worked Example: Max Sum Subarray of Size K
Variable-Size Window
Worked Example: Longest Substring Without Repeating Characters
Worked Example: Smallest Subarray With Sum ≥ Target
Recognizing When to Reach for Sliding Window
Summary & Next Steps

1. What Sliding Window Solves

Sliding window is a specialization of two-pointer for problems about contiguous subarrays or substrings. The brute-force approach recomputes something (a sum, a set of characters) for every possible window from scratch — O(n²) or worse. Sliding window instead maintains a running window and updates it incrementally as it moves, doing O(1) work per step for O(n) total.

2. Fixed-Size Window

The window has a constant size k and slides one step at a time: as it moves, one element leaves on the left and one enters on the right.

items = [2, 4, 1, 5, 3], k = 3

[2, 4, 1] 5  3     window sum = 7
 2 [4, 1, 5] 3     window sum = 10   (drop 2, add 5)
 2  4 [1, 5, 3]    window sum = 9    (drop 4, add 3)

3. Worked Example: Max Sum Subarray of Size K

def max_sum_subarray(items, k):
    window_sum = sum(items[:k])       # O(k) once, to build the first window
    max_sum = window_sum
 
    for i in range(k, len(items)):
        window_sum += items[i] - items[i - k]   # add new, remove old — O(1)
        max_sum = max(max_sum, window_sum)
 
    return max_sum
    # O(n) time, O(1) space — vs. O(n*k) recomputing each window's sum from scratch

The brute-force version recomputes sum(items[i:i+k]) for every starting position — that's O(k) work, n times, giving O(n*k). Sliding window instead updates the running sum in O(1) per step by subtracting the element that just left and adding the one that just entered.

4. Variable-Size Window

The window's size isn't fixed — it grows by moving a right pointer forward, and shrinks by moving a left pointer forward whenever a condition is violated. This is the shape for "longest/shortest substring or subarray satisfying X" problems.

right expands the window until it breaks a rule
left  contracts the window until the rule holds again

5. Worked Example: Longest Substring Without Repeating Characters

def longest_unique_substring(text):
    seen = set()
    left = 0
    longest = 0
 
    for right in range(len(text)):
        while text[right] in seen:           # rule broken — shrink from the left
            seen.remove(text[left])
            left += 1
        seen.add(text[right])
        longest = max(longest, right - left + 1)
 
    return longest
    # O(n) time — each character is added to `seen` and removed at most once,
    # even though there's a nested while loop

Why this is still O(n), not O(n²): the inner while loop looks like nesting, but left only ever moves forward and never resets — across the entire run of the function, it advances at most n times total. This "amortized" analysis (each pointer makes at most n total moves across the whole loop, not per outer iteration) is a recurring justification for sliding window's linear time, and is worth being able to explain out loud in an interview.

6. Worked Example: Smallest Subarray With Sum ≥ Target

def smallest_subarray_with_sum(items, target):
    left = 0
    current_sum = 0
    smallest_length = float('inf')
 
    for right in range(len(items)):
        current_sum += items[right]
        while current_sum >= target:                     # rule satisfied — try shrinking
            smallest_length = min(smallest_length, right - left + 1)
            current_sum -= items[left]
            left += 1
 
    return smallest_length if smallest_length != float('inf') else 0
    # O(n) time, O(1) space

Notice the mirrored structure: Chapter 5's example shrinks the window when a rule breaks; this one shrinks the window while a rule holds, trying to find the smallest window that still satisfies it. Recognizing which of these two shapes a problem needs is most of the work.

7. Recognizing When to Reach for Sliding Window

Reach for sliding window when the problem mentions:

"Contiguous subarray" or "substring" — sliding window only applies to contiguous ranges, unlike subsets (Module 4).
A fixed size k → fixed-size window.
"Longest" / "shortest" / "smallest window satisfying some condition" → variable-size window.
A brute-force instinct to recompute something for every window — that recomputation is exactly what sliding window eliminates.

8. Summary & Next Steps

Key Takeaways

Sliding window is two-pointer specialized for contiguous subarray/substring problems, turning O(n*k) or O(n²) brute force into O(n).
Fixed-size windows update in O(1) per step by adding the new element and removing the one that just left.
Variable-size windows expand with a right pointer and contract with a left pointer according to a rule — total work is still O(n) because left never moves backward.
The word "contiguous" is the key differentiator from Module 4's subset/permutation problems, which don't require contiguity.

Concept Check

Why is the fixed-size window's running-sum update O(1) instead of O(k)?
In the longest-unique-substring example, why is the algorithm still O(n) despite having a while loop nested inside a for loop?
What's the structural difference between "shrink when a rule breaks" and "shrink while a rule holds"?

Next Chapter

→ Chapter 5: String Operations & Immutability

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index