Arrays

Sliding Window

TimeO(n) SpaceO(1)

Think of looking through a train window. As the train moves, new scenery enters on one side and old scenery leaves on the other. You always see a continuous section of landscape. Instead of photographing the entire route, you just note what enters and exits your view.

When to use it: You need to find or compute something over all contiguous subarrays/substrings of a certain size, or find the smallest/largest window satisfying a constraint.

Key insight: Instead of recomputing from scratch for every window position, add the new element and remove the old one — turning O(n*k) into O(n).

Common trap: Forgetting to shrink the window. In variable-size windows, the left boundary must advance when the window constraint is violated.

# Fixed-size sliding window: max sum of subarray of size k
function maxSumSubarray(arr, k):
    windowSum = sum of arr[0..k-1]          # initialize first window
    maxSum = windowSum

    for i = k to length(arr) - 1:
        windowSum = windowSum + arr[i] - arr[i - k]   # slide: add new, remove old
        maxSum = max(maxSum, windowSum)

    return maxSum

# Variable-size sliding window: smallest subarray with sum >= target
function minSubarrayLen(arr, target):
    left = 0
    windowSum = 0
    minLen = infinity

    for right = 0 to length(arr) - 1:
        windowSum = windowSum + arr[right]      # expand window

        while windowSum >= target:              # shrink while valid
            minLen = min(minLen, right - left + 1)
            windowSum = windowSum - arr[left]
            left = left + 1

    return minLen if minLen != infinity else 0

def max_sum_subarray(arr: list[int], k: int) -> int:
    """Maximum sum of any subarray of size k."""
    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum


def min_subarray_len(arr: list[int], target: int) -> int:
    """Smallest subarray with sum >= target. Returns 0 if none."""
    left = 0
    window_sum = 0
    min_len = float("inf")

    for right in range(len(arr)):
        window_sum += arr[right]

        while window_sum >= target:
            min_len = min(min_len, right - left + 1)
            window_sum -= arr[left]
            left += 1

    return min_len if min_len != float("inf") else 0


def longest_unique_substring(s: str) -> int:
    """Length of the longest substring without repeating characters."""
    seen = {}
    left = 0
    max_len = 0

    for right, char in enumerate(s):
        if char in seen and seen[char] >= left:
            left = seen[char] + 1
        seen[char] = right
        max_len = max(max_len, right - left + 1)

    return max_len

Problem: Given a string, find the length of the longest substring without repeating characters.

How would you approach this?

Answer: This is a variable-size sliding window problem. Expand the right boundary to include new characters. When a duplicate is found, shrink from the left until the window is valid again. Track characters with a hash map.

Problem: Given an array of positive integers and an integer k, find the maximum sum of any contiguous subarray of size k.

How would you approach this?

Answer: This is a fixed-size sliding window problem. Compute the sum of the first k elements, then slide by adding the next element and subtracting the element that just left the window. Track the maximum sum seen.

Time: O(n) because each element is added to the window exactly once and removed at most once. Even though there is a while loop inside the for loop, the left pointer only moves forward, so total work across all iterations is linear.

Space: O(1) for fixed-size windows with numeric sums. For variable-size windows tracking characters or frequencies, space is O(k) where k is the alphabet or distinct element count — often O(1) for bounded alphabets like ASCII.