Array: [1, 3, 2, 6, -1, 4, 1, 8, 2], k=5

Window 1: [1, 3, 2, 6, -1] → Sum = 11
Window 2: [3, 2, 6, -1, 4] → Sum = 14 (remove 1, add 4)
Window 3: [2, 6, -1, 4, 1] → Sum = 12 (remove 3, add 1)

Find smallest subarray with sum ≥ target

Array: [2, 1, 5, 2, 3, 2], target = 7

Expand until sum ≥ 7, then contract from left:
[2, 1, 5] → sum=8 ≥ 7, length=3
[1, 5] → sum=6 < 7, expand
[1, 5, 2] → sum=8 ≥ 7, length=3
[5, 2] → sum=7 ≥ 7, length=2 ← minimum!

from typing import List

def fixed_window(arr: List[int], k: int) -> List[int]:
    """
    Process array with fixed window size k.
    Returns result for each window position.
    
    Time: O(n), Space: O(1)
    
    >>> fixed_window([1, 3, 2, 6, -1, 4, 1, 8, 2], 5)
    [2.2, 2.8, 2.4, 3.6, 2.8]  # averages
    """
    n = len(arr)
    if n < k:
        return []
    
    results = []
    window_sum = sum(arr[:k])  # First window
    results.append(window_sum / k)
    
    for i in range(k, n):
        # Slide: remove leftmost, add rightmost
        window_sum = window_sum - arr[i - k] + arr[i]
        results.append(window_sum / k)
    
    return results


def max_sum_subarray_k(arr: List[int], k: int) -> int:
    """
    Find maximum sum of any contiguous subarray of size k.
    
    Time: O(n), Space: O(1)
    
    >>> max_sum_subarray_k([2, 1, 5, 1, 3, 2], 3)
    9
    >>> max_sum_subarray_k([2, 3, 4, 1, 5], 2)
    7
    """
    if len(arr) < k:
        return 0
    
    # Calculate sum of first window
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Slide window from left to right
    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 variable_window_shrinkable(arr: List[int], condition) -> int:
    """
    Template for finding longest/maximum subarray satisfying condition.
    Window shrinks from left when condition violated.
    
    Pattern: Expand right, shrink left while invalid
    """
    left = 0
    result = 0
    state = initialize_state()
    
    for right in range(len(arr)):
        # Expand window: add arr[right] to state
        update_state_add(state, arr[right])
        
        # Shrink window while condition is violated
        while not is_valid(state, condition):
            update_state_remove(state, arr[left])
            left += 1
        
        # Update result with current valid window
        result = max(result, right - left + 1)
    
    return result


def min_subarray_sum_at_least_target(nums: List[int], target: int) -> int:
    """
    Find minimum length subarray with sum >= target.
    Returns 0 if no such subarray exists.
    
    Time: O(n), Space: O(1)
    
    >>> min_subarray_sum_at_least_target([2, 3, 1, 2, 4, 3], 7)
    2
    >>> min_subarray_sum_at_least_target([1, 4, 4], 4)
    1
    """
    n = len(nums)
    min_length = float('inf')
    window_sum = 0
    left = 0
    
    for right in range(n):
        window_sum += nums[right]
        
        # Shrink window while valid (sum >= target)
        while window_sum >= target:
            min_length = min(min_length, right - left + 1)
            window_sum -= nums[left]
            left += 1
    
    return min_length if min_length != float('inf') else 0

def variable_window_non_shrinkable(arr: List[int], condition) -> int:
    """
    Template for finding exact size or count.
    Window only expands, left moves at most once per iteration.
    
    Useful for: "At most K" problems, exact window counting
    """
    left = 0
    result = 0
    state = initialize_state()
    
    for right in range(len(arr)):
        # Expand window
        update_state_add(state, arr[right])
        
        # Move left pointer if needed (at most once)
        if not is_valid(state, condition):
            update_state_remove(state, arr[left])
            left += 1
        
        # Window size is always right - left + 1
        result = max(result, right - left + 1)
    
    return result


def longest_substring_k_distinct(s: str, k: int) -> int:
    """
    Find longest substring with at most k distinct characters.
    
    Time: O(n), Space: O(k)
    
    >>> longest_substring_k_distinct("eceba", 2)
    3
    >>> longest_substring_k_distinct("aa", 1)
    2
    """
    from collections import defaultdict
    
    char_count = defaultdict(int)
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        char_count[s[right]] += 1
        
        # Shrink window while more than k distinct chars
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
        
        max_length = max(max_length, right - left + 1)
    
    return max_length

from collections import deque

def sliding_window_maximum(nums: List[int], k: int) -> List[int]:
    """
    Return max element in each window of size k.
    Uses monotonic deque for O(n) time.
    
    Time: O(n), Space: O(k)
    
    >>> sliding_window_maximum([1, 3, -1, -3, 5, 3, 6, 7], 3)
    [3, 3, 5, 5, 6, 7]
    """
    if not nums or k == 0:
        return []
    
    dq = deque()  # Store indices, values are decreasing
    result = []
    
    for i in range(len(nums)):
        # Remove elements outside current window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # Remove smaller elements (they can't be max)
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        
        dq.append(i)
        
        # Add to result once we have full window
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

# Trace for [1, 3, -1, -3, 5, 3, 6, 7], k=3:
# i=0: dq=[0]
# i=1: nums[1]=3 > nums[0]=1, pop 0, dq=[1]
# i=2: dq=[1, 2], result=[3]
# i=3: dq=[1, 2, 3], but 1 < 3-3+1=1, pop 1, dq=[2, 3], result=[3, 3]
# i=4: nums[4]=5 > all, dq=[4], result=[3, 3, 5]
# i=5: dq=[4, 5], result=[3, 3, 5, 5]
# i=6: nums[6]=6 > all, dq=[6], result=[3, 3, 5, 5, 6]
# i=7: nums[7]=7 > all, dq=[7], result=[3, 3, 5, 5, 6, 7]

def length_of_longest_substring(s: str) -> int:
    """
    Find length of longest substring without repeating characters.
    
    Time: O(n), Space: O(min(m, n)) where m is charset size
    
    >>> length_of_longest_substring("abcabcbb")
    3
    >>> length_of_longest_substring("bbbbb")
    1
    >>> length_of_longest_substring("pwwkew")
    3
    """
    char_index = {}  # char -> last seen index
    left = 0
    max_length = 0
    
    for right, char in enumerate(s):
        # If char seen and within current window
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        
        char_index[char] = right
        max_length = max(max_length, right - left + 1)
    
    return max_length

# Trace for "abcabcbb":
# right=0, 'a': char_index={a:0}, left=0, len=1
# right=1, 'b': char_index={a:0, b:1}, left=0, len=2
# right=2, 'c': char_index={a:0, b:1, c:2}, left=0, len=3
# right=3, 'a': 'a' at 0 >= left=0, left=1, char_index={a:3, b:1, c:2}, len=3
# right=4, 'b': 'b' at 1 >= left=1, left=2, char_index={a:3, b:4, c:2}, len=3
# right=5, 'c': 'c' at 2 >= left=2, left=3, char_index={a:3, b:4, c:5}, len=3
# right=6, 'b': 'b' at 4 >= left=3, left=5, len=2
# right=7, 'b': 'b' at 6 >= left=5, left=7, len=1
# Result: 3

from collections import Counter

def min_window(s: str, t: str) -> str:
    """
    Find minimum window in s containing all characters of t.
    
    Time: O(|s| + |t|), Space: O(|s| + |t|)
    
    >>> min_window("ADOBECODEBANC", "ABC")
    'BANC'
    >>> min_window("a", "a")
    'a'
    >>> min_window("a", "aa")
    ''
    """
    if not s or not t or len(s) < len(t):
        return ""
    
    # Count chars needed from t
    need = Counter(t)
    required = len(need)  # Unique chars in t
    
    # Window state
    formed = 0  # Unique chars in window with required count
    window_counts = {}
    
    left = 0
    min_len = float('inf')
    result = (0, 0)  # (start, end)
    
    for right in range(len(s)):
        # Add character from right
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1
        
        # Check if frequency matches requirement
        if char in need and window_counts[char] == need[char]:
            formed += 1
        
        # Try to shrink window
        while left <= right and formed == required:
            # Update result if this window is smaller
            if right - left + 1 < min_len:
                min_len = right - left + 1
                result = (left, right)
            
            # Remove leftmost character
            char = s[left]
            window_counts[char] -= 1
            if char in need and window_counts[char] < need[char]:
                formed -= 1
            left += 1
    
    return "" if min_len == float('inf') else s[result[0]:result[1] + 1]

def subarrays_with_k_distinct(nums: List[int], k: int) -> int:
    """
    Count subarrays with exactly K different integers.
    Uses: exactly(k) = atMost(k) - atMost(k-1)
    
    Time: O(n), Space: O(n)
    
    >>> subarrays_with_k_distinct([1, 2, 1, 2, 3], 2)
    7
    >>> subarrays_with_k_distinct([1, 2, 1, 3, 4], 3)
    3
    """
    def at_most_k(nums: List[int], k: int) -> int:
        """Count subarrays with at most k distinct integers."""
        from collections import defaultdict
        
        count = defaultdict(int)
        left = 0
        result = 0
        
        for right in range(len(nums)):
            count[nums[right]] += 1
            
            while len(count) > k:
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    del count[nums[left]]
                left += 1
            
            # All subarrays ending at right with at most k distinct
            result += right - left + 1
        
        return result
    
    return at_most_k(nums, k) - at_most_k(nums, k - 1)

# For [1, 2, 1, 2, 3], k=2:
# atMost(2) = 12: [1], [2], [1], [2], [3], [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]
# atMost(1) = 5: [1], [2], [1], [2], [3]
# exactly(2) = 12 - 5 = 7

def subarray_sum_equals_k(nums: List[int], k: int) -> int:
    """
    Count subarrays with sum equal to k.
    Note: Uses prefix sum + hashmap, not pure sliding window
    (because array can have negative numbers).
    
    Time: O(n), Space: O(n)
    
    >>> subarray_sum_equals_k([1, 1, 1], 2)
    2
    >>> subarray_sum_equals_k([1, 2, 3], 3)
    2
    """
    count = 0
    prefix_sum = 0
    prefix_count = {0: 1}  # Empty prefix has sum 0
    
    for num in nums:
        prefix_sum += num
        # If (prefix_sum - k) exists, we found subarrays
        if prefix_sum - k in prefix_count:
            count += prefix_count[prefix_sum - k]
        prefix_count[prefix_sum] = prefix_count.get(prefix_sum, 0) + 1
    
    return count

def character_replacement(s: str, k: int) -> int:
    """
    Longest substring where you can replace at most k characters
    to make all characters the same.
    
    Time: O(n), Space: O(26) = O(1)
    
    >>> character_replacement("ABAB", 2)
    4
    >>> character_replacement("AABABBA", 1)
    4
    """
    count = {}
    left = 0
    max_count = 0  # Count of most frequent char in window
    result = 0
    
    for right in range(len(s)):
        count[s[right]] = count.get(s[right], 0) + 1
        max_count = max(max_count, count[s[right]])
        
        # Window size - max_count = chars to replace
        # If > k, shrink window
        while right - left + 1 - max_count > k:
            count[s[left]] -= 1
            left += 1
        
        result = max(result, right - left + 1)
    
    return result

def total_fruit(fruits: List[int]) -> int:
    """
    Find longest subarray with at most 2 distinct values.
    
    Time: O(n), Space: O(1)
    
    >>> total_fruit([1, 2, 1])
    3
    >>> total_fruit([0, 1, 2, 2])
    3
    >>> total_fruit([1, 2, 3, 2, 2])
    4
    """
    basket = {}
    left = 0
    max_fruits = 0
    
    for right, fruit in enumerate(fruits):
        basket[fruit] = basket.get(fruit, 0) + 1
        
        while len(basket) > 2:
            basket[fruits[left]] -= 1
            if basket[fruits[left]] == 0:
                del basket[fruits[left]]
            left += 1
        
        max_fruits = max(max_fruits, right - left + 1)
    
    return max_fruits

# WRONG: Window size calculation
length = right - left  # Missing + 1

# CORRECT
length = right - left + 1

def fixed_window_safe(arr: List[int], k: int) -> List[int]:
    if not arr or k <= 0 or k > len(arr):
        return []
    # ... rest of implementation

# WRONG
while condition:
    left += 1  # Forgot to update state!

# CORRECT
while condition:
    window_state.remove(arr[left])
    left += 1

# Sliding window for sum problems only works with positive numbers
# For arrays with negative numbers, use prefix sum + hashmap