Intermediate

Fixed Size Window

In fixed-size window problems, the window length K is given. You slide the window one element at a time, adding the new element and removing the oldest. This gives O(n) time instead of O(n×K) brute force.

Problem 1: Maximum Sum Subarray of Size K

Problem: Given an array of integers and a number K, find the maximum sum of any contiguous subarray of size K.

Example: arr = [2, 1, 5, 1, 3, 2], K = 3 → Output: 9 (subarray [5, 1, 3])

def max_sum_subarray(arr: list[int], k: int) -> int:
    """Find maximum sum of any contiguous subarray of size k.

    Time: O(n), Space: O(1)
    """
    if len(arr) < k:
        return 0

    # Build the first window
    window_sum = sum(arr[:k])
    max_sum = window_sum

    # Slide the window
    for right in range(k, len(arr)):
        window_sum += arr[right] - arr[right - k]
        max_sum = max(max_sum, window_sum)

    return max_sum


# Test
assert max_sum_subarray([2, 1, 5, 1, 3, 2], 3) == 9
assert max_sum_subarray([2, 3, 4, 1, 5], 2) == 7
assert max_sum_subarray([1], 1) == 1
print("All tests passed!")

ML Application: This is exactly how rolling sum features are computed over time series sensor data. Pandas df['col'].rolling(k).sum() uses this pattern internally.

Problem 2: Average of All Subarrays of Size K

Problem: Given an array, find the averages of all contiguous subarrays of size K.

Example: arr = [1, 3, 2, 6, -1, 4, 1, 8, 2], K = 5 → [2.2, 2.8, 2.4, 3.6, 2.8]

def avg_subarrays(arr: list[int], k: int) -> list[float]:
    """Compute the average of every contiguous subarray of size k.

    Time: O(n), Space: O(n-k+1) for output
    """
    result = []
    window_sum = sum(arr[:k])
    result.append(window_sum / k)

    for right in range(k, len(arr)):
        window_sum += arr[right] - arr[right - k]
        result.append(window_sum / k)

    return result


# Test
result = avg_subarrays([1, 3, 2, 6, -1, 4, 1, 8, 2], 5)
assert result == [2.2, 2.8, 2.4, 3.6, 2.8]
print("All tests passed!")

Problem 3: Sliding Window Maximum (LeetCode 239)

Problem: Given an array and a window size K, return the maximum value in each window as it slides from left to right.

Example: nums = [1,3,-1,-3,5,3,6,7], K = 3 → [3,3,5,5,6,7]

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    """Find the maximum in each sliding window of size k.

    Uses a monotonic decreasing deque to maintain candidates.
    Time: O(n), Space: O(k)
    """
    result = []
    dq = deque()  # stores indices, front = index of current max

    for i in range(len(nums)):
        # Remove indices outside the window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove smaller elements from the back
        # (they can never be the max while nums[i] is in the window)
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        # Window is fully formed starting at index k-1
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result


# Test
assert max_sliding_window([1,3,-1,-3,5,3,6,7], 3) == [3,3,5,5,6,7]
assert max_sliding_window([1], 1) == [1]
assert max_sliding_window([9,11], 2) == [11]
print("All tests passed!")

Problem 4: Permutation in String (LeetCode 567)

Problem: Given two strings s1 and s2, return true if s2 contains a permutation of s1.

Example: s1 = "ab", s2 = "eidbaooo" → True ("ba" is a permutation of "ab")

from collections import Counter

def check_inclusion(s1: str, s2: str) -> bool:
    """Check if any permutation of s1 exists as a substring in s2.

    Uses a fixed window of size len(s1) with character frequency matching.
    Time: O(n), Space: O(1) - at most 26 lowercase letters
    """
    if len(s1) > len(s2):
        return False

    k = len(s1)
    s1_count = Counter(s1)
    window_count = Counter(s2[:k])

    if window_count == s1_count:
        return True

    for right in range(k, len(s2)):
        # Add new character
        window_count[s2[right]] += 1

        # Remove oldest character
        left_char = s2[right - k]
        window_count[left_char] -= 1
        if window_count[left_char] == 0:
            del window_count[left_char]

        if window_count == s1_count:
            return True

    return False


# Test
assert check_inclusion("ab", "eidbaooo") == True
assert check_inclusion("ab", "eidboaoo") == False
assert check_inclusion("adc", "dcda") == True
print("All tests passed!")

Problem 5: Repeated DNA Sequences (LeetCode 187)

Problem: Find all 10-letter-long sequences (substrings) that occur more than once in a DNA string.

Example: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" → ["AAAAACCCCC", "CCCCCAAAAA"]

def find_repeated_dna(s: str) -> list[str]:
    """Find all 10-letter DNA sequences that appear more than once.

    Fixed window of size 10 with a hash set for O(1) lookups.
    Time: O(n), Space: O(n)
    """
    if len(s) <= 10:
        return []

    seen = set()
    repeated = set()

    for i in range(len(s) - 9):
        seq = s[i:i + 10]
        if seq in seen:
            repeated.add(seq)
        seen.add(seq)

    return list(repeated)


# Test
result = find_repeated_dna("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT")
assert set(result) == {"AAAAACCCCC", "CCCCCAAAAA"}

result2 = find_repeated_dna("AAAAAAAAAAAAA")
assert result2 == ["AAAAAAAAAA"]
print("All tests passed!")

Optimization: For very long DNA strings, use a rolling hash (Rabin-Karp) instead of storing full 10-character substrings. Map each nucleotide to 2 bits: A=00, C=01, G=10, T=11, and use a 20-bit integer as the hash.

Summary

Problem	Time	Space	Key Technique
Max Sum Subarray	O(n)	O(1)	Running sum
Average Subarrays	O(n)	O(n)	Running sum / k
Sliding Window Max	O(n)	O(k)	Monotonic deque
Permutation in String	O(n)	O(1)	Character frequency map
DNA Sequences	O(n)	O(n)	Hash set / rolling hash