Sliding Window Pattern: How to Turn Nested Loops Into Linear Time

Sliding window is one of the first patterns worth mastering because it shows up in both interviews and production code. Whenever you need to reason about a contiguous range in an array or string, a window is often the cleanest way to do it.

The core idea is simple: instead of recomputing work for every possible range, keep a moving window and update it incrementally.

When Sliding Window Is a Good Fit

Reach for this pattern when:

• The problem asks about a contiguous subarray or substring.
• A brute-force solution checks every range with nested loops.
• You can update the answer by adding one element on the right and sometimes removing one from the left.

Typical prompts include:

• longest substring with some property
• smallest subarray meeting a constraint
• maximum sum of k consecutive values

Fixed-Size Window

In a fixed-size window, the width never changes. You add a new value on the right and remove the oldest value on the left.

Classic example: maximum sum of any subarray of length k.

def max_sum_k(nums: list[int], k: int) -> int:
    window_sum = sum(nums[:k])
    best = window_sum

    for right in range(k, len(nums)):
        window_sum += nums[right]
        window_sum -= nums[right - k]
        best = max(best, window_sum)

    return best

This turns an O(n * k) approach into O(n).

Variable-Size Window

In a variable-size window, you grow the window until a condition breaks, then shrink it from the left until it becomes valid again.

Classic example: minimum length subarray with sum at least target for positive integers.

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

    for right in range(len(nums)):
        window_sum += nums[right]

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

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

The reason this works is that every element enters the window once and leaves the window once, so the total work remains linear.

A String Example: Longest Substring Without Repeating Characters

This is the interview problem that makes the variable window click for many people.

def length_of_longest_substring(s: str) -> int:
    last_seen: dict[str, int] = {}
    left = 0
    best = 0

    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1

        last_seen[ch] = right
        best = max(best, right - left + 1)

    return best

The subtle part is the >= left check. It makes sure we only react to duplicates that are inside the current window.

Common Mistakes

• Using sliding window when the range is not contiguous
• Forgetting whether the window rule works only for positive numbers
• Updating the answer before restoring the window to a valid state
• Off-by-one mistakes in window size calculations

That second point matters a lot. The shrinking trick for sum constraints depends on the fact that removing items from the left can only decrease the sum in a predictable way. Once negative numbers are allowed, you often need prefix sums or a different strategy entirely.

Mental Model

Ask yourself three questions:

1. What makes the current window valid?
2. What state do I need to maintain while the window moves?
3. When should I shrink from the left?

If you can answer those clearly, the implementation usually becomes straightforward.

Complexity

k is the number of distinct values you need to track.

Practice These Next

• Maximum Average Subarray I
• Minimum Size Subarray Sum
• Longest Repeating Character Replacement
• Permutation in String

If you can identify whether a problem needs a fixed or variable window within 30 seconds, you are already ahead of most candidates.