Sliding window technique

Imagine you’re monitoring server response times and need to alert when any 5-minute window averages above 200ms. If you recompute the whole 5-minute block from scratch every time the window moves forward by one reading, you keep redoing almost all the same work. With n readings and a window of size k, that brute-force approach costs O(n × k).

Sliding window asks a better question: what actually changed when the window moved by one step? Only one value entered on the right, and one value left on the left. If you update your running state with those two changes, each slide is O(1), so the whole scan becomes O(n).

That is why sliding window shows up everywhere: arrays, strings, rate limits, monitoring dashboards, substring problems, and interview questions that sound different but share the same structure.

The core insight

A window is just a contiguous range like arr[start...end]. The trick is to avoid rebuilding that range’s answer from scratch every time.

When the window slides one step right:

• add the new element entering the window
• remove the old element leaving the window
• update the answer from the running state

For a sum problem, that means:

newSum = oldSum + enteringValue - leavingValue

That tiny formula is the reason sliding window is powerful. Instead of spending O(k) to sum k items again, you spend O(1) to adjust what you already know.

There are really two big versions of the pattern:

1. Fixed-size window — the window size is always k
2. Variable-size window — the window grows and shrinks depending on a condition

Let’s build both from concrete examples.

Pattern 1: Fixed-size window

Problem: Find the maximum sum of any subarray of size k.

Example: arr = [2, 1, 5, 1, 3, 2], k = 3

The windows are:

• [2, 1, 5] → sum = 8
• [1, 5, 1] → sum = 7
• [5, 1, 3] → sum = 9
• [1, 3, 2] → sum = 6

So the answer is 9.

A beginner’s first approach is often: “for every starting index, sum the next k elements.” That works, but each window costs O(k), and there are about n windows, so total time is O(n × k).

With sliding window, we do something smarter.

Step by step

1. Initialize the sum of the first k elements.
2. For each new position, add arr[i].
3. Subtract arr[i - k], because that element just left the window.
4. Track the maximum sum seen so far.

Using the example:

• Start with [2, 1, 5] → sum = 8, max = 8
• Slide right: add 1, remove 2 → sum = 7, max = 8
• Slide right: add 3, remove 1 → sum = 9, max = 9
• Slide right: add 2, remove 5 → sum = 6, max = 9

Notice how each move reused the previous sum. We never recomputed a whole window.

def max_sum_subarray_k(arr: list[int], k: int) -> int:
    if not arr or k <= 0 or k > len(arr):
        return 0

    window_sum = sum(arr[:k])
    max_sum = window_sum

    for end in range(k, len(arr)):
        window_sum += arr[end]
        window_sum -= arr[end - k]
        max_sum = max(max_sum, window_sum)

    return max_sum

public static int maxSumSubarrayK(int[] arr, int k) {
    if (arr == null || arr.length == 0 || k <= 0 || k > arr.length) {
        return 0;
    }

    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }

    int maxSum = windowSum;

    for (int end = k; end < arr.length; end++) {
        windowSum += arr[end];
        windowSum -= arr[end - k];
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

int maxSumSubarrayK(const vector<int>& arr, int k) {
    if (arr.empty() || k <= 0 || k > static_cast<int>(arr.size())) {
        return 0;
    }

    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }

    int maxSum = windowSum;

    for (int end = k; end < static_cast<int>(arr.size()); end++) {
        windowSum += arr[end];
        windowSum -= arr[end - k];
        maxSum = max(maxSum, windowSum);
    }

    return maxSum;
}

Complexity:

• Time: O(n)
• Extra space: O(1)

More fixed-window examples

Once you recognize “exactly size k,” the pattern becomes automatic.

• Maximum average subarray — same logic as maximum sum, then divide by k
• First negative integer in every window of size k — window size stays fixed, but the state you maintain is different
• Number of subarrays with exactly k distinct values — often solved via the atMost(k) - atMost(k - 1) trick we’ll cover later

The key lesson is: with fixed windows, the size never changes. Only the position changes.

Pattern 2: Variable-size window (shrink from left)

Problem: Find the minimum length subarray with sum at least target.

Example: arr = [2, 3, 1, 2, 4, 3], target = 7

The answer is 2, because [4, 3] is the shortest window whose sum is at least 7.

Here the window size is not fixed. Sometimes the best window is length 4, sometimes 3, sometimes 2. So we cannot slide a rigid block of size k. We need a window that expands and shrinks.

The key insight: when to shrink

This is the heart of variable-size sliding window.

• Move end right to grow the window.
• Keep adding values to the running state.
• As soon as the condition becomes true, try to shrink from the left while it stays true.

Why shrink? Because if the question asks for a minimum or shortest window, any extra values on the left are suspicious. If the current window already satisfies the condition, maybe you can remove some leading values and still keep it valid.

Step by step with numbers

For arr = [2, 3, 1, 2, 4, 3], target = 7:

• Add 2 → sum = 2 (not enough)
• Add 3 → sum = 5 (not enough)
• Add 1 → sum = 6 (not enough)
• Add 2 → sum = 8 (condition met)
  • record length 4
  • shrink: remove 2 → sum = 6
• Add 4 → sum = 10
  • record length 4
  • shrink: remove 3 → sum = 7
  • still valid, record length 3
  • shrink: remove 1 → sum = 6
• Add 3 → sum = 9
  • record length 3
  • shrink: remove 2 → sum = 7
  • still valid, record length 2
  • shrink: remove 4 → sum = 3

Best length found = 2.

That “grow until valid, then shrink while valid” rhythm is the pattern.

Template

start = 0
for end in range(n):
    # expand: add arr[end] to window state
    while window_condition_met():
        # record answer
        # shrink: remove arr[start] from window state
        start += 1

def min_subarray_len(target: int, arr: list[int]) -> int:
    start = 0
    window_sum = 0
    best = float('inf')

    for end in range(len(arr)):
        window_sum += arr[end]

        while window_sum >= target:
            best = min(best, end - start + 1)
            window_sum -= arr[start]
            start += 1

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

public static int minSubarrayLen(int target, int[] arr) {
    int start = 0;
    int windowSum = 0;
    int best = Integer.MAX_VALUE;

    for (int end = 0; end < arr.length; end++) {
        windowSum += arr[end];

        while (windowSum >= target) {
            best = Math.min(best, end - start + 1);
            windowSum -= arr[start];
            start++;
        }
    }

    return best == Integer.MAX_VALUE ? 0 : best;
}

int minSubarrayLen(int target, const vector<int>& arr) {
    int start = 0;
    int windowSum = 0;
    int best = INT_MAX;

    for (int end = 0; end < static_cast<int>(arr.size()); end++) {
        windowSum += arr[end];

        while (windowSum >= target) {
            best = min(best, end - start + 1);
            windowSum -= arr[start];
            start++;
        }
    }

    return best == INT_MAX ? 0 : best;
}

This works because every index moves forward at most once. end moves from left to right, and start also only moves from left to right. So even though there is a nested while, the total work is still O(n).

Important: this specific sum-based version assumes positive numbers. If negative numbers are allowed, shrinking may break the logic, and you usually need a different approach.

Pattern 3: Variable window with a hash map (string problems)

Arrays often use a running sum. String problems usually need a different kind of window state: a frequency map.

Problem: Longest substring without repeating characters

Example: s = "abcabcbb"

The longest substring without repeating characters is "abc", so the answer is 3.

How do we know whether the current window is valid? We track how many times each character appears inside the window.

• Expand right and add s[end] to the map.
• If that character count becomes greater than 1, the window has a duplicate.
• Shrink from the left until the duplicate disappears.
• Track the longest valid window.

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

    for end, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1

        while counts[ch] > 1:
            left_char = s[start]
            counts[left_char] -= 1
            start += 1

        best = max(best, end - start + 1)

    return best

public static int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> counts = new HashMap<>();
    int start = 0;
    int best = 0;

    for (int end = 0; end < s.length(); end++) {
        char ch = s.charAt(end);
        counts.put(ch, counts.getOrDefault(ch, 0) + 1);

        while (counts.get(ch) > 1) {
            char leftChar = s.charAt(start);
            counts.put(leftChar, counts.get(leftChar) - 1);
            start++;
        }

        best = Math.max(best, end - start + 1);
    }

    return best;
}

int lengthOfLongestSubstring(const string& s) {
    unordered_map<char, int> counts;
    int start = 0;
    int best = 0;

    for (int end = 0; end < static_cast<int>(s.size()); end++) {
        counts[s[end]]++;

        while (counts[s[end]] > 1) {
            counts[s[start]]--;
            start++;
        }

        best = max(best, end - start + 1);
    }

    return best;
}

The pattern is exactly the same as the previous section. The only thing that changed is the window state:

• sum for numeric problems
• frequency map for string problems
• distinct-count tracker for “at most k distinct” problems

Problem: Minimum window substring

In Minimum Window Substring, you are given s and t, and you want the shortest substring of s that contains every character of t with the required counts.

This is where the popular need counter pattern appears:

• build a frequency map of characters needed from t
• expand right through s
• decrease “needed” counts as useful characters arrive
• once all requirements are satisfied, shrink from the left to make the window as short as possible

The exact implementation is more detailed, but the mental model is still the same: expand until valid, shrink while valid.

Fixed vs variable: a decision guide

When you read a problem statement, certain phrases are strong hints.

A quick rule of thumb:

• If the size is given, think fixed window.
• If the size is part of the answer, think variable window.
• If the validity depends on characters or categories, think hash map / frequency table inside the window.

The “at most k” trick

One of the most useful sliding-window identities is:

exactly(k) = atMost(k) - atMost(k - 1)

Why does this work?

• atMost(k) counts every window with 0, 1, 2, ..., k distinct values.
• atMost(k - 1) counts every window with 0, 1, 2, ..., k - 1 distinct values.
• Subtract them, and only windows with exactly k remain.

This trick turns hard counting problems into easier helper functions.

For example, to count subarrays with exactly 2 distinct values:

• count subarrays with at most 2 distinct
• count subarrays with at most 1 distinct
• subtract

It is a beautiful example of using sliding window as a building block instead of only as a final answer.

Common pitfalls

Sliding window is simple once you see it, but beginners often make the same mistakes.

1. Forgetting to update state on shrink

   • If you move start, you must also remove arr[start] or decrement that character’s count.

2. Off-by-one window length

   • The current window length is end - start + 1, not end - start.

3. Using the wrong condition direction

   • while sum >= target is different from while sum > target.
   • A single missing = can change the answer.

4. Not handling empty input or invalid k

   • If arr is empty, or k > len(arr), decide what your function should return.

5. Applying the positive-number template to negative numbers

   • The minimum-length sum problem’s standard sliding window logic depends on all values being positive.

When debugging, print start, end, the current state, and the exact moment you shrink. Most bugs become obvious once you watch pointer movement.

Practice problems

• Maximum Sum Subarray of Size K (Easy)
• Longest Substring Without Repeating Characters (#3, Medium)
• Minimum Window Substring (#76, Hard)
• Sliding Window Maximum (#239, Hard)
• Fruit Into Baskets (#904, Medium)

A note about Sliding Window Maximum: it uses a window, but it adds a deque to keep track of the current maximum efficiently. That makes it a great “next level” problem once the basic pattern feels natural.

Final mental checklist

Before you code, ask yourself:

1. Is the window size fixed, or does it change?
2. What state do I need to maintain — sum, frequency map, distinct count, max structure?
3. What exactly makes the window valid or invalid?
4. If the window becomes valid, should I shrink to improve the answer?
5. Do both pointers move only forward?

If you can answer those five questions, most sliding-window problems become much less mysterious.

What’s next

Sliding window is about answering questions over contiguous ranges while you move through the data once. The natural next step is learning how to answer range questions even faster when the window does not move one step at a time: prefix sums and difference arrays.