Sliding Window Technique: Fixed & Variable Windows Explained

Many questions ask about a contiguous stretch of the input: the largest sum of k consecutive numbers, the longest substring with no repeated letter. Neighbouring stretches share almost all their elements, so the sliding window technique keeps one stretch, the window, and updates it as the edges move — O(1) a step instead of O(k). It is two pointers moving the same way, in two kinds:

Why recomputing every window is too slow

Summing every window of k from scratch is n − k + 1 windows of k additions: about 2.5 × 10⁹ for n = 100,000 and k = 50,000, against roughly 10⁸ simple steps a second. Without a fixed length it is worse — about n²/2 substrings, each checked for repeats. Yet neighbouring windows share k − 1 elements, added up again every time.

The idea: slide the window instead of rebuilding it

A fixed-size window keeps a running sum: old sum + newcomer − leaver. Given a rule instead of a length, a variable-size window from left to right follows three rules:

• Grow. Move right one step and add the new element to the window's state.
• Shrink. While the window breaks the rule, remove the element at left and move left on.
• Record. Once the window obeys the rule again, compare it with the best so far.

The state is whatever checks the rule in O(1): a running sum, or a count map of how often each value is inside. Below, the longest substring without a repeat in "pwwkew" — where a map of last-seen positions lets left jump straight past a repeat.

1. The window is the stretch s[left..right], and it may never hold a character twice. Both edges start at index 0 with nothing inside yet; a map remembers the last index each character was seen at.
2. right moves to index 0 and reads 'p', which is not in the window, so the window grows to "p" (length 1). That is the longest yet: best = 1.
3. right moves to index 1 and reads 'w', which is not in the window, so the window grows to "pw" (length 2). That is the longest yet: best = 2.
4. right reaches 'w' at index 2, but 'w' is already in the window at index 1. Shrinking one step at a time would work, but the map says exactly where the repeat is.
5. So left jumps straight to index 2, one past the old 'w'. The window "w" is distinct again; its length is 1, and the best is still 2.
6. right moves to index 3 and reads 'k', which is not in the window, so the window grows to "wk" (length 2). The best stays 2.
7. right moves to index 4 and reads 'e', which is not in the window, so the window grows to "wke" (length 3). That is the longest yet: best = 3.
8. right reaches 'w' at index 5, but 'w' is already in the window at index 2. Shrinking one step at a time would work, but the map says exactly where the repeat is.
9. So left jumps straight to index 3, one past the old 'w'. The window "kew" is distinct again; its length is 3, and the best is still 3.
10. right has passed the end. Each index entered the window once and left at most once, so the scan is O(n) — the answer is 3, for "wke".

A fixed-size window

There is nothing to decide: build the first window once, then slide it to the end. When right enters, the element leaving is arr[right - k] and the window starts at right - k + 1.

1. Build the first window once: 2 + 1 + 5 = 8. That costs k additions — the only time the window is summed from scratch.
2. Slide one step: 1 enters and 2 leaves, so the sum is 8 − 2 + 1 = 7. The 2 elements both windows share are never added again — the brute force would add them all over.
3. 3 enters, 1 leaves: 7 − 1 + 3 = 9. That beats every window so far: best = 9.
4. 2 enters, 5 leaves: 9 − 5 + 2 = 6. Not better than 9.
5. The best window is 2..4 with sum 9. Every window after the first cost one addition and one subtraction, whatever k is: O(n) in all, against O(n × k) for summing each window afresh.

The code

The program runs the same array with k = 3 and k = 2. With k = 2 two windows tie at 6; the strict > keeps the first one.

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

// Largest sum of k consecutive elements, and the index where that window starts.
pair<int, int> maxWindowSum(const vector<int>& arr, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += arr[i];   // the first window, built once
    int best = sum, bestStart = 0;
    for (int right = k; right < (int)arr.size(); right++) {
        sum += arr[right] - arr[right - k];       // one element enters, one leaves
        if (sum > best) {
            best = sum;
            bestStart = right - k + 1;
        }
    }
    return {best, bestStart};
}

int main() {
    vector<int> arr = {2, 1, 5, 1, 3, 2};
    for (int k : {3, 2}) {
        pair<int, int> r = maxWindowSum(arr, k);
        cout << "k = " << k << ": best sum " << r.first << " (indices " << r.second
             << " to " << r.second + k - 1 << ")\n";
    }
    return 0;
}

public class Main {
    // Largest sum of k consecutive elements, and the index where that window starts.
    static int[] maxWindowSum(int[] arr, int k) {
        int sum = 0;
        for (int i = 0; i < k; i++) sum += arr[i];   // the first window, built once
        int best = sum, bestStart = 0;
        for (int right = k; right < arr.length; right++) {
            sum += arr[right] - arr[right - k];       // one element enters, one leaves
            if (sum > best) {
                best = sum;
                bestStart = right - k + 1;
            }
        }
        return new int[] {best, bestStart};
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 1, 3, 2};
        for (int k : new int[] {3, 2}) {
            int[] r = maxWindowSum(arr, k);
            System.out.println("k = " + k + ": best sum " + r[0] + " (indices " + r[1]
                    + " to " + (r[1] + k - 1) + ")");
        }
    }
}

def max_window_sum(arr, k):
    """Largest sum of k consecutive elements, and the index where that window starts."""
    total = sum(arr[:k])                      # the first window, built once
    best, best_start = total, 0
    for right in range(k, len(arr)):
        total += arr[right] - arr[right - k]  # one element enters, one leaves
        if total > best:
            best = total
            best_start = right - k + 1
    return best, best_start


arr = [2, 1, 5, 1, 3, 2]
for k in (3, 2):
    best, start = max_window_sum(arr, k)
    print(f"k = {k}: best sum {best} (indices {start} to {start + k - 1})")

// Largest sum of k consecutive elements, and the index where that window starts.
function maxWindowSum(arr, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += arr[i]; // the first window, built once
  let best = sum;
  let bestStart = 0;
  for (let right = k; right < arr.length; right++) {
    sum += arr[right] - arr[right - k]; // one element enters, one leaves
    if (sum > best) {
      best = sum;
      bestStart = right - k + 1;
    }
  }
  return [best, bestStart];
}

const arr = [2, 1, 5, 1, 3, 2];
for (const k of [3, 2]) {
  const [best, start] = maxWindowSum(arr, k);
  console.log(`k = ${k}: best sum ${best} (indices ${start} to ${start + k - 1})`);
}

k = 3: best sum 9 (indices 2 to 4)
k = 2: best sum 6 (indices 1 to 2)

The same slide answers Maximum Sum Subarray of Size K. Permutation in String is a fixed window too: slide a pattern-length window across the text and compare its letter counts with the pattern's.

A variable-size window: grow, then shrink

The classic is Longest Substring Without Repeating Characters, with a count map as the state. The window was valid before s[right] arrived, so a count of 2 can only be the newcomer's: shrink until it is 1 again. This is the program's loop, without the last-seen jump:

1. right = 0: 'a' enters, its count is 1, and the window "a" is valid. The count map is the window's state: how many times each letter is inside.
2. right = 1: 'b' enters with count 1 — still no repeat. The window "ab" has length 2, the longest yet.
3. right = 2: 'c' enters with count 1 — still no repeat. The window "abc" has length 3, the longest yet.
4. right = 3: 'a' now appears twice. Only the newcomer can be the repeat, so drop from the left until its count is 1: 'a' goes. The window "bca" has length 3.
5. right = 4: 'b' appears twice again, and its first copy is at the left edge: drop 'b'. The window "cab" has length 3.
6. right = 5: 'c' appears twice again, and its first copy is at the left edge: drop 'c'. The window "abc" has length 3.
7. right = 6: 'b' appears twice, but its first copy is not at the left edge, so 'a' and 'b' both go before its count is 1. The window "cb" has length 2.
8. right = 7: 'b' appears twice, but its first copy is not at the left edge, so 'c' and 'b' both go before its count is 1. The window "b" has length 1.
9. The longest is 3, "abc". right moved 8 times and left moved 7 times, each element entering once and leaving at most once: O(n), despite the loop inside the loop.

Why shrinking is safe

left never moves back, so once it passes an index no later window starts there. That cannot miss the answer because the rule is monotone: a repeat-free window stays so when shrunk, and a window with a repeat keeps it when grown:

1. Each cell is one window: start by row, right end by column, its length written in when it has no repeated letter (teal). The brute force checks all 36 windows.
2. The rule is monotone: a window with no repeat stays repeat-free when shrunk, and one with a repeat keeps it when grown. So down each column the valid windows form one block, ending at the diagonal — here the column for right = 6.
3. The top of each block is the best start for that right end, and as right moves on it never moves up: 0, 0, 0, 1, 2, 3, 5, 7. So left can be carried forward instead of restarting — at most n moves in all.
4. The answer is the tallest block, length 3, first at right = 2. The loop walks only the staircase — about 2n steps — and never looks at the 18 broken windows above it.

That is the loop's invariant: after the shrink loop, the window from left to right is the longest valid window ending at right. Every substring ends somewhere, so the best over all right is the best overall. Before writing any window, ask: does shrinking a valid window keep it valid? If not, the window is the wrong tool.

The code

The program records only a strictly longer window, so for "pwwkew" it reports "wke", the first of the two longest answers.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

// Longest substring of s with no repeated character, found by grow-then-shrink.
string longestDistinct(const string& s) {
    unordered_map<char, int> count;   // how many times each character is in the window
    int left = 0, bestLeft = 0, bestLen = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        count[s[right]]++;                     // grow: s[right] enters
        while (count[s[right]] > 1) {          // shrink until the window is valid again
            count[s[left]]--;
            left++;
        }
        if (right - left + 1 > bestLen) {      // valid here: record it
            bestLen = right - left + 1;
            bestLeft = left;
        }
    }
    return s.substr(bestLeft, bestLen);
}

int main() {
    for (string s : {"abcabcbb", "bbbbb", "pwwkew"}) {
        string best = longestDistinct(s);
        cout << "\"" << s << "\" -> " << best.size() << " (\"" << best << "\")\n";
    }
    return 0;
}

import java.util.HashMap;
import java.util.Map;

public class Main {
    // Longest substring of s with no repeated character, found by grow-then-shrink.
    static String longestDistinct(String s) {
        Map<Character, Integer> count = new HashMap<>(); // how many times each character is in the window
        int left = 0, bestLeft = 0, bestLen = 0;
        for (int right = 0; right < s.length(); right++) {
            char in = s.charAt(right);
            count.merge(in, 1, Integer::sum);            // grow: s[right] enters
            while (count.get(in) > 1) {                  // shrink until the window is valid again
                count.merge(s.charAt(left), -1, Integer::sum);
                left++;
            }
            if (right - left + 1 > bestLen) {            // valid here: record it
                bestLen = right - left + 1;
                bestLeft = left;
            }
        }
        return s.substring(bestLeft, bestLeft + bestLen);
    }

    public static void main(String[] args) {
        for (String s : new String[] {"abcabcbb", "bbbbb", "pwwkew"}) {
            String best = longestDistinct(s);
            System.out.println("\"" + s + "\" -> " + best.length() + " (\"" + best + "\")");
        }
    }
}

def longest_distinct(s):
    """Longest substring of s with no repeated character, found by grow-then-shrink."""
    count = {}                     # how many times each character is in the window
    left = best_left = best_len = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1   # grow: s[right] enters
        while count[ch] > 1:               # shrink until the window is valid again
            count[s[left]] -= 1
            left += 1
        if right - left + 1 > best_len:    # valid here: record it
            best_len = right - left + 1
            best_left = left
    return s[best_left:best_left + best_len]


for s in ("abcabcbb", "bbbbb", "pwwkew"):
    best = longest_distinct(s)
    print(f'"{s}" -> {len(best)} ("{best}")')

// Longest substring of s with no repeated character, found by grow-then-shrink.
function longestDistinct(s) {
  const count = new Map(); // how many times each character is in the window
  let left = 0;
  let bestLeft = 0;
  let bestLen = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    count.set(ch, (count.get(ch) || 0) + 1); // grow: s[right] enters
    while (count.get(ch) > 1) {
      // shrink until the window is valid again
      count.set(s[left], count.get(s[left]) - 1);
      left++;
    }
    if (right - left + 1 > bestLen) {
      // valid here: record it
      bestLen = right - left + 1;
      bestLeft = left;
    }
  }
  return s.slice(bestLeft, bestLeft + bestLen);
}

for (const s of ["abcabcbb", "bbbbb", "pwwkew"]) {
  const best = longestDistinct(s);
  console.log(`"${s}" -> ${best.length} ("${best}")`);
}

"abcabcbb" -> 3 ("abc")
"bbbbb" -> 1 ("b")
"pwwkew" -> 3 ("wke")

For a small known alphabet, an array of counts indexed by character code (26 or 128 slots) does the map's job faster.

The shortest window: shrink while it is still valid

Longest-window loops shrink while the window is invalid, then record. Shortest-window loops shrink while it is still valid, recording each step. Minimum Size Subarray Sum wants the shortest run of positive numbers summing to at least a target:

1. Grow until the sum reaches 7: 2, 3, 1, 2 enter, sum 8. Valid, so record length 4 — the shortest yet, then drop 2 from the left to try a shorter window.
2. 4 enters: sum 10. Valid, so record length 4, no shorter than 4, then drop 3 from the left to try a shorter window.
3. Still 7 ≥ 7. Valid, so record length 3 — the shortest yet, then drop 1 from the left to try a shorter window.
4. 3 enters: sum 9. Valid, so record length 3, no shorter than 3, then drop 2 from the left to try a shorter window.
5. Still 7 ≥ 7. Valid, so record length 2 — the shortest yet, then drop 4 from the left to try a shorter window.
6. After the last drop the sum is 3 < 7 and right has reached the end. The shortest window is 4..5, length 2: every start that had a valid window got its shortest one recorded.

That is enough because before every grow the sum is below the target, and with positive numbers every window inside a too-small one is too small too — so each start's shortest valid window is recorded before left moves past it.

The code

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

// Shortest stretch of positive numbers whose sum is at least target.
// Returns {length, start}, or {0, -1} when no stretch reaches it.
pair<int, int> shortestWithSum(const vector<int>& nums, int target) {
    int left = 0, sum = 0, bestLen = 0, bestStart = -1;
    for (int right = 0; right < (int)nums.size(); right++) {
        sum += nums[right];                               // grow
        while (sum >= target) {                           // valid: record, then try shorter
            if (bestLen == 0 || right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestStart = left;
            }
            sum -= nums[left];                            // shrink
            left++;
        }
    }
    return {bestLen, bestStart};
}

int main() {
    vector<int> nums = {2, 3, 1, 2, 4, 3};
    for (int target : {7, 100}) {
        pair<int, int> r = shortestWithSum(nums, target);
        if (r.first == 0) {
            cout << "No subarray reaches " << target << "\n";
        } else {
            cout << "Shortest subarray with sum >= " << target << ": length " << r.first
                 << " (indices " << r.second << " to " << r.second + r.first - 1 << ")\n";
        }
    }
    return 0;
}

public class Main {
    // Shortest stretch of positive numbers whose sum is at least target.
    // Returns {length, start}, or {0, -1} when no stretch reaches it.
    static int[] shortestWithSum(int[] nums, int target) {
        int left = 0, sum = 0, bestLen = 0, bestStart = -1;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];                               // grow
            while (sum >= target) {                           // valid: record, then try shorter
                if (bestLen == 0 || right - left + 1 < bestLen) {
                    bestLen = right - left + 1;
                    bestStart = left;
                }
                sum -= nums[left];                            // shrink
                left++;
            }
        }
        return new int[] {bestLen, bestStart};
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3};
        for (int target : new int[] {7, 100}) {
            int[] r = shortestWithSum(nums, target);
            if (r[0] == 0) {
                System.out.println("No subarray reaches " + target);
            } else {
                System.out.println("Shortest subarray with sum >= " + target + ": length " + r[0]
                        + " (indices " + r[1] + " to " + (r[1] + r[0] - 1) + ")");
            }
        }
    }
}

def shortest_with_sum(nums, target):
    """Shortest stretch of positive numbers whose sum is at least target.
    Return (length, start), or (0, -1) when no stretch reaches it."""
    left = total = best_len = 0
    best_start = -1
    for right in range(len(nums)):
        total += nums[right]                  # grow
        while total >= target:                # valid: record, then try shorter
            if best_len == 0 or right - left + 1 < best_len:
                best_len = right - left + 1
                best_start = left
            total -= nums[left]               # shrink
            left += 1
    return best_len, best_start


nums = [2, 3, 1, 2, 4, 3]
for target in (7, 100):
    length, start = shortest_with_sum(nums, target)
    if length == 0:
        print(f"No subarray reaches {target}")
    else:
        print(f"Shortest subarray with sum >= {target}: length {length} "
              f"(indices {start} to {start + length - 1})")

// Shortest stretch of positive numbers whose sum is at least target.
// Returns [length, start], or [0, -1] when no stretch reaches it.
function shortestWithSum(nums, target) {
  let left = 0;
  let sum = 0;
  let bestLen = 0;
  let bestStart = -1;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right]; // grow
    while (sum >= target) {
      // valid: record, then try shorter
      if (bestLen === 0 || right - left + 1 < bestLen) {
        bestLen = right - left + 1;
        bestStart = left;
      }
      sum -= nums[left]; // shrink
      left++;
    }
  }
  return [bestLen, bestStart];
}

const nums = [2, 3, 1, 2, 4, 3];
for (const target of [7, 100]) {
  const [length, start] = shortestWithSum(nums, target);
  if (length === 0) {
    console.log(`No subarray reaches ${target}`);
  } else {
    console.log(`Shortest subarray with sum >= ${target}: length ${length} (indices ${start} to ${start + length - 1})`);
  }
}

Shortest subarray with sum >= 7: length 2 (indices 4 to 5)
No subarray reaches 100

With a count map instead of a sum, the same loop is the heart of Minimum Window Substring: grow until the window holds every pattern character, then shrink while it still does.

Why it is O(n), not O(n²)

Count pointer moves, not loop iterations. right moves n times; left only moves forwards, so across the whole run it moves at most n times. Every element enters once and leaves at most once: at most 2n steps, amortised over the run.

Counting windows: exactly K = at most K − at most (K − 1)

To count subarrays under a monotone rule, add right - left + 1 after each shrink: every start from left to right is valid. "Exactly K distinct" is not monotone, so count two things that are, and subtract:

1. "At most 2 distinct" is monotone, so a window counts it: after shrinking, every start from left to right gives a valid subarray ending at right — right − left + 1 of them. The same loop runs for at most 1.
2. right = 1: at most 2 keeps 0..1 and adds 2; at most 1 keeps 1..1 and adds 1.
3. right = 2: at most 2 keeps 0..2 and adds 3; at most 1 keeps 2..2 and adds 1.
4. right = 3: at most 2 keeps 0..3 and adds 4; at most 1 keeps 3..3 and adds 1.
5. right = 4: at most 2 keeps 3..4 and adds 2; at most 1 keeps 4..4 and adds 1. A third distinct value forced the first window to shrink.
6. A subarray with at most 2 distinct values has either exactly 2 or at most 1, never both, so subtracting leaves exactly 2: 12 − 5 = 7 subarrays. "Exactly" is not monotone; the two "at most" counts are.

That is Subarrays with K Different Integers, and the same subtraction solves Count Number of Nice Subarrays and Binary Subarrays With Sum.

When the window does not work: negative numbers

Every argument above leaned on monotonicity, and for sums that needs non-negative numbers. Without it the window fails silently:

1. The window grows to the whole array and its sum is 3 < 4. The shrink loop only runs once the sum reaches the target, so it never runs, and the program reports that no subarray reaches 4.
2. Yet [4] alone reaches 4. Dropping −1 would raise the sum — the one move the shrink rule never makes, because it assumes removing an element can only lower it. With negatives, use prefix sums.

When an array can hold negatives, switch tools:

• "How many subarrays sum to k?" Prefix sums with a hash map — see Prefix Sum and Subarray Sum Equals K.
• "The shortest subarray with sum at least k?" Prefix sums with a monotonic deque, as in Shortest Subarray with Sum at Least K.
• "The largest sum of any subarray?" Not a window question: Kadane's algorithm.

Other shapes of the same idea

• At most k bad elements: Max Consecutive Ones III, the longest window with at most k zeroes.
• A window of distance k: Contains Duplicate II, a set of the last k values.
• The window's maximum: Sliding Window Maximum, a deque of decreasing values — the monotonic stack idea on a queue.

Time and space complexity

How to recognise a sliding window problem

• The answer is a contiguous subarray or substring: "consecutive", "substring", "subarray", "in a row".
• It asks for the longest, shortest, largest sum or number of such stretches.
• A length k is given: a fixed window. A rule is given: a variable window.
• The rule is monotone; for sums, the numbers cannot be negative.

"Subsequence" is a warning sign: it may skip elements, so it is not a window — think dynamic programming.

Common mistakes

• A window on negative numbers. Check the constraints first.
• Recording at the wrong moment. Longest: after the shrink loop. Shortest: inside it, before each removal.
• Off by one. The window holds right - left + 1 elements; in a fixed window the leaver is arr[right - k].
• Not undoing the state exactly. Each step of left must reverse what adding that element did; delete zero counts if you use the map's size.
• Restarting left for every right. That is the O(n²) brute force again.

Practice in this order

1. Maximum Sum Subarray of Size K: the fixed window.
2. Contains Duplicate II: a fixed window whose state is a set.
3. Longest Substring Without Repeating Characters: grow, then shrink.
4. Minimum Size Subarray Sum: shrink while valid.
5. Max Consecutive Ones III: "at most k zeroes".
6. Permutation in String: a fixed window of letter counts.
7. Longest Repeating Character Replacement: a rule built from the top letter.
8. Minimum Window Substring: the classic hard one.
9. Subarrays with K Different Integers: exactly K by subtraction.

Every window problem is on the sliding window problem list. Next on the road: Prefix Sum, for the subarray questions a window cannot handle.