Sliding Windows

Sliding Windows maintain a subarray/subsequence while moving through the input once.
The main decision is always: when to grow and when to shrink.

General Setup

Use a window [l, r):

• l is inclusive, r is exclusive.
• Grow by increasing r.
• Shrink by increasing l.
• Maintain window data (sum, frequency map, bad-count, distinct-count, etc.).

1) Fixed-Length Windows

Use this when the window size is exactly k.

fixed_length_window(arr, k):
    initialize:
        l, r = 0, 0
        window_data
        cur_best
    while r < len(arr):
        grow window with arr[r]; r += 1
        if r - l == k:
            update cur_best
            shrink window from l; l += 1
    return cur_best

def most_weekly_sales(sales):
    l = 0
    window_sum = 0
    best = 0

    for r in range(len(sales)):
        window_sum += sales[r]
        if r - l + 1 == 7:
            best = max(best, window_sum)
            window_sum -= sales[l]
            l += 1
    return best

2) Resetting Windows

Use this when adding one element can make the whole window irrecoverably invalid, so shrinking one-by-one is unnecessary.

resetting_window(arr):
    initialize:
        l, r = 0, 0
        window_data
        cur_best
    while r < len(arr):
        if window remains valid after adding arr[r]:
            grow window with arr[r]; r += 1
            update cur_best
        else:
            reset window and data structures past the problematic element
    return cur_best

def longest_good_day_streak(sales):
    l = 0
    best = 0

    for r in range(len(sales)):
        if sales[r] >= 10:
            best = max(best, r - l + 1)
        else:
            l = r + 1
    return best

3) Maximum Windows

Use this when the objective is to maximize window length/value under a constraint.

maximum_window(arr):
    initialize:
        l, r = 0, 0
        window_data
        cur_best
    while r < len(arr):
        if can grow and stay valid:
            grow window with arr[r]; r += 1
            update cur_best
        elif l == r:
            l += 1; r += 1
        else:
            shrink window from l; l += 1
    return cur_best

def max_at_most_3_bad_days(sales):
    l = 0
    bad_days = 0
    best = 0

    for r in range(len(sales)):
        if sales[r] < 10:
            bad_days += 1

        while bad_days > 3:
            if sales[l] < 10:
                bad_days -= 1
            l += 1

        best = max(best, r - l + 1)
    return best

4) Minimum Windows

Use this when the objective is to find the shortest window that satisfies a constraint.

minimum_window(arr):
    initialize:
        l, r = 0, 0
        window_data
        cur_best = inf
    while True:
        if window must grow to become valid:
            if r == len(arr):
                break
            grow window with arr[r]; r += 1
        else:
            update cur_best
            shrink window from l; l += 1
    return cur_best

def shortest_over_20_sales(sales):
    l = 0
    window_sum = 0
    best = float('inf')

    for r in range(len(sales)):
        window_sum += sales[r]
        while window_sum > 20:
            best = min(best, r - l + 1)
            window_sum -= sales[l]
            l += 1

    return -1 if best == float('inf') else best

5) Counting Problems (At-Most-K / Exactly-K / At-Least-K)

When the At-Most-K version has the maximum-window property, you can reuse it for other counting forms.

At-Most-K Recipe

count_at_most_k(arr, k):
    l = 0
    count = 0
    window_data
    for r in range(len(arr)):
        add arr[r] to window_data
        while invalid(window_data, k):
            remove arr[l] from window_data
            l += 1
        count += r - l + 1
    return count

Reusable transforms

• Exactly-K = At-Most-K(k) - At-Most-K(k - 1)
• At-Least-K = TotalSubarrays - At-Most-K(k - 1), where TotalSubarrays = n * (n + 1) / 2

Some counting problems do not fit this transform directly and should be handled case by case.

def count_at_most_k_bad_days(sales, k):
    l = 0
    bad_days = 0
    count = 0

    for r in range(len(sales)):
        if sales[r] < 10:
            bad_days += 1
        while bad_days > k:
            if sales[l] < 10:
                bad_days -= 1
            l += 1
        count += (r - l + 1)

    return count

exactly_k = count_at_most_k_bad_days(sales, k) - count_at_most_k_bad_days(sales, k - 1)

n = len(sales)
total = n * (n + 1) // 2
at_least_k = total - count_at_most_k_bad_days(sales, k - 1)

Key Takeaways

• Contiguous Subarrays: Sliding windows are primarily used for problems involving contiguous subarrays or substrings.
• Two Pointers: The technique relies on two pointers (l and r) moving in the same direction (usually left to right).
• Linear Time: The complexity is typically $O(N)$ because each element is added and removed from the window at most once.
• Window Validity: The core logic revolves around maintaining a valid window state:
  • Expand (r++) to include more elements or find a valid window.
  • Shrink (l++) to maintain constraints or minimize the window size.
• Optimization: Always check if you can calculate the result from the window state in $O(1)$ time to keep the overall complexity linear.