Applying Sliding Windows to Contiguous Subarray Problems

Recognizing a sliding-window problem

A subarray is a contiguous portion of an array. If left = 2 and right = 5, the current window is:

nums[left:right + 1]

A sliding-window problem usually asks about a contiguous subarray or substring satisfying some condition:

• maximum sum or average over exactly $k$ consecutive elements;
• shortest subarray whose sum reaches a target;
• longest substring with no repeated characters;
• longest subarray with at most $k$ distinct values.

The central idea is to retain a compact state for the current window instead of recomputing it from scratch. For a sum problem, the state is a running sum. For a uniqueness condition, it may be a set. For frequency constraints, it is usually a dictionary.

Both pointers only move forward:

• right adds an element to the window;
• left removes an element from the window.

That is the source of the efficiency. You do not enumerate every possible start-end pair and rescan its contents.

Fixed-length windows: keep exactly $k$ elements

Consider this problem:

Given an integer list nums and an integer k, return the maximum average among all contiguous subarrays of length k.

For:

nums = [1, 12, -5, -6, 50, 3]
k = 4

the candidate windows are:

[1, 12, -5, -6]
[12, -5, -6, 50]
[-5, -6, 50, 3]

Their best average is:

A brute-force implementation can construct each window and sum it. Since there are roughly $n$ windows and summing each takes $k$ work, that costs:

When $k$ can grow with $n$, this becomes quadratic in the worst case.

Reuse the previous sum

Suppose the current window has sum $S$. When we shift it one position right:

• one value enters on the right;
• exactly one value leaves on the left.

So the next sum is:

There is no need to sum all $k$ elements again.

def max_average_fixed(nums: list[int], k: int) -> float:
    if not 1 <= k <= len(nums):
        raise ValueError("k must be between 1 and len(nums)")

    window_sum = sum(nums[:k])
    best_sum = window_sum

    # `right` is the index of the incoming element.
    for right in range(k, len(nums)):
        window_sum += nums[right]
        window_sum -= nums[right - k]
        best_sum = max(best_sum, window_sum)

    return best_sum / k

At the beginning of each loop iteration, window_sum is the sum of the preceding window:

nums[right - k:right]

After adding nums[right] and removing nums[right - k], it becomes the sum of the new window:

nums[right - k + 1:right + 1]

The subtraction index is worth understanding rather than memorizing. If right == k, then right - k == 0, so the first element of the original window is exactly the value that must leave.

Because all candidate windows have the same positive length $k$, maximizing the sum also maximizes the average. The code tracks sums and divides once at the end.

This form works even when values are negative. The window size is determined only by $k$, not by whether the sum rises or falls.

A reusable fixed-window template

The sum is only one possible state. For a fixed-size string problem, the state might be character counts; for an audio-oriented stream, it could be rolling frame energy or a count of clipped samples in each chunk.

The structural template is:

def fixed_window(nums: list[int], k: int):
    left = 0
    state = ...   # running sum, dictionary, count, and so on
    answer = ...

    for right, value in enumerate(nums):
        # Add `value` to state.

        if right - left + 1 == k:
            # The window nums[left:right + 1] has exactly k elements.
            # Evaluate or record the answer.

            # Remove nums[left] from state.
            left += 1

    return answer

The important invariant is:

At the moment you evaluate the answer, the active window has exactly $k$ elements and state describes those exact elements.

After evaluation, remove the leftmost element so the next iteration can add one new item and restore the size to $k$.

For the running-sum example:

• Time: $O(n)$
• Auxiliary space: $O(1)$

The list is traversed once, and every shift does constant work.

Variable-length windows: expand, then repair

A variable window does not have a preselected size. Instead, it maintains a validity condition.

A canonical example is:

Given a target and a list of positive integers, return the length of the shortest contiguous subarray whose sum is at least the target. Return 0 if none exists.

For:

target = 7
nums = [2, 3, 1, 2, 4, 3]

the answer is 2, from:

[4, 3]

The basic movement policy is different from the fixed-size case:

1. Expand right until the window is valid.
2. Once valid, record it.
3. Shrink left as much as possible while it remains valid.
4. Continue expanding right.

def min_length_at_least(target: int, nums: list[int]) -> int:
    left = 0
    window_sum = 0
    best_length = float("inf")

    for right, value in enumerate(nums):
        window_sum += value

        while window_sum >= target:
            best_length = min(best_length, right - left + 1)
            window_sum -= nums[left]
            left += 1

    return 0 if best_length == float("inf") else best_length

Why while, not if?

Suppose we reach this valid window:

[3, 1, 2, 4]  # sum = 10

It meets a target of 7, so its length is a candidate. But it may contain unnecessary values at the left:

[1, 2, 4]     # sum = 7

This is also valid and shorter. A single if would shrink only once, missing the better candidate. The while loop keeps shrinking until removing one more item would make the window invalid.

A compressed trace of the example looks like this:

The image captures the key behavioral difference from a fixed window: the right edge expands until the condition is met, then the left edge advances to remove unnecessary elements.

Why this variable window works only with positive values

The short answer is monotonicity.

For a list of positive integers:

• expanding right can only increase the window sum;
• shrinking left can only decrease the window sum.

That gives the pointer moves a sound logical basis.

If the current window sum is below the target, shrinking it cannot help. So the only useful action is to expand right.

If the sum reaches the target, any longer window with the same right endpoint cannot be shorter than the current one. So record it, then shrink left to search for the shortest valid suffix ending at that same right.

The loop invariant is:

After the inner while loop finishes, the current window is the first invalid window obtained by shrinking from a valid one ending at right.

That means every time the code records a length, it considers a real valid candidate, and it checks the shortest valid window for each ending index.

Negative values break the rule

Do not apply this exact sum-based method blindly when negatives are allowed.

Consider:

nums = [2, -1, 2, 1]
target = 3

When the first three values total 3, the algorithm shrinks by removing 2, leaving a sum of 1. At the next element, its tracked window may be:

[-1, 2, 1]  # sum = 2

but the suffix:

[2, 1]      # sum = 3

is valid and shorter. The earlier negative value prevents the “shrink means sum decreases predictably” argument from working.

In an interview, state the assumption explicitly:

This variable sliding window is valid because all numbers are positive, so the window sum changes monotonically as either boundary moves.

For arbitrary signed integers, a different approach is required; do not force a sliding-window template onto it.

Variable windows with a set: longest unique substring

Variable windows are not only for sums. The condition can be structural.

Return the length of the longest substring containing no repeated characters.

For:

s = "abcaabcbb"

a valid current window contains each character at most once. A set is sufficient because the invariant guarantees that every included character occurs exactly once.

def longest_unique_substring(s: str) -> int:
    left = 0
    seen: set[str] = set()
    best_length = 0

    for right, char in enumerate(s):
        while char in seen:
            seen.remove(s[left])
            left += 1

        seen.add(char)
        best_length = max(best_length, right - left + 1)

    return best_length

Before char is added, seen represents the characters in:

s[left:right]

If char is already present, adding it would invalidate the window. Remove characters from the left until that earlier occurrence is gone. Then add char; the window is valid again.

This is exactly where the dictionary-and-set work from the earlier lesson becomes useful:

For a condition such as “at most $k$ distinct characters,” use a frequency dictionary rather than a plain set. When removing a character from the left, its count may decrease without disappearing entirely from the window.

Why nested loops are still linear

At first glance, this structure can look quadratic:

for right in range(n):
    ...
    while window_is_invalid:
        left += 1

It is not automatically $O(n^2)$. Count pointer movement instead:

• right moves from the start to the end at most $n$ times.
• left also only moves forward, at most $n$ times.

No element can enter the window more than once, and no element can leave more than once. Therefore, the total number of pointer advances is at most proportional to $2n$:

Space depends on the state:

• rolling sum: $O(1)$;
• uniqueness set or frequency dictionary: up to $O(n)$ in the worst case.

A strong interview explanation is:

Although the code has a for loop containing a while loop, left never resets. Across the whole execution, both pointers advance at most $n$ times, so total time is $O(n)$.

Pattern-selection checklist

Before coding, classify the prompt with this sequence:

1. Is the desired sequence contiguous?
   Look for “subarray,” “substring,” “consecutive,” or “continuous.” If elements can be skipped, it is likely not a sliding-window problem.

2. Is the length specified exactly?
   If yes, use a fixed-length window. Maintain a window of size $k$, evaluate it, remove the leftmost item, and continue.

3. If length is not fixed, can a window be made valid by moving only left forward?
   If yes, consider a variable window with an explicit validity condition.

4. What state can be updated when an item enters or leaves?
   Common choices are a sum, count, set, or frequency dictionary.

5. Are the assumptions sufficient for the pointer logic?
   In particular, minimum-length sum problems require positive values for the standard variable-window method.

For streaming ML or audio applications, the fixed form often appears as a rolling statistic over fixed-duration chunks: for example, maximum energy over windows of a fixed sample count. The same add-one/remove-one update avoids recalculating an aggregate across every overlapping chunk.

Key takeaways

Sliding windows use two forward-moving pointers to maintain state for a contiguous region.

• Use a fixed-length window when the prompt gives an exact size $k$.
• Update its state by adding the entering value and removing the leaving value.
• Use a variable-length window when a validity condition determines when to shrink.
• For a minimum subarray sum at least a target, shrink repeatedly with while, not once with if.
• The standard sum-based variable window requires positive values; negative values invalidate its monotonic reasoning.
• A nested while does not imply quadratic time when both pointers only move forward: the total work is $O(n)$.

Next, you will move to a different linear-time pattern: using a stack to match nested structures or find a next greater or smaller element.