06 — Sliding Window

The core idea

A sliding window keeps a contiguous range [left, right] plus a summary of what's inside it — a sum, a character count, a distinct-element count.

The point: when the window moves, you update the summary instead of recomputing it.

Seeing where the saving comes from

"Find the largest sum of any 3 consecutive elements in [1, 4, 2, 10, 2, 3, 1]."

Brute force — for each start, add up 3 elements:

for (int i = 0; i + k <= n; i++) {
    int sum = 0;
    for (int j = i; j < i + k; j++) sum += nums[j];   // re-adding from scratch
    best = Math.max(best, sum);
}

O(n · k). Now watch two consecutive windows:

window at i=0:  [1, 4, 2] 10  2  3  1     sum = 7
window at i=1:   1 [4, 2, 10] 2  3  1     sum = 16

They share 4 and 2. Re-adding them is wasted work. The only real change is: one element left, one entered.

sum = sum - nums[i - 1] + nums[i + k - 1];    // O(1) per move

O(n). That's the entire technique.

When it applies

All three must hold:

1. The answer is a contiguous subarray or substring. Non-contiguous (a subsequence) means dynamic programming instead (19).

2. You can update the summary in O(1) per step. A sum, a count array, a distinct count — yes. A median — no.

3. The validity condition is monotonic in window size. Growing the window can only make it "more invalid" (or shrinking only more valid).

Why condition 3 matters

This is the one people skip, and it's what makes shrinking from the left safe.

Take "longest substring with at most k distinct characters". Adding a character can only keep the distinct count the same or raise it — never lower it. So if a window is invalid, every larger window containing it is also invalid, and shrinking is the only way back to validity.

If a condition could flip back and forth as the window grows, shrinking from the left might skip past a valid answer, and windowing would be wrong.

Template 1 — fixed-size window

int sum = 0, best = Integer.MIN_VALUE;

for (int right = 0; right < n; right++) {
    sum += nums[right];                       // element enters

    if (right >= k - 1) {                     // window is now exactly size k
        best = Math.max(best, sum);
        sum -= nums[right - k + 1];           // element leaves
    }
}

Understanding the two index expressions:

• right >= k - 1 — the window [right-k+1, right] is full. For k = 3, the first full window ends at right = 2.
• right - k + 1 — the leftmost index of the current window, the one about to leave.

Off-by-ones here are the most common bug in this template. Check them on a tiny example (k = 1, k = 2) before running.

Template 2 — variable window, find the longest valid

Expand always. Shrink only while the window is invalid. Record once valid.

int left = 0, best = 0;
for (int right = 0; right < n; right++) {
    add(nums[right]);                          // extend the window

    while (isInvalid()) {                      // restore validity
        remove(nums[left]);
        left++;
    }

    best = Math.max(best, right - left + 1);   // window is valid here
}

Window length is right - left + 1 (inclusive on both ends). Write it out rather than trusting memory — the + 1 is dropped constantly.

Longest Substring Without Repeating Characters

s = "abcabcbb" → answer 3 ("abc").

The set-based version, easier to explain:

Set<Character> window = new HashSet<>();
int left = 0, best = 0;

for (int right = 0; right < s.length(); right++) {
    while (window.contains(s.charAt(right))) {   // duplicate: shrink until it's gone
        window.remove(s.charAt(left));
        left++;
    }
    window.add(s.charAt(right));
    best = Math.max(best, right - left + 1);
}
return best;

Trace on "abcabcbb":

Answer: 3. ✓

The map-based version jumps left in one step instead of shrinking one at a time:

Map<Character, Integer> lastSeen = new HashMap<>();
int left = 0, best = 0;

for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
        left = lastSeen.get(c) + 1;            // jump past the previous occurrence
    }
    lastSeen.put(c, right);
    best = Math.max(best, right - left + 1);
}

The >= left guard is essential. The map remembers characters from before the current window too. Without the guard, a stale index would drag left backwards, growing the window incorrectly. The guard means "only react if that occurrence is still inside my window."

Both are O(n). The set version is easier to narrate; the map version is slightly faster.

Longest Repeating Character Replacement

You may replace up to k characters with any letter. Find the longest substring that can become all one character.

Deriving the condition — this is the insight being tested:

Consider a window. The cheapest way to make it uniform is to keep the character that already appears most and replace everything else. So:

replacements needed = windowLength - (count of the most frequent character)

The window is valid when that's ≤ k.

int[] count = new int[26];
int left = 0, maxFreq = 0, best = 0;

for (int right = 0; right < s.length(); right++) {
    count[s.charAt(right) - 'A']++;
    maxFreq = Math.max(maxFreq, count[s.charAt(right) - 'A']);

    while (right - left + 1 - maxFreq > k) {   // too many replacements needed
        count[s.charAt(left) - 'A']--;
        left++;
    }
    best = Math.max(best, right - left + 1);
}
return best;

Trace on s = "AABABBA", k = 1:

Answer: 4 ("AABA" → replace the B). ✓

The subtlety interviewers probe: maxFreq is never decreased when the window shrinks, so it can be stale (too high). The answer is still correct. Reason: a stale maxFreq only makes the condition easier to satisfy, so the window may not shrink when it "should" — but best only ever grows when a genuinely longer valid window is found, and a too-large maxFreq can never manufacture a window longer than one already achieved. Recomputing maxFreq on every shrink would be correct too, just slower. If you know this question, mention it unprompted.

Template 3 — variable window, find the shortest valid

Mirror image of Template 2: expand until valid, then shrink while still valid, recording at each step.

int left = 0, best = Integer.MAX_VALUE;
for (int right = 0; right < n; right++) {
    add(nums[right]);

    while (isValid()) {
        best = Math.min(best, right - left + 1);   // record BEFORE shrinking
        remove(nums[left]);
        left++;
    }
}
return best == Integer.MAX_VALUE ? 0 : best;

The difference from Template 2 in one line: longest records outside the shrink loop (after restoring validity); shortest records inside it (while still valid).

Minimum Window Substring

Find the shortest substring of s containing every character of t, including duplicates.

s = "ADOBECODEBANC", t = "ABC" → answer "BANC".

The challenge: checking "does the window contain all of t?" naively costs O(len(t)) per step. Two counters make it O(1).

if (s.length() < t.length()) return "";

Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);

Map<Character, Integer> window = new HashMap<>();
int have = 0, required = need.size();          // count of DISTINCT chars fully satisfied
int left = 0, bestLen = Integer.MAX_VALUE, bestStart = 0;

for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    window.merge(c, 1, Integer::sum);

    // did this character just COMPLETE its requirement?
    if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) have++;

    while (have == required) {                 // valid — try to shrink
        if (right - left + 1 < bestLen) {
            bestLen = right - left + 1;
            bestStart = left;
        }
        char lc = s.charAt(left);
        window.merge(lc, -1, Integer::sum);
        if (need.containsKey(lc) && window.get(lc) < need.get(lc)) have--;   // broke it
        left++;
    }
}
return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);

Understanding have and required:

• required = how many distinct characters t needs. For t = "ABC" that's 3; for t = "AABC" still 3 (A, B, C).
• have = how many of those distinct characters currently appear in the window at least as often as needed.
• The window is valid exactly when have == required.

Why the check uses == and not >=:

if (window.get(c) == need.get(c)) have++;

We increment on the exact moment a character's requirement becomes satisfied. If the count goes from 2 to 3 when only 2 were needed, we don't increment again — it was already counted. Using >= would increment repeatedly and inflate have. Symmetrically on removal, we decrement only when the count drops below what's needed.

.intValue() is required. Both sides are boxed Integers. For values above 127, == compares object references and fails (03).

Trace on s = "ADOBECODEBANC", t = "ABC" (key moments):

Answer: "BANC". ✓

O(n + m) time.

Template 4 — matching count arrays (Permutation in String)

"Does s2 contain any permutation of s1?" The window is fixed-size (s1.length()), and validity means "the window's letter counts exactly equal s1's".

The straightforward version — compare the arrays each step:

int[] need = new int[26], win = new int[26];
for (int i = 0; i < s1.length(); i++) {
    need[s1.charAt(i) - 'a']++;
    win[s2.charAt(i) - 'a']++;
}
if (Arrays.equals(need, win)) return true;

for (int r = s1.length(); r < s2.length(); r++) {
    win[s2.charAt(r) - 'a']++;                      // entering
    win[s2.charAt(r - s1.length()) - 'a']--;        // leaving
    if (Arrays.equals(need, win)) return true;
}
return false;

Arrays.equals is 26 comparisons — a constant — so this is O(26n) = O(n). This is a perfectly good answer. Write it first.

The refinement — maintain a matches counter so the check is truly O(1):

int matches = 0;
for (int i = 0; i < 26; i++) if (need[i] == win[i]) matches++;

for (int r = s1.length(); r < s2.length(); r++) {
    if (matches == 26) return true;

    int in = s2.charAt(r) - 'a';
    win[in]++;
    if (win[in] == need[in]) matches++;            // just became equal
    else if (win[in] == need[in] + 1) matches--;   // just stopped being equal

    int out = s2.charAt(r - s1.length()) - 'a';
    win[out]--;
    if (win[out] == need[out]) matches++;
    else if (win[out] == need[out] - 1) matches--;
}
return matches == 26;

Reading the increment/decrement logic: after changing one slot by ±1, only that slot can have changed its equal-or-not status. If it landed exactly on need, one more slot matches. If it just moved one step past need (from equal to unequal), one fewer matches. Any other movement doesn't change the status.

Offer this as the optimization after the simple version works. It demonstrates incremental invariant maintenance — a transferable skill.

Template 5 — monotonic deque window (Sliding Window Maximum)

Why the other templates fail here

For a sum, removing an element is easy: subtract it. For a maximum, it isn't — if you remove the current max, you have no idea what the new max is. There's no O(1) update for a plain variable.

The fix

Keep a deque of indices whose values are in decreasing order. Then:

• The front always holds the index of the window's maximum.
• When a new value arrives, any smaller values already in the deque can never be the max again — the new one is bigger and stays in the window longer. Discard them.

Deque<Integer> dq = new ArrayDeque<>();     // holds INDICES; their values decrease front→back
int[] res = new int[nums.length - k + 1];

for (int i = 0; i < nums.length; i++) {
    // 1. Drop the front if it has slid out of the window
    if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();

    // 2. Drop from the back anything smaller than the incoming value
    while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();

    dq.offerLast(i);

    // 3. Record once the first full window exists
    if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
}
return res;

Trace on nums = [1,3,-1,-3,5,3,6,7], k = 3:

Result: [3,3,5,5,6,7]. ✓

Two things to internalize:

1. Store indices, not values. You need the index to know when an element has slid out of the window. The value is one dereference away.
2. O(n) despite the inner while. Each index is added once and removed once, so total deque operations are at most 2n — the same amortized argument as the monotonic stack (09).

Step 1 uses if rather than while because only one index can expire per iteration.

Kadane's algorithm as a degenerate window

Maximum Subarray is a window whose shrink rule is "discard the entire prefix when it stops helping":

int best = nums[0], cur = nums[0];
for (int i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);   // extend the window, or restart it here
    best = Math.max(best, cur);
}

Math.max(nums[i], cur + nums[i]) is the decision to reset left to i: if the running sum has gone negative, carrying it forward only hurts, so drop everything and start fresh.

Framing it this way makes Maximum Subarray and Maximum Product Subarray one family rather than two tricks. NeetCode files it under Greedy (20), but the reasoning is windowing.

Initialize with nums[0], not 0 — an all-negative array must return its largest element, and starting at 0 wrongly returns 0.

Choosing the template

Debugging checklist

1. Is the length right - left + 1? The + 1 is dropped constantly.
2. Longest vs shortest — are you recording inside or outside the shrink loop?
3. Does the shrink loop always terminate? left must increment on every iteration.
4. Is the summary updated symmetrically? Everything added on entry must be undone on exit.
5. Is the condition monotonic? If not, a window is the wrong tool entirely.

Complexity summary