Sliding Window

Use when: Subarray/substring problems with a size or condition constraint.

Complexity: O(N)

Fixed Size Window

def fixed_window(nums, k):
    window_sum = sum(nums[:k])
    best = window_sum
 
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        best = max(best, window_sum)
 
    return best

Variable Size Window - Shrink When Invalid

# Find longest subarray/substring satisfying condition
def variable_window(nums):
    left = 0
    best = 0
    state = ...  # e.g. a count, a dict
 
    for right in range(len(nums)):
        # expand: add nums[right] to state
        state = update(state, nums[right])
 
        while not valid(state):  # shrink until valid
            state = remove(state, nums[left])
            left += 1
 
        best = max(best, right - left + 1)
 
    return best

Variable Size Window - Shrink When Valid (find minimum)

# Find shortest subarray satisfying condition
def min_window(nums, target):
    left = 0
    best = float('inf')
    current = 0
 
    for right in range(len(nums)):
        current += nums[right]
 
        while current >= target:  # shrink while still valid
            best = min(best, right - left + 1)
            current -= nums[left]
            left += 1
 
    return best if best != float('inf') else 0

Signals in a Problem

• “Longest/shortest subarray/substring”
• Contiguous elements with a constraint (sum, count, distinct chars)
• “At most K distinct”, “sum >= target”