Sliding Window: The Pattern Behind 20% of Coding Interview Questions

Tarjan

5 min read

·

Jun 29, 2026

--

Listen

Share

Why you keep writing slow code

Here’s a problem you’ll see in some form in almost every interview:

“Given an array, find the maximum sum of any subarray of size k.”

The first instinct is brutal but obvious — look at every window, add it up:

// ❌ Brute force: O(n * k)
int best = Integer.MIN_VALUE;
for (int i = 0; i + k <= a.length; i++) {
    int sum = 0;
    for (int j = i; j < i + k; j++) sum += a[j];  // re-add k elements EVERY time
    best = Math.max(best, sum);
}

Notice the waste: when you move from window [0,1,2] to [1,2,3], you throw away the sum you just computed and re-add almost the same numbers. Two windows that overlap in k-1 elements, recomputed from scratch.

The Sliding Window pattern fixes exactly this. Instead of recomputing, you keep a running summary and update it as the window moves — add the element entering on the right, subtract the one leaving on the left.

That single idea takes a huge class of problems from O(n·k) or O(n²) down to O(n).

The mental model

There are two flavors. Get these two pictures in your head and you’ll recognize the pattern instantly.

1. Fixed window — a ruler of length k sliding along

The window size never changes. You slide it one step at a time.

The whole secret is that one line:

windowSum += a[right] - a[left];   // add what enters, drop what leaves

You touch each element twice at most (once when it enters, once when it leaves) → O(n).

2. Variable window — a rubber band that stretches and snaps

Here the size changes to satisfy a condition like “longest substring with no repeating characters” or “smallest subarray with sum ≥ target.”

You expand the right edge greedily, and shrink the left edge whenever the window becomes invalid.

• right always moves forward — it grows the window.
• left only moves when it has to — to restore validity.

Both pointers only ever move forward, so even though it looks like a nested loop, each element is added once and removed once. Still O(n).

How to recognize it in under 30 seconds

If the problem says…Think…“contiguous subarray / substring”Sliding window (not subsequence!)“of size k”Fixed window“longest / shortest / at most / at least k”Variable window“no repeating / at most k distinct”Variable window + a frequency map

🚩 Red flag that it’s NOT a window: the word “subsequence.” Windows only work on contiguous ranges.

The Java templates (copy these)

Fixed window

int maxSumK(int[] a, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += a[i];   // build the first window [0..k-1]
    int best = sum;
    for (int right = k; right < a.length; right++) {
        sum += a[right];          // element ENTERING on the right
        sum -= a[right - k];      // element LEAVING on the left
        best = Math.max(best, sum);
    }
    return best;
}

Variable window (the master template)

This skeleton solves a huge family of problems. Memorize its shape:

int left = 0;
for (int right = 0; right < n; right++) {
    include(a[right]);                 // 1) EXPAND: add the new element
    while (windowIsInvalid()) {        // 2) SHRINK while we broke the rule
            exclude(a[left]);
            left++;
        }
        // 3) window [left..right] is valid here → update the answer
        best = Math.max(best, right - left + 1);   // window size = right - left + 1
}

Three moving parts:
expand → restore validity → record answer.
Every variable-window problem is just a different include, windowIsInvalid, and what you record.

Press enter or click to view image in full size

A complete worked example

Problem (LeetCode 3): Find the length of the longest substring without repeating characters.

int longestUnique(String s) {
    int[] last = new int[128];          // last seen position (+1) of each ASCII char
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (last[c] > left) {           // c already appears INSIDE the window
            left = last[c];             // jump left past the previous occurrence
        }
        last[c] = right + 1;            // record c's newest position
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Dry run on "abcabcbb"

Watch the window slide. The green cells are the current window:

Step by step:

rightcharwindowsizebest0aa111bab222cabc333abca334bcab335cabc336bcb237bb13

Answer: 3 ("abc"). One pass, no nested recomputation.

Common mistakes beginners make

• ❌ Using a window for subsequence problems. Windows are for contiguous ranges only.
• ❌ if instead of while when shrinking. Sometimes you must shrink several times to become valid again.
• ❌ Off-by-one on size: it’s right - left + 1, not right - left.
• ❌ Forgetting to remove the left element’s contribution from your running sum / frequency map.
• ❌ The non-negative trap: the “shrink while sum ≥ target” trick only works when all numbers are non-negative. With negatives, use prefix sums + a deque instead.

One trick that impresses interviewers

“Count subarrays with exactly K distinct” feels hard… until you rewrite it as:

exactly(K) = atMost(K) − atMost(K − 1)

Both atMost calls are simple variable-window scans. Write that identity on the whiteboard and watch the interviewer nod.

Practice problems (Easy → Hard)

Easy

• 643 — Maximum Average Subarray I (fixed window warm-up)

Medium

• 3 — Longest Substring Without Repeating Characters ⭐
• 209 — Minimum Size Subarray Sum
• 424 — Longest Repeating Character Replacement
• 438 — Find All Anagrams in a String
• 567 — Permutation in String
• 1004 — Max Consecutive Ones III

Hard

• 76 — Minimum Window Substring ⭐
• 239 — Sliding Window Maximum (window + monotonic deque)
• 992 — Subarrays with K Different Integers

The 10-second cheat sheet

SLIDING WINDOW
--------------
FIXED k:   sum += a[right] - a[right - k]
VARIABLE:  for right: include(a[right]);
           while(invalid){ exclude(a[left]); left++; }
           update answer
size = right - left + 1
"longest/at most" → maximize    "shortest/≥ target" → minimize
contiguous ONLY · negatives break the sum trick · O(n) time

Wrapping up

The Sliding Window pattern is one of the highest-ROI things you can learn for coding interviews. The moment you read “contiguous subarray/substring,” your brain should jump to two questions:

1. Fixed or variable size?
2. Am I maximizing or minimizing?

Answer those two, drop in the matching template, and you’ve turned a scary O(n²) problem into a clean O(n) one.

This is part of a series where I break down every major DSA interview pattern, one at a time. Next up: Two Pointers — the cousin of the sliding window. Follow so you don’t miss it. 👋

If this helped, a few claps go a long way. What pattern should I cover next? Drop it in the comments.