Sliding Window

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

The sliding window technique maintains a "window" (contiguous subarray/substring) and slides it through the data. Instead of recomputing from scratch each time, you add/remove elements at the boundaries.
Fixed window: size k stays constant, slide to find max/min/sum.Variable window: expand when valid, shrink when invalid.

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