Sliding Window

Process subarrays in O(n) by maintaining a window that slides through the data

Say you want the biggest sum of three numbers in a row. You could add up every group of three from scratch. But look what you are wasting: when you move one step over, two of the three numbers are the same as before. You are re-adding them for no reason.
The sliding window trick fixes that. Think of a window frame that covers three numbers and glides along the row. Each time it slides one step, you drop the number that left and add the number that entered. One subtraction, one addition, and you have the new sum. No re-adding the whole group. Slide it below and watch.

That small saving is the whole win: it turns a slow re-add-everything loop into a fast single pass, O(n).
The window above stays a fixed size (three). Sometimes you want the window to breathe instead: grow it while things are still okay, shrink it when a rule breaks. That is a variable window, and it solves questions like "the longest stretch with no repeated letter". Same idea, one moving frame, you just also decide when to stretch or squeeze it.

Fixed window, max sum subarray of size kpython

def max_sum_subarray(nums, k):
    """Maximum sum of any subarray of size k. O(n) time."""
    window_sum = sum(nums[:k])
    max_sum = window_sum

    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]  # Add new, remove old
        max_sum = max(max_sum, window_sum)

    return max_sum

print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))  # → 9 (5+1+3)

Variable window, longest substring without repeating characterspython

def length_of_longest_substring(s):
    seen = {}
    left = max_len = 0

    for right, char in enumerate(s):
        if char in seen and seen[char] >= left:
            left = seen[char] + 1  # Shrink window past the duplicate
        seen[char] = right
        max_len = max(max_len, right - left + 1)

    return max_len

print(length_of_longest_substring("abcabcbb"))  # → 3 (abc)

🤔Quick Check

When should you use a variable (not fixed) sliding window?

Practice Exercises

0/1 solved

Exercise 1 of 1hard

⏱ 00:00

Minimum Window Substring

Find the minimum window in s that contains all characters of t.
Expected output: BANC

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next