Advanced Sliding Window Techniques

Monotonic Deque Pattern

A monotonic deque maintains elements in increasing or decreasing order, perfect for tracking min/max in sliding windows.

Decreasing Deque (for Maximum)

from collections import deque

def sliding_window_maximum(nums, k):
    """Track maximum in each window"""
    dq = deque()  # Store indices, decreasing values
    result = []

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

        # Maintain decreasing order
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

Key: Front of deque always has index of maximum element.

Increasing Deque (for Minimum)

def sliding_window_minimum(nums, k):
    """Track minimum in each window"""
    dq = deque()  # Store indices, increasing values
    result = []

    for i in range(len(nums)):
        while dq and dq[0] <= i - k:
            dq.popleft()

        # Maintain increasing order
        while dq and nums[dq[-1]] > nums[i]:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

Problem 1: Shortest Subarray with Sum ≥ K

Challenge: Handle negative numbers (can't just shrink greedily).

from collections import deque

def shortest_subarray(nums, k):
    """Works with negative numbers"""
    n = len(nums)
    prefix = [0]

    # Build prefix sums
    for num in nums:
        prefix.append(prefix[-1] + num)

    dq = deque()  # Store indices
    min_len = float('inf')

    for i in range(n + 1):
        # Check if we can form valid subarray
        while dq and prefix[i] - prefix[dq[0]] >= k:
            min_len = min(min_len, i - dq.popleft())

        # Maintain increasing prefix sums
        while dq and prefix[i] <= prefix[dq[-1]]:
            dq.pop()

        dq.append(i)

    return min_len if min_len != float('inf') else -1

print(shortest_subarray([1], 1))           # 1
print(shortest_subarray([1,2], 4))         # -1
print(shortest_subarray([2,-1,2], 3))      # 3

Key: Use prefix sums + monotonic deque for negative numbers.

Problem 2: Constrained Subsequence Sum

Problem: Maximum sum subsequence where consecutive elements are at most k apart.

from collections import deque

def constrained_subset_sum(nums, k):
    """DP + sliding window maximum"""
    dq = deque()  # Store indices of dp values
    dp = [0] * len(nums)

    for i in range(len(nums)):
        # Remove out of range
        while dq and dq[0] < i - k:
            dq.popleft()

        # dp[i] = nums[i] + max(0, max of last k dp values)
        dp[i] = nums[i]
        if dq:
            dp[i] += max(0, dp[dq[0]])

        # Maintain decreasing deque
        while dq and dp[dq[-1]] < dp[i]:
            dq.pop()

        dq.append(i)

    return max(dp)

print(constrained_subset_sum([10,2,-10,5,20], 2))  # 37

Problem 3: Longest Subarray With Limit

Problem: Longest subarray where max - min ≤ limit.

from collections import deque

def longest_subarray(nums, limit):
    max_dq = deque()  # Decreasing
    min_dq = deque()  # Increasing
    left = 0
    max_len = 0

    for right in range(len(nums)):
        # Add to max deque (decreasing)
        while max_dq and nums[max_dq[-1]] < nums[right]:
            max_dq.pop()
        max_dq.append(right)

        # Add to min deque (increasing)
        while min_dq and nums[min_dq[-1]] > nums[right]:
            min_dq.pop()
        min_dq.append(right)

        # Shrink if difference too large
        while nums[max_dq[0]] - nums[min_dq[0]] > limit:
            left += 1
            # Remove if outside window
            if max_dq[0] < left:
                max_dq.popleft()
            if min_dq[0] < left:
                min_dq.popleft()

        max_len = max(max_len, right - left + 1)

    return max_len

print(longest_subarray([8,2,4,7], 4))  # 2
print(longest_subarray([10,1,2,4,7,2], 5))  # 4

Problem 4: Number of Subarrays with Bounded Max

Problem: Count subarrays where max element is in range [left, right].

def num_subarray_bounded_max(nums, left, right):
    def count_at_most(bound):
        """Count subarrays with max ≤ bound"""
        count = 0
        length = 0

        for num in nums:
            if num <= bound:
                length += 1
                count += length
            else:
                length = 0

        return count

    # In range = (at most right) - (at most left-1)
    return count_at_most(right) - count_at_most(left - 1)

print(num_subarray_bounded_max([2,1,4,3], 2, 3))  # 3

Problem 5: Permutation in String

Problem: Check if s2 contains a permutation of s1.

from collections import Counter

def check_inclusion(s1, s2):
    if len(s1) > len(s2):
        return False

    s1_freq = Counter(s1)
    window_freq = {}

    k = len(s1)
    matches = 0

    for i in range(len(s2)):
        # Add right char
        char = s2[i]
        window_freq[char] = window_freq.get(char, 0) + 1

        if char in s1_freq and window_freq[char] == s1_freq[char]:
            matches += 1
        elif char in s1_freq and window_freq[char] == s1_freq[char] + 1:
            matches -= 1

        # Remove left char if window too large
        if i >= k:
            left_char = s2[i - k]
            if left_char in s1_freq and window_freq[left_char] == s1_freq[left_char]:
                matches -= 1
            elif left_char in s1_freq and window_freq[left_char] == s1_freq[left_char] + 1:
                matches += 1

            window_freq[left_char] -= 1

        # Check if permutation found
        if matches == len(s1_freq):
            return True

    return False

print(check_inclusion("ab", "eidbaooo"))  # True
print(check_inclusion("ab", "eidboaoo"))  # False

Problem 6: Find All Anagrams

Problem: Find all start indices of anagrams of p in s.

from collections import Counter

def find_anagrams(s, p):
    if len(p) > len(s):
        return []

    p_freq = Counter(p)
    window_freq = {}
    result = []
    k = len(p)

    for i in range(len(s)):
        # Add char
        char = s[i]
        window_freq[char] = window_freq.get(char, 0) + 1

        # Remove if window too large
        if i >= k:
            left_char = s[i - k]
            window_freq[left_char] -= 1
            if window_freq[left_char] == 0:
                del window_freq[left_char]

        # Check if anagram
        if i >= k - 1 and window_freq == p_freq:
            result.append(i - k + 1)

    return result

print(find_anagrams("cbaebabacd", "abc"))  # [0, 6]

Common Patterns Summary

1. Track Min/Max: Monotonic Deque

# Decreasing deque for max
while dq and nums[dq[-1]] < nums[i]:
    dq.pop()

2. Exact Match: At Most Trick

# Exactly k = At most k - At most (k-1)
return at_most_k(k) - at_most_k(k - 1)

3. Character Frequency: Fixed Window

# Track matches
if char in required and window[char] == required[char]:
    matches += 1

4. Negative Numbers: Prefix Sums

# Use prefix sums + monotonic deque
prefix[i] - prefix[j] >= target

Tips

1. Choose right data structure: Set, map, or deque
2. Update in correct order: Remove old, add new, update result
3. Handle edge cases: Empty arrays, k > n, impossible targets
4. Optimize space: Clear map entries when count reaches 0
5. Test carefully: Off-by-one errors are common