Sliding Window Technique: Fixed & Variable Window Problems Explained

Sliding window is the first pattern most people learn after hashing, and it carries a big share of string and array questions. Plenty of candidates still get stuck on it in interviews. The reason is rarely that they never heard of it. They memorised solutions to individual problems instead of the two or three skeletons behind them, so a small change (count instead of longest, or "exactly K" instead of "at most K") throws them off.

This guide is built around those skeletons. Every problem is solved with one of three templates, and for each one I show which part of the template changed. If you can write the templates from memory and explain why each pointer only moves forward, you can handle the variations.

What Is the Sliding Window Technique?

Take the simplest version: given an array and a number k, find the maximum sum of any k consecutive elements. The brute force recomputes each window from scratch:

def max_sum_brute(nums, k):
    best = float('-inf')
    for i in range(len(nums) - k + 1):
        best = max(best, sum(nums[i:i + k]))   # k work per window
    return best

Neighbouring windows share k−1 elements, though. Window [i, i+k−1] and window [i+1, i+k] differ by exactly one element leaving on the left and one entering on the right. So instead of summing k numbers, you do one subtraction and one addition. That's the whole idea: maintain the window's state incrementally as its boundaries move.

The "state" is whatever you need to answer the question about the current window:

Why is it O(n) when there is a nested loop in the variable-size version? Because the left pointer never moves backwards. Over the whole run, right moves n times and left moves at most n times, so the inner while loop executes at most n times in total, not n times per outer iteration. That argument is worth saying out loud in an interview; it's the first follow-up most interviewers ask.

When Does the Sliding Window Pattern Apply?

Check these three signals before you reach for it:

1. Contiguity. The question is about a subarray or substring, not a subsequence. "Pick any elements" means DP or greedy, not a window.
2. An optimisation or count over windows. Longest, shortest, maximum sum, number of windows, every window of size k.
3. Monotonic validity. If a window is invalid, every bigger window containing it is also invalid (or the reverse for "shortest valid" problems). That's what makes it safe to move left forward and never look back.

The third signal is the one people skip. "At most 2 distinct characters" is monotonic: adding characters can only increase the distinct count. "Sum equals exactly k" with negative numbers is not: a window can overshoot and come back. When the monotonic property is missing, the window approach silently gives wrong answers, which is worse than failing loudly.

Fixed-Size Sliding Window: Template and Problems

When the window size k is given, both pointers move in lockstep. The cleanest way to write it is a single loop over right, where the element at right − k falls out once the window is full.

def fixed_window(nums, k):
    state = init()
    answer = None
    for right in range(len(nums)):
        add(state, nums[right])              # element enters
        if right >= k:
            remove(state, nums[right - k])   # element leaves
        if right >= k - 1:                   # window [right-k+1, right] is full
            answer = combine(answer, state)
    return answer

Writing it this way avoids the separate "build the first window" loop that causes so many off-by-one bugs.

Problem 1: Maximum Average Subarray I (LeetCode 643)

Find the maximum average of any contiguous subarray of length k. Maximising the average is the same as maximising the sum, so track a running sum and divide once at the end.

def findMaxAverage(nums, k):
    window = 0
    best = float('-inf')
    for right, x in enumerate(nums):
        window += x
        if right >= k:
            window -= nums[right - k]
        if right >= k - 1:
            best = max(best, window)
    return best / k

double findMaxAverage(vector<int>& nums, int k) {
    long long window = 0, best = LLONG_MIN;
    for (int right = 0; right < (int)nums.size(); ++right) {
        window += nums[right];
        if (right >= k) window -= nums[right - k];
        if (right >= k - 1) best = max(best, window);
    }
    return (double)best / k;
}

Dry run on nums = [1, 12, -5, -6, 50, 3], k = 4: the windows are [1,12,−5,−6] = 2, [12,−5,−6,50] = 51, [−5,−6,50,3] = 42. Best sum is 51, answer 12.75. Note the long long in C++: with values up to 10⁴ and k up to 10⁵ an int would survive, but interviewers like seeing you think about overflow.

Problem 2: Find All Anagrams in a String (LeetCode 438)

Return every start index in s where a permutation of p begins. A window is an anagram of p exactly when its letter counts equal p's letter counts, and the window size is fixed at len(p).

def findAnagrams(s, p):
    k = len(p)
    if k > len(s):
        return []
    need = [0] * 26
    have = [0] * 26
    for c in p:
        need[ord(c) - 97] += 1
    res = []
    for right, c in enumerate(s):
        have[ord(c) - 97] += 1
        if right >= k:
            have[ord(s[right - k]) - 97] -= 1
        if right >= k - 1 and have == need:
            res.append(right - k + 1)
    return res

vector<int> findAnagrams(const string& s, const string& p) {
    int k = p.size();
    vector<int> res;
    if (k > (int)s.size()) return res;
    array<int, 26> need{}, have{};
    for (char c : p) need[c - 'a']++;
    for (int right = 0; right < (int)s.size(); ++right) {
        have[s[right] - 'a']++;
        if (right >= k) have[s[right - k] - 'a']--;
        if (right >= k - 1 && have == need) res.push_back(right - k + 1);
    }
    return res;
}

Each comparison costs 26, so this is O(26·n), which is O(n). If the interviewer pushes for a true O(1) per step, keep a counter matches of how many of the 26 letters currently have equal counts and update it only for the two letters that changed. The same code with a one-line change solves Permutation in String (567): return true the first time the arrays match.

Problem 3: Sliding Window Maximum (LeetCode 239)

Return the maximum of every window of size k. A running sum doesn't help here because when the maximum leaves the window you have no idea what the next maximum is. The fix is a monotonic deque of indices whose values are decreasing from front to back. The front is always the current window's maximum.

from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()          # indices, values strictly decreasing
    res = []
    for i, x in enumerate(nums):
        if dq and dq[0] <= i - k:          # front fell out of window
            dq.popleft()
        while dq and nums[dq[-1]] <= x:    # smaller values can never be max again
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> res;
    for (int i = 0; i < (int)nums.size(); ++i) {
        if (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) res.push_back(nums[dq.front()]);
    }
    return res;
}

Dry run on [1, 3, -1, -3, 5, 3, 6, 7], k = 3:

Each index is pushed and popped at most once, so the whole thing is O(n) with O(k) extra space. The full walkthrough, including the heap alternative and why it is O(n log n), is in the LeetCode 239 deep dive, and the deque idea itself is covered in monotonic stack and queue problems.

Variable-Size Sliding Window: Longest and Shortest Templates

When k is not given, the window grows and shrinks based on a condition. There are two mirror-image templates, and picking the wrong one is the most common bug I see in mock interviews.

# Template A: longest window satisfying a condition
def longest(nums):
    left = 0
    best = 0
    for right in range(len(nums)):
        add(nums[right])
        while invalid():
            remove(nums[left])
            left += 1
        best = max(best, right - left + 1)    # window is valid here
    return best

# Template B: shortest window satisfying a condition
def shortest(nums):
    left = 0
    best = float('inf')
    for right in range(len(nums)):
        add(nums[right])
        while valid():
            best = min(best, right - left + 1)  # record BEFORE shrinking
            remove(nums[left])
            left += 1
    return 0 if best == float('inf') else best

Notice where the answer is recorded. In Template A it's after the while loop, because the loop restores validity. In Template B it's inside the loop, because the loop runs only while the window is valid. Swap those two positions and you'll get an answer that is off by one window.

Problem 4: Longest Substring Without Repeating Characters (LeetCode 3)

Template A with "invalid = some character appears twice". Because only the newly added character can be duplicated, you can check just that one.

def lengthOfLongestSubstring(s):
    seen = set()
    left = best = 0
    for right, c in enumerate(s):
        while c in seen:            # window invalid once c is added
            seen.remove(s[left])
            left += 1
        seen.add(c)
        best = max(best, right - left + 1)
    return best

The optimised version jumps left directly past the previous occurrence instead of stepping one by one. It's still O(n) but with fewer operations, and it's the version most interviewers expect as a follow-up:

int lengthOfLongestSubstring(const string& s) {
    vector<int> last(256, -1);      // last index of each byte
    int left = 0, best = 0;
    for (int right = 0; right < (int)s.size(); ++right) {
        unsigned char c = s[right];
        if (last[c] >= left) left = last[c] + 1;   // only jump forward
        last[c] = right;
        best = max(best, right - left + 1);
    }
    return best;
}

The last[c] >= left guard matters. On "abba", when right reaches the final 'a', its last index is 0, but left is already 2. Without the guard, left would jump back to 1 and the answer would be 3 instead of 2. There's a full breakdown in the LeetCode 3 explainer.

Problem 5: Longest Repeating Character Replacement (LeetCode 424)

You may replace at most k characters. A window can become all one letter if window_length − max_frequency ≤ k, so that's the validity condition.

def characterReplacement(s, k):
    count = [0] * 26
    left = max_freq = best = 0
    for right, c in enumerate(s):
        count[ord(c) - 65] += 1
        max_freq = max(max_freq, count[ord(c) - 65])
        while (right - left + 1) - max_freq > k:
            count[ord(s[left]) - 65] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

int characterReplacement(const string& s, int k) {
    array<int, 26> cnt{};
    int left = 0, maxFreq = 0, best = 0;
    for (int right = 0; right < (int)s.size(); ++right) {
        maxFreq = max(maxFreq, ++cnt[s[right] - 'A']);
        while (right - left + 1 - maxFreq > k) {
            cnt[s[left] - 'A']--;
            left++;
        }
        best = max(best, right - left + 1);
    }
    return best;
}

The subtle part: max_freq is never decreased when characters leave. That looks like a bug, but it isn't. The answer only improves when a window has a higher max frequency than anything seen before, so a stale, too-high max_freq can only keep the window from shrinking when it "should". It never produces a length larger than a real valid window. Interviewers love asking about this line. If you can't justify it on the spot, recompute the max over the 26 counts inside the loop; O(26n) is still linear.

Problem 6: Max Consecutive Ones III (LeetCode 1004)

Longest subarray of 1s if you can flip at most k zeros. Restated: longest window containing at most k zeros. That's Template A with a zero counter.

def longestOnes(nums, k):
    left = zeros = best = 0
    for right, x in enumerate(nums):
        zeros += (x == 0)
        while zeros > k:
            zeros -= (nums[left] == 0)
            left += 1
        best = max(best, right - left + 1)
    return best

int longestOnes(vector<int>& nums, int k) {
    int left = 0, zeros = 0, best = 0;
    for (int right = 0; right < (int)nums.size(); ++right) {
        if (nums[right] == 0) zeros++;
        while (zeros > k) {
            if (nums[left] == 0) zeros--;
            left++;
        }
        best = max(best, right - left + 1);
    }
    return best;
}

The skill being tested is the restatement. "Flip at most k" sounds like a choice problem; "window with at most k zeros" is a counting condition. Many window problems are disguised this way.

Problem 7: Fruit Into Baskets (LeetCode 904)

Another disguise: two baskets, each holds one fruit type, pick a contiguous run. Translation: longest subarray with at most 2 distinct values.

from collections import defaultdict

def totalFruit(fruits):
    count = defaultdict(int)
    left = best = 0
    for right, f in enumerate(fruits):
        count[f] += 1
        while len(count) > 2:
            count[fruits[left]] -= 1
            if count[fruits[left]] == 0:
                del count[fruits[left]]     # keep len(count) = distinct
            left += 1
        best = max(best, right - left + 1)
    return best

int totalFruit(vector<int>& fruits) {
    unordered_map<int, int> cnt;
    int left = 0, best = 0;
    for (int right = 0; right < (int)fruits.size(); ++right) {
        cnt[fruits[right]]++;
        while (cnt.size() > 2) {
            if (--cnt[fruits[left]] == 0) cnt.erase(fruits[left]);
            left++;
        }
        best = max(best, right - left + 1);
    }
    return best;
}

Forgetting to delete zero-count keys is the classic bug: the map size then overcounts distinct values and the window shrinks too far. Replace 2 with k and you've solved "Longest Substring with At Most K Distinct Characters" (LeetCode 340, premium).

Problem 8: Minimum Size Subarray Sum (LeetCode 209)

Now the mirror image. Find the shortest subarray whose sum is at least target, with all numbers positive. Because the numbers are positive, a valid window stays valid as it grows, so Template B applies.

def minSubArrayLen(target, nums):
    left = window = 0
    best = float('inf')
    for right, x in enumerate(nums):
        window += x
        while window >= target:
            best = min(best, right - left + 1)
            window -= nums[left]
            left += 1
    return 0 if best == float('inf') else best

int minSubArrayLen(int target, vector<int>& nums) {
    int left = 0, best = INT_MAX;
    long long window = 0;
    for (int right = 0; right < (int)nums.size(); ++right) {
        window += nums[right];
        while (window >= target) {
            best = min(best, right - left + 1);
            window -= nums[left++];
        }
    }
    return best == INT_MAX ? 0 : best;
}

Dry run with target = 7, nums = [2, 3, 1, 2, 4, 3]:

Answer 2, the window [4, 3]. The follow-up the problem itself suggests is an O(n log n) solution: prefix sums are increasing (all positive), so for each start you can binary search for the first prefix that reaches target. It's slower than the window but a good way to show you know binary search on monotonic arrays.

Problem 9: Minimum Window Substring (LeetCode 76)

The hardest of the classic set. Find the smallest window of s that contains every character of t, with multiplicity. It's Template B where "valid" means "no characters of t are still missing". The trick that makes validity O(1) is a single integer missing instead of comparing two maps.

from collections import Counter

def minWindow(s, t):
    need = Counter(t)          # how many more of each char we still need
    missing = len(t)           # total chars still needed
    left = 0
    best_len, best_start = float('inf'), 0
    for right, c in enumerate(s):
        if need[c] > 0:
            missing -= 1
        need[c] -= 1           # can go negative: surplus copies
        while missing == 0:
            if right - left + 1 < best_len:
                best_len, best_start = right - left + 1, left
            need[s[left]] += 1
            if need[s[left]] > 0:   # we just dropped a char we needed
                missing += 1
            left += 1
    return "" if best_len == float('inf') else s[best_start:best_start + best_len]

string minWindow(const string& s, const string& t) {
    vector<int> need(128, 0);
    for (char c : t) need[c]++;
    int missing = t.size(), left = 0, bestLen = INT_MAX, bestStart = 0;
    for (int right = 0; right < (int)s.size(); ++right) {
        if (need[s[right]]-- > 0) missing--;
        while (missing == 0) {
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestStart = left;
            }
            if (++need[s[left]] > 0) missing++;
            left++;
        }
    }
    return bestLen == INT_MAX ? "" : s.substr(bestStart, bestLen);
}

Why does a negative need make sense? It means the window holds surplus copies, or characters not in t at all. When such a character leaves, its count rises but stays at most zero, so missing is unaffected. Only when a count crosses from 0 to 1 did we lose something we actually needed. Run it by hand on s = "ADOBECODEBANC", t = "ABC" and you'll get "BANC". The step-by-step trace is in the LeetCode 76 walkthrough.

The At-Most-K Trick: Counting Subarrays with Exactly K

Counting problems add a twist. If Template A gives you the longest valid window ending at each right, then every window ending at right with a start in [left, right] is also valid (shrinking a valid window keeps it valid). That's right − left + 1 windows, so:

def count_at_most(nums, K):
    left = total = 0
    for right in range(len(nums)):
        add(nums[right])
        while invalid(K):
            remove(nums[left])
            left += 1
        total += right - left + 1     # all valid windows ending at right
    return total

"Exactly K" isn't monotonic. A window with exactly 2 distinct values can grow into one with 3 and you can't tell, at the moment of shrinking, whether you've gone too far. The way around it is set subtraction:

windows with exactly K = windows with at most K − windows with at most K−1

Problem 10: Subarrays with K Different Integers (LeetCode 992)

from collections import defaultdict

def subarraysWithKDistinct(nums, k):
    def at_most(K):
        count = defaultdict(int)
        left = total = 0
        for right, x in enumerate(nums):
            count[x] += 1
            while len(count) > K:
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    del count[nums[left]]
                left += 1
            total += right - left + 1
        return total
    return at_most(k) - at_most(k - 1)

class Solution {
    int atMost(const vector<int>& nums, int K) {
        unordered_map<int, int> cnt;
        int left = 0, total = 0;
        for (int right = 0; right < (int)nums.size(); ++right) {
            cnt[nums[right]]++;
            while ((int)cnt.size() > K) {
                if (--cnt[nums[left]] == 0) cnt.erase(nums[left]);
                left++;
            }
            total += right - left + 1;
        }
        return total;
    }
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }
};

Dry run on nums = [1, 2, 1, 2, 3], k = 2. For atMost(2), the counts added per right are 1, 2, 3, 4, and then at right = 4 the 3 forces left to index 3, adding 2: total 12. For atMost(1), every step leaves a single-element window, total 5. Answer 12 − 5 = 7, which matches the seven subarrays [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

The same trick solves Count Number of Nice Subarrays (1248) (exactly k odd numbers) and Binary Subarrays With Sum (930) (exactly goal ones, all values 0/1). Note that 930 only works with the window because values are non-negative; that leads straight into the next section.

When Sliding Window Fails (and What to Use Instead)

Knowing when not to use the pattern is half the skill. These are the usual traps:

A concrete counterexample helps you remember. Run the Problem 8 code on LeetCode 862's example: nums = [84, -37, 32, 40, 95], target 167. The sum climbs 84, 47, 79, 119, 214. At 214 it records length 5, drops 84 and sees 130, which is below target, so it stops shrinking. But the next element to leave is −37, and dropping it would raise the sum back to 167 with the window [32, 40, 95] of length 3. The template returns 5; the right answer is 3. The window logic assumed "removing elements only lowers the sum", and a single negative number broke that. The prefix-sum alternatives are covered in prefix sum and difference array problems.

How Sliding Window Shows Up in Interviews

Sliding window questions are popular because they reward a specific reasoning step: noticing that brute force recomputes overlapping work. Interviewers are looking for that insight, a correct template, and a crisp complexity argument.

How to present your solution

1. State the brute force and its cost. "Checking every substring is O(n²) windows, O(n³) if I validate each from scratch."
2. Name the overlap. "Adjacent windows share all but one element, so I can update state incrementally."
3. State the validity condition and why it's monotonic. "Once a window has a repeat, any extension still has it, so the left pointer never needs to move back."
4. Pick the template out loud. "This is longest-valid, so I shrink while invalid and record after the loop."
5. Prove O(n). "Each pointer moves at most n times in total."
6. Test edge cases: empty input, k larger than n, all identical elements, the answer being the whole array, no valid window.

Follow-ups interviewers commonly ask

• "Can you make the per-step cost O(1)?" For anagram windows, replace array comparison with a matches counter.
• "What if the input is a stream?" Fixed-size windows work naturally on streams with a circular buffer. Variable windows need you to store the elements between left and right.
• "What if the characters are Unicode?" Switch from a 26/128 array to a hash map; complexity is unchanged in expectation.
• "Return the window, not just the length." Track best start alongside best length, as in problem 9.
• "What if numbers can be negative?" This is the trap question. Explain why monotonicity breaks and switch to prefix sums.

Red flags that cost candidates the round

• Moving left backwards, or resetting left to right + 1 on a violation. That works for some problems by accident and fails on others ("abba" above).
• Recording the answer in the wrong place for the template.
• Using len(map) as the distinct count without deleting zero-count keys.
• Claiming O(n²) because "there's a nested loop", or claiming O(n) without being able to explain why.

If you're still building the habit of talking through this reasoning, the guide on thinking out loud in coding interviews has scripts for exactly these moments.

Sliding Window Practice List by Difficulty

Do these in order. For each one, before writing code, write a single line: template, state, validity condition. If you can't write that line, you don't understand the problem yet.

Fifteen problems is enough to own the pattern. After that, mix them with two pointers problems in timed sets, so you practise the decision of which pattern to use and not just how to use it. In a real interview nobody tells you "this is a sliding window question".

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.