DSA sheet · Arrays & Strings · Sliding Window pattern

Sliding Window Patterns Overview

This is the concept video that opens the sliding window series. The teacher doesn't solve one problem fully. Instead she shows how to recognise a sliding window question and splits them into four types, each with one LeetCode example: a fixed-size window, a dynamic (variable-size) window, a window with a frequency map, and a "longest window after at most k changes" window. For each type she explains the moves of the two pointers on a small example.

Why it matters: almost every "best / count of contiguous subarray or substring" question in interviews is one of these four shapes. If you can name the shape in the first minute, the code is mostly a template. The rest of this notebook (problems 2–14) is just these templates applied again and again.

This concept page uses the 9 steps adapted for a pattern video:
① what a window is → ② how to spot a sliding-window problem → ③ brute force vs window (why it's faster) → ④ fixed vs variable, side by side → ⑤–⑧ each pattern she lists (idea, tiny example, dry run, Python template) → ⑨ which sheet problems use which pattern & remember

• Part 0 · Sliding window from scratch (window, expand, shrink, fixed vs variable)
• Part A · Pattern 1: fixed-size window (Maximum Average Subarray)
• Part B · Pattern 2: dynamic window, shortest/longest (Minimum Size Subarray Sum)
• Part C · Pattern 3: window + frequency map (Permutation in String)
• Part D · Pattern 4: longest window with at most k changes (Character Replacement)
• Part E · Extra shapes used later in the sheet (counting, exactly K, monotonic deque)
• Part F · Revision page (which problem → which pattern)

Part 0 · Before starting

1What is a window?

A subarray is a piece of an array where the elements sit next to each other (contiguous). For a string, the same thing is called a substring. You pick a start and an end and take everything in between. You may not skip anything in the middle.

The teacher's point: a subarray is exactly what we call a window. A window of length 2 is called a "window of size 2".

We describe a window with two indexes: left (first cell inside) and right (last cell inside). We write it as [left..right], both ends included. Its length is right − left + 1.

2The two moves: expand and shrink

• Expand = move right one step to the right. A new cell joins the window. We update our running info (sum, count, map) by adding that one cell.
• Shrink = move left one step to the right. The oldest cell leaves the window. We update our info by removing that one cell.

Both pointers only ever move forward. Neither ever goes back. That one fact is why sliding window is fast (step 3 below).

In this notebook the array is drawn as boxes: yellow = inside the window, grey = already left behind (it will never come back), plain = not reached yet. The row under it shows where L and R stand.

3Why not just check every window? (brute force vs sliding)

The simple way is two loops: for every start, walk an end pointer forward and recompute the window's sum or count. There are about n²/2 windows, so this is O(n²) (or O(n·k) when the size is fixed at k).

The teacher's observation, on her fixed-size example: when you move from one window to the next, most of the cells are the same. Window 1 = [10, 12, −5, −45], window 2 = [12, −5, −45, 30]. The three cells in the middle are in both. The brute force adds them again anyway. The only real change is one cell joined (30) and one cell left (10).

So instead of recomputing, we keep the old answer and do sum = sum + new_cell − old_cell. That's O(1) per move instead of O(k), and the whole scan becomes O(n).

4How to spot a sliding-window problem

Checklist built from the four patterns she shows (plus the pattern-picking she does in the next videos):

1. The question talks about a subarray or substring (contiguous). If it says "subsequence", it's not this pattern.
2. It wants something about everything inside the range (sum, average, count of chars, distinct values), not just the two end values. (Only the ends matter → two pointers.)
3. It asks for a maximum / minimum / longest / shortest / count of such windows, or "does one exist?".
4. When you grow the window, the thing you track changes in one direction only (sum only goes up when all numbers are positive, number of distinct chars only goes up, number of zeros only goes up). This is the monotonic condition (explained in step 6).
5. The constraints are big (n up to 10⁵ or 10⁶), so O(n²) would cross about 10⁸ operations and give TLE (Time Limit Exceeded). That's the hint that an O(n) idea exists.

5FIXED vs VARIABLE: the most important difference

Every sliding window is one of these two. Get this clear before anything else.

Fixed, k = 3. The window moves like a frame of constant width: both ends step together.

Variable, "shortest with sum ≥ 7". The width breathes: it grows while too small, shrinks while big enough.

6Why sliding window needs a monotonic condition

A variable window only works if we can decide without looking back: "growing can only make it worse (or better), shrinking can only fix it". For sums that's true only when every number is positive. With negatives, adding a number can make the sum smaller and removing one can make it bigger, so the window shrinks at the wrong time and skips answers.

My own tiny example: shortest subarray with sum ≥ 5 in [1, −1, 5]. The right answer is 1 (just [5]).

1. Add 1 → sum 1. Add −1 → sum 0. Add 5 → sum 5 ≥ 5 → record size 3.
2. Shrink: remove 1 → sum 4 < 5 → stop shrinking.
3. Right is at the end → answer 3. Wrong. Removing the −1 next would have pushed the sum back up to 5, but the window had already stopped.

That's why the teacher always checks the constraints for negative numbers. With negatives in a sum problem she reaches for prefix sum (counting exact sums) or Kadane's (maximum sum) instead. The fixed-size window is the exception: it never decides anything, it just slides, so negatives are fine there.

7Frequency maps in Python

Patterns 3 and 4 keep a frequency map: a dict from "item" to "how many times it is inside the window right now".

from collections import Counter

freq = {}
freq['a'] = freq.get('a', 0) + 1     # add one 'a' to the window
freq['a'] -= 1                       # one 'a' leaves the window
if freq['a'] == 0:
    del freq['a']                    # drop zero counts so len(freq) = number of distinct items

Counter("abca")                      # Counter({'a': 2, 'b': 1, 'c': 1}) - builds a map in one call

The teacher does exactly this in Pattern 3: when a character leaves, "first decrement the counter, and if it hits zero, remove the key". If you leave zero counts in the map, two maps that mean the same window will compare as different ({'a':1,'e':0} != {'a':1}).

Part A · Pattern 1: fixed-size window

her example: Maximum Average Subarray I (LeetCode 643)

1The idea in simple words

Use this when the question gives you the length k and asks for the max / min / average / sum of the windows of that length. The teacher says that when you see a fixed k with max or average, you can go for the fixed window straight away.

Her example: given an array and k = 4, return the largest average among all subarrays of length 4.

2Building it from her example

She reads the first numbers as 10, 12, −5, −45, then 30 (the rest of the array isn't read out, so I'll use these five).

1. First window: indexes 0 to 3 (0..3 is 4 cells = k). Add them up: 10 + 12 − 5 − 45 = −28. Average = −28 / 4 = −7. Keep a best variable for the maximum.
2. Second window: start one step later, at index 1. She points out that 12, −5, −45 are in both windows. The only new thing is +30 (joins on the right) and −10 (leaves on the left).
3. So you don't need all subarrays from scratch, only "a continuous chunk of length k", updated by one add and one subtract each step.
4. Her pointer setup: start i (left) at 0 and j (right) at k − 1, so [i..j] is exactly k cells. Each step: add nums[j+1], subtract nums[i], move both by one.

3Template (Python)

class Solution:
    def findMaxAverage(self, nums, k):
        window = sum(nums[:k])           # first window: indexes 0..k-1
        best = window
        for right in range(k, len(nums)):
            window += nums[right]        # new cell joins on the right
            window -= nums[right - k]    # oldest cell leaves on the left
            best = max(best, window)
        return best / k                  # same length for all, so max sum = max average

4Dry run (hand table)

nums = [10, 12, −5, −45, 30], k = 4.

Answer: −8 / 4 = −2.0. On LeetCode's own example [1, 12, −5, −6, 50, 3], k = 4, the same code gives 12.75.

Time O(n): the first window costs k, then n − k slides cost 1 each. Space O(1).

Part B · Pattern 2: dynamic (variable-size) window

her example: Minimum Size Subarray Sum (LeetCode 209)

1The idea in simple words

Now no length is given. The question asks for the longest or shortest (minimum / maximum length) subarray or substring that satisfies a condition. Finding that length is the whole job.

Her description of the moves: start the pointers somewhere, keep moving right until the condition changes, note the length, then move left forward, then move right again. The size is not fixed, so you have to track it yourself.

Her example: given nums = [2, 3, 1, 2, 4, 3] and target = 7, return the minimum length of a subarray whose sum is ≥ 7. (Answer: 2, the window [4, 3].)

2Building it from her example

1. Put both pointers (she calls them i and j) at index 0. Keep a total variable.
2. A window is valid only when its sum is ≥ 7. While the sum is less than 7, the window can't be an answer, so move j to the right.
3. Add 2 → 2 (less). Move j, add 3 → 5 (less). Move j, add 1 → 6 (less). Move j, add 2 → 8 ≥ 7. Now [0..3] is valid.
4. Its length: j − i + 1 = 3 − 0 + 1 = 4. Keep a min_len variable and compare.
5. Then (her "decrement from the left"): move i forward to try a shorter window, while it stays valid. Then move j again. Repeat until j has passed the end.

3Templates (Python)

class Solution:
    def minSubArrayLen(self, target, nums):
        left = 0
        total = 0
        best = float('inf')
        for right in range(len(nums)):
            total += nums[right]                 # expand
            while total >= target:               # valid -> try to make it shorter
                best = min(best, right - left + 1)
                total -= nums[left]              # shrink
                left += 1
        return 0 if best == float('inf') else best

class Solution:
    def longestSumAtMost(self, nums, limit):
        # longest subarray with sum <= limit (all nums positive)
        left = 0
        total = 0
        best = 0
        for right in range(len(nums)):
            total += nums[right]                 # expand
            while total > limit and left <= right:   # invalid -> shrink until valid
                total -= nums[left]
                left += 1
            best = max(best, right - left + 1)   # valid now, record
        return best

4Dry run (hand table)

nums = [2, 3, 1, 2, 4, 3], target = 7.

Time O(n): right visits each index once and left visits each index at most once, so at most 2n moves in total, even though there's a while inside a for. Space O(1).

Part C · Pattern 3: window + frequency map

her example: Permutation in String (LeetCode 567)

1The idea in simple words

Here the condition is about how many times each character (or number) appears in the window. So besides the two pointers we keep a hash map of counts for the window. Hints in the question: "at most K distinct characters", "all characters appear the same number of times", "anagram", "permutation".

Her example: given strings s1 and s2, return True if some permutation of s1 appears as a substring of s2.

Permutation = the same characters in any order. For "ab" the permutations are "ab" and "ba". For 1 2 3 they are 123, 132, 213, 231, 312, 321. What matters is that the characters and their counts match exactly; the order doesn't.

2Building it from her example

s1 = "ab", s2 = "eidbaooo". Answer: True, because "ba" sits inside s2.

1. Length check first: a permutation of s1 has exactly len(s1) characters. If s1 is longer than s2 (s1 = "abc", s2 = "ab"), it can't fit → return False right away.
2. So the window is fixed at len(s1) = 2. This pattern is a fixed window with a map instead of a sum.
3. Why a map and not a direct comparison? Comparing "ab" to "ba" character by character says "different", but "ba" is a permutation. So compare counts: s1 has {a:1, b:1}; the window "ba" also has {a:1, b:1} → equal.
4. Start with the first 2 chars of s2, "ei": map {e:1, i:1}. Not equal.
5. Slide: add the new char d → {e:1, i:1, d:1}; remove the char that left, e: decrement it, and since it's now 0, delete the key → {i:1, d:1}. That's the window "id". Not equal.
6. Keep sliding. Only s2's map changes. s1's map stays the same the whole time.

3Template (Python)

class Solution:
    def checkInclusion(self, s1, s2):
        k = len(s1)
        if k > len(s2):
            return False                         # can't fit
        need = {}
        for ch in s1:
            need[ch] = need.get(ch, 0) + 1       # s1's map never changes
        window = {}
        for right in range(len(s2)):
            ch = s2[right]
            window[ch] = window.get(ch, 0) + 1   # add the new char
            if right >= k:                       # window too long: remove the oldest
                old = s2[right - k]
                window[old] -= 1
                if window[old] == 0:
                    del window[old]              # drop zero counts
            if window == need:                   # same chars, same counts
                return True
        return False

4Dry run (hand table)

s1 = "ab" → need = {a:1, b:1}. s2 = "eidbaooo", k = 2.

Time O(n · 26) = O(n). Space O(26) = O(1) for lowercase letters.

Part D · Pattern 4: longest window with at most k changes

her example: Longest Repeating Character Replacement (LeetCode 424)

1The idea in simple words

The fourth type: find the maximum length, but the window is allowed to contain a few "bad" cells, because the question lets you fix up to k of them (flip, replace, change).

Her example: s = "AABABBA", k = 1. One operation = pick any character and change it to any uppercase letter. Return the length of the longest substring with all the same letter you can get after at most k operations. Change one B to A and you get "AAAA" (length 4) → answer 4.

2Building it from her examples

Her mini example: "ABC", k = 1

1. A: nothing to change.
2. B: different from A. We have 1 change, so turn B into A. Changes left: 0.
3. C: different again, but no changes left. Stop. Longest so far = 2 ("AB" → "AA").

Which letters do we change? (the greedy idea)

In a window, keep the letter that appears the most, and change all the others. Changing the rarer letters costs the fewest operations. So for a window:

changes needed = window length − (count of the most frequent letter)

Her check on "AAB" (index 0..2): length 3, max frequency 2 (A) → 3 − 2 = 1 change, which is exactly the number of B's. 1 ≤ k = 1, so the window is valid, and its length 3 is a candidate.

To know the max frequency, keep a map of counts for the window and a variable max_freq.

The teacher says this video only shows the pattern, not the full code. The template below is my full version of her idea.

3Template (Python)

class Solution:
    def characterReplacement(self, s, k):
        count = {}
        left = 0
        max_freq = 0
        best = 0
        for right in range(len(s)):
            ch = s[right]
            count[ch] = count.get(ch, 0) + 1
            max_freq = max(max_freq, count[ch])      # most common letter seen in a window
            if (right - left + 1) - max_freq > k:    # needs more than k changes
                count[s[left]] -= 1                  # slide: oldest letter leaves
                left += 1
            best = max(best, right - left + 1)
        return best

4Dry run (hand table)

s = "AABABBA", k = 1.

Answer 4 ✓. Time O(n), space O(26).

Part E · Extra shapes used later in the sheet

The concept video stops at the four patterns above. The later problems in this sheet use three more shapes. They are summarised here (my additions, so this page works as a full reference); each one is taught properly on its own problem page.

1Counting windows: count += right − left + 1

When the question asks how many subarrays satisfy a condition that is "at most" style (sum ≤ k, product < k, at most K distinct), use the longest-window loop, and after shrinking add right − left + 1.

Why: once [left..right] is valid, every window that ends at right and starts anywhere from left to right is also valid (it's a smaller piece of a valid window). There are exactly right − left + 1 such starts. Example: valid [2..4] ends at 4 → [2..4], [3..4], [4..4] = 3 windows.

class Solution:
    def countSumAtMost(self, nums, k):
        left = 0
        total = 0
        count = 0
        for right in range(len(nums)):
            total += nums[right]
            while total > k and left <= right:   # shrink until valid (or empty)
                total -= nums[left]
                left += 1
            count += right - left + 1            # all valid windows ending at right
        return count

2Exactly K = atMost(K) − atMost(K − 1)

"Exactly K" is not monotonic: a window with too few distinct values may need to grow, and one with too many must shrink, so a single window can't decide. But "at most K" is monotonic. And:

#(exactly K) = #(at most K) − #(at most K − 1)

Because the windows with at most K distinct are exactly those with ≤ K − 1 distinct plus those with exactly K.

class Solution:
    def subarraysWithKDistinct(self, nums, k):
        return self.at_most(nums, k) - self.at_most(nums, k - 1)

    def at_most(self, nums, k):
        if k < 0:
            return 0
        freq = {}
        left = 0
        count = 0
        for right in range(len(nums)):
            x = nums[right]
            freq[x] = freq.get(x, 0) + 1
            while len(freq) > k:                 # too many distinct values
                y = nums[left]
                freq[y] -= 1
                if freq[y] == 0:
                    del freq[y]
                left += 1
            count += right - left + 1
        return count

3Fixed window + monotonic deque (maximum of every window)

For "the max of each window of size k" a sum isn't enough: when the max leaves, what's the next max? Keep a deque (double-ended queue, collections.deque) of indexes whose values are decreasing from front to back. The front is always the max of the current window.

• Before adding index r, pop from the back every index whose value ≤ nums[r]. They can never be a max again, because nums[r] is bigger and stays in the window longer.
• If the front index has slid out of the window (≤ r − k), pop it from the front.

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums, k):
        dq = deque()                     # indexes, values decreasing front -> back
        out = []
        for right in range(len(nums)):
            while dq and nums[dq[-1]] <= nums[right]:
                dq.pop()                 # smaller values can never be a max again
            dq.append(right)
            if dq[0] <= right - k:
                dq.popleft()             # front fell out of the window
            if right >= k - 1:
                out.append(nums[dq[0]])  # front = max of [right-k+1 .. right]
        return out

Part F · Revision page

print(Solution().findMaxAverage([1, 12, -5, -6, 50, 3], 4))   # 12.75
print(Solution().minSubArrayLen(7, [2, 3, 1, 2, 4, 3]))        # 2
print(Solution().checkInclusion("ab", "eidbaooo"))             # True
print(Solution().characterReplacement("AABABBA", 1))           # 4
print(Solution().subarraysWithKDistinct([1, 2, 1, 2, 3], 2))   # 7
print(Solution().maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3))  # [3, 3, 5, 5, 6, 7]

(Each template defines its own Solution, so run each line right after the matching template.)

Based on this video: How to identify Sliding Window patterns