Sliding Window

Find the longest unique substring in abca. The last a makes the window invalid: remove the old a before recording the length. Longest and shortest window problems record answers at different moments.

This article always uses a half-open window: everything left of slow has already left, [slow, fast) is the window itself, and fast and everything to its right has not been seen yet. The window length is just fast - slow, with no +1.

Every version keeps three rules:

1. The window state always matches [slow, fast). The state can be a sum, a set, a count map, or a deque. When an element enters, add it to the state; when it leaves, undo it. If one step gets out of sync, every check after it is wrong.
2. slow moves only when the window is invalid (or a fixed-size window is too long), and it only moves right. This needs monotonicity: making the window longer only makes the condition harder to satisfy, and making it shorter only makes it easier. Without that (for example, sums over an array with negative numbers), you cannot slide.
3. The answer only comes from valid windows. Which line updates the answer depends on whether the window is valid on that line.

The article goes in this order, and each step adds exactly one idea:

When to Use This Pattern

The brute force enumerates every subarray: n starts, n ends, plus the cost of checking each one, so O(n²) at best. Take LC 209 (positive integers, shortest subarray with sum ≥ target), nums = [2, 3, 1, 2, 4, 3], target = 7. The brute force adds from start 0 until the sum reaches 7, then starts over from index 1 and adds the same numbers again.

A sliding window never goes back. The window [0, 4) starting at 0 has sum 8 and is already valid; to move the start to 1, you don't re-add from 1, you subtract nums[0] and get the sum of [1, 4). Why is it safe not to go back? Because every number is positive:

When the start moves right, the shortest valid end never moves left. That is the monotonicity in rule 2. Both pointers only move right, 2n steps in total.

Recognition Checklist

• It asks about a contiguous subarray or substring, not a subsequence
• It wants the longest, the shortest, a count, or "every window of length k"
• The condition changes monotonically as the window grows (sum of non-negatives, number of distinct chars, number of zeros)
• The window state can be updated in O(1) when one element enters or leaves (sum, count map, deque)
• Enumerating every subarray is O(n²) and you need O(n)

Before You Code

Before writing code, answer these every time (four questions in total; the fourth complements the first):

1. What does the window [slow, fast) hold, and what state describes it? For example, "the count of each character in s[slow:fast], stored in cnt". The state decides how question 4 undoes things and how question 2 checks validity.
2. Fixed or variable size? When is the window invalid, so that slow has to move? A fixed window lets one element out once its length exceeds k; a variable window keeps letting elements out with while until it is valid again.
3. Which line updates the answer? Longest: after shrinking, when the window is valid again. Shortest: while the window is valid, record first, then let one out to see if a shorter one still works.
4. Whatever entering did, leaving does in reverse. += pairs with -=, increment with decrement, add with remove.

The four answers connect: question 1 fixes the state, question 2 uses the state to write the "invalid" condition, question 3 uses that condition to decide whether the answer goes inside or after the while, and question 4 keeps the state correct after slow moves.

Try it on LC 3 Longest Substring Without Repeating Characters, s = "abcbd":

• What the window holds: the slice s[slow:fast]; the state is a count map cnt of each character.
• Fixed or variable: variable. Once the character c that just entered appears twice (cnt[c] > 1) the window is invalid, so keep letting characters out until only one c is left.
• Where the answer is updated: it's a longest question, so after shrinking the window is valid and fast - slow updates the answer.
• How to undo: entering does cnt[c] += 1, leaving does cnt[s[slow]] -= 1.

Step 2 turns it into code and walks "abba" and "abcbd" by hand.

Longest Substring Without Repeating Characters (LeetCode 3)

Given a string, return the length of its longest contiguous substring without repeating characters, not the substring itself or a subsequence that skips characters. Empty input returns zero; a window cannot contain two copies of one character.

Input: s = "abcbd". Expected: 3.

The window is the half-open slice s[slow:fast] ([slow, fast)). It must contain no repeated character, and its length is simply fast - slow. cnt counts each character in the window.

1. Walk it by hand

2. Read the rule off the table

• Every row moves fast forward unconditionally: count s[fast] in cnt, then fast += 1.
• If the character that just came in now appears more than once, keep decrementing s[slow]'s count and doing slow += 1 until only one copy is left. Only the newcomer can be repeated, so that is the one to watch.
• After shrinking the window has no repeats, so compare fast - slow with best (longest: update after shrinking).

3. Turn each row into code

def length_of_longest_substring(s):
    cnt = {}
    slow = fast = best = 0
    while fast < len(s):
        c = s[fast]
        cnt[c] = cnt.get(c, 0) + 1
        fast += 1
        while cnt[c] > 1:
            cnt[s[slow]] -= 1
            slow += 1
        best = max(best, fast - slow)
    return best

Core Templates

All five steps use the same approach: answer the four questions first, then check every line against the three rules at the top: does the state match the window, does slow move only when it should, and does the answer come from a valid window.

All the code shares one skeleton:

slow = fast = 0
while fast < n:
    add a[fast] to the state; fast += 1      # one in
    while/if something must leave:           # out (if for fixed size, while for variable)
        undo a[slow] from the state; slow += 1
    update the answer when the window is valid   # where depends on longest vs shortest

Step 1: Fixed-size window, one in and one out

Problem: the maximum sum of a subarray of length exactly k.

The input is an integer array nums and an integer k (1 ≤ k ≤ len(nums)). Return the largest sum among all contiguous subarrays of length exactly k. The array may contain negative numbers.

For example, [2, 1, 5, 1, 3, 2] with k = 3 → 9: there are 4 windows of length 3, with sums 8, 7, 9, 6, and the largest is [5, 1, 3].

This is a teaching problem, not a specific LeetCode problem. When k is not between 1 and len(nums), the code below returns None; that is this function's own convention.

The four questions:

• What the window holds: nums[slow:fast], with its sum window as the state.
• When to let one out: when the length fast - slow exceeds k. Only one element enters per round, so it can exceed by at most one, and if is enough.
• Where the answer is updated: only a window of length exactly k is valid, so update then. During the first k − 1 rounds the window is not full yet and must not be recorded.
• How to undo: enter with window += nums[fast], leave with window -= nums[slow].

The brute force slices sum(nums[i:i+k]) for every start, O(nk). One in, one out only touches the two ends, O(1) per step.

def max_sum_k(nums, k):
    if k <= 0 or k > len(nums):
        return None
    slow = fast = 0                 # chained assignment: both start at 0
    window = 0                      # sum of nums[slow:fast]
    best = None
    while fast < len(nums):
        window += nums[fast]        # one in
        fast += 1
        if fast - slow > k:         # more than k: one out
            window -= nums[slow]
            slow += 1
        if fast - slow == k:        # exactly k is a valid window
            # conditional expression a if cond else b: take window the first time, the larger one after that
            best = window if best is None else max(best, window)
    return best


assert max_sum_k([2, 1, 5, 1, 3, 2], 3) == 9
assert max_sum_k([-1, -2, -3], 2) == -3
assert max_sum_k([4], 1) == 4
assert max_sum_k([1, 2], 3) is None

nums = [2, 1, 5, 1, 3, 2], k = 3:

best starts as None, not 0: if every number is negative the maximum sum is negative, and starting from 0 would return a wrong 0.

O(n) time: fast takes n steps and slow at most n − k. O(1) space.

Variation: duplicates at most k apart (LC 219)

The input is an integer array nums and a non-negative integer k. Return a boolean: are there two different indices i and j with nums[i] == nums[j] and |i - j| <= k?

For example, in [1, 2, 1] the two 1s are at indices 0 and 2, two apart. k = 2 → True; k = 1 → False, because the array has a repeat but it is too far apart. With k = 0 the answer is always False, since different indices differ by at least 1.

Think first: For a newcomer nums[j], which earlier numbers does "indices at most k apart" ask you to compare it with? How many numbers should the window hold, and what state describes them? Should the newcomer be checked before it enters the window, or after? What goes wrong the other way round?

def contains_nearby_duplicate(nums, k):
    window = set()                  # values in nums[slow:fast], at most k of them
    slow = fast = 0
    while fast < len(nums):
        x = nums[fast]
        if x in window:             # check first: equals one of the previous k
            return True
        window.add(x)               # then add
        fast += 1
        if fast - slow > k:         # more than k: the oldest leaves
            window.remove(nums[slow])
            slow += 1
    return False


assert contains_nearby_duplicate([1, 2, 1], 2) is True     # the example from the statement
assert contains_nearby_duplicate([1, 2, 1], 1) is False
assert contains_nearby_duplicate([1, 2, 3, 1], 3) is True
assert contains_nearby_duplicate([1, 2, 3, 1, 2, 3], 2) is False
assert contains_nearby_duplicate([1, 0, 1, 1], 1) is True
assert contains_nearby_duplicate([1, 1], 0) is False

Variation: the k closest elements to x (LC 658)

The input is an array arr sorted in ascending order (it may have duplicates), an integer k (1 ≤ k ≤ len(arr)), and a target x. Return the k elements of arr closest to x, sorted in ascending order.

"Closer to x" compares |a - x|. When two numbers are equally close, the smaller one counts as closer. With duplicates, each position counts separately and both can be chosen.

For example, [1, 2, 3, 4, 5] with k = 4, x = 3 → [1, 2, 3, 4]: the distances to 3 are 2, 1, 0, 1, 2; 1 and 5 tie, and the smaller 1 is kept.

Return the values, not their indices, in ascending order, not ordered by distance.

Think first: Why must the k closest elements of a sorted array be one contiguous block? With a window of fixed length k, sliding right by one means swapping the leftmost arr[slow] for the newcomer arr[fast]. When is that swap worth it? On a tie, do you swap?

def find_closest_elements(arr, k, x):
    slow, fast = 0, k               # window arr[slow:fast], start with the first k; fast is the next candidate
    # slide right only while x is right of the midpoint of arr[slow] and arr[fast]; ties keep the left
    while fast < len(arr) and x - arr[slow] > arr[fast] - x:
        slow += 1                   # leftmost out
        fast += 1                   # newcomer in
    return arr[slow:fast]


assert find_closest_elements([1, 2, 3, 4, 5], 4, 3) == [1, 2, 3, 4]   # the example from the statement
assert find_closest_elements([1, 2, 3, 4, 5, 6, 7], 3, 5) == [4, 5, 6]
assert find_closest_elements([1, 1, 2, 3, 4, 5], 4, -1) == [1, 1, 2, 3]
assert find_closest_elements([1, 1, 1, 10, 10, 10], 1, 9) == [10]
assert find_closest_elements([1, 3], 1, 2) == [1]

Step 1 recap

• What it solves: look at every window of length exactly k, for example to find the maximum sum or to see whether a window holds a repeat.
• The key line: if fast - slow > k: let one out. Only one enters per round, so it can exceed by at most one, and if is enough.
• What the variations change: the maximum sum keeps a sum; LC 219 switches the state to a set and checks before adding; LC 658 stops looking at every window and compares the two ends instead, sliding only while the newcomer is closer.
• The easiest mistake: recording before the window is full, or starting the answer at 0. Record only when fast - slow == k, and start from None.

In a fixed window, when slow moves is fixed (whenever the length is exceeded), with no validity check. In the next step the length is not fixed, and whether slow moves depends on what is inside the window.

Step 2: Variable size, longest: shrink while invalid

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

The input is a string s. Return the length of its longest contiguous substring with no repeated characters. An empty string returns 0. Characters are not limited to letters; digits and spaces count too.

For example, "pwwkew" → 3, for "wke". "pwke" does not count: its characters are not adjacent in s, so it is a subsequence, not a substring.

"Before You Code" already answered the four questions for this problem on "abcbd". What this step adds is that the window can become invalid. fast still brings one in every round; if the window is invalid afterwards, keep letting elements out with while until it is valid again. After shrinking the window is always valid, so the answer is updated outside the while, after shrinking (rule 3).

Why watch only the character c that just entered? Before c came in, the window was valid (last round finished shrinking) and had no repeats. After one c comes in, only c can be repeated.

cnt.get(c, 0) is the dictionary lookup with a default: if c is a key it returns its value, otherwise it returns 0 instead of raising KeyError the way cnt[c] would. So cnt[c] = cnt.get(c, 0) + 1 means "add one to c's count, starting from 0 the first time".

def length_of_longest_substring(s):
    cnt = {}                        # count of each char in s[slow:fast]
    slow = fast = best = 0
    while fast < len(s):
        c = s[fast]                 # in: fast always moves forward
        cnt[c] = cnt.get(c, 0) + 1
        fast += 1
        while cnt[c] > 1:           # only the newcomer c can be repeated
            cnt[s[slow]] -= 1       # out: undo s[slow]
            slow += 1
        best = max(best, fast - slow)   # valid after shrinking, record the longest
    return best


assert length_of_longest_substring("abcbd") == 3
assert length_of_longest_substring("abba") == 2
assert length_of_longest_substring("pwwkew") == 3
assert length_of_longest_substring("") == 0
assert length_of_longest_substring("aaaa") == 1

s = "abba":

The third row needs two elements out before the window is valid, so shrinking must use while. With if, at most one leaves per round and the window can carry a repeat forward. On the earlier example "abcbd":

The if version records the invalid "bcbd" as the answer.

Even with the inner while, time is O(n): slow only moves right, at most n steps over the whole run, so all the inner loops together run at most n times. Space is the size of the alphabet.

Another way: remember the last position (LC 3)

Instead of a count map, keep last[c], the index where c last appeared. When c repeats, don't let characters out one at a time; jump slow straight to last[c] + 1, which removes the old c and everything left of it at once.

Think first: In "abba", when you reach the last a, what is last['a']? What is slow at that moment? If you write slow = last[c] + 1 directly, what does the window become?

Same idea: flip at most k zeros to ones (LC 1004)

The input is an array nums of 0s and 1s and a non-negative integer k. You may change at most k zeros into ones. Return the length of the longest run of consecutive 1s after the changes. Return only the length, not which zeros were changed.

For example, [1, 0, 1, 0, 1] with k = 1 → 3: change the 0 at index 1 to get 1 1 1 0 1, whose longest run is the first three. Only one of the two zeros can be changed, so 5 is out of reach.

You may change fewer than k, or none at all.

Think first: If you change every 0 in a chosen block to 1, the block becomes all 1s. So what kind of subarray of the original array is "a run of 1s after the changes"? What should the window state record, and when is the window invalid?

def longest_ones(nums, k):
    zeros = 0                       # number of 0s in nums[slow:fast]
    slow = fast = best = 0
    while fast < len(nums):
        if nums[fast] == 0:         # in
            zeros += 1
        fast += 1
        while zeros > k:            # too many zeros, invalid
            if nums[slow] == 0:     # out: undo what entering added
                zeros -= 1
            slow += 1
        best = max(best, fast - slow)
    return best


assert longest_ones([1, 0, 1, 0, 1], 1) == 3     # the example from the statement
assert longest_ones([1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], 2) == 6
assert longest_ones([0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1], 3) == 10
assert longest_ones([0, 0], 0) == 0
assert longest_ones([], 1) == 0

Same idea: longest repeating substring after k replacements (LC 424)

The input is a string s of uppercase English letters and a non-negative integer k. One operation changes any one character into any uppercase letter, and you may do at most k operations. Return the length of the longest contiguous substring that is all one letter after the operations.

For example, "AABABBA" with k = 1 → 4: change the A at index 3 to B to get "AABBBBA", whose middle "BBBB" has length 4.

You choose which letter the block ends up as; it is not fixed in advance.

Think first: Given a window, what is the smallest number of characters you must change to make it all one letter? Which letter should you keep? Can a count map like the one in LC 3 give you that number?

def character_replacement(s, k):
    cnt = {}                        # count of each letter in s[slow:fast]
    slow = fast = best = 0
    while fast < len(s):
        cnt[s[fast]] = cnt.get(s[fast], 0) + 1
        fast += 1
        # replacements needed = length - count of the most frequent letter
        while (fast - slow) - max(cnt.values()) > k:
            cnt[s[slow]] -= 1
            slow += 1
        best = max(best, fast - slow)
    return best


assert character_replacement("AABABBA", 1) == 4   # the example from the statement
assert character_replacement("ABAB", 2) == 4
assert character_replacement("ABCD", 0) == 1
assert character_replacement("", 3) == 0

Step 2 recap

• What it solves: the longest contiguous substring / subarray that satisfies a condition. The window can become invalid and has to shrink back to valid.
• The key line: while invalid: keep letting one out, and only after shrinking best = max(best, fast - slow).
• What the variations change: only the state and the "invalid" condition. LC 3 uses a count map with cnt[c] > 1; LC 1004 counts zeros with zeros > k; LC 424 uses length − top count > k; LC 340 uses len(cnt) > k. The last-position version replaces "one out at a time" with a jump, and needs max so slow never moves back.
• The easiest mistake: shrinking with if. Only one leaves at a time and the window may still be invalid; "abcbd" returns 4.

For longest, record after shrinking. The next step asks for the shortest instead, and where the answer is recorded has to change with it.

Step 3: Variable size, shortest: while valid, record first, then shrink

Problem : in an array of positive integers, the length of the shortest subarray with sum ≥ target, or 0 if none ( LC 209 ). (Pro lesson)

Step 3 recap

What it solves : the shortest contiguous subarray that satisfies a condition, where the condition only gets easier to satisfy as the window… (Pro lesson)

Step 4: Compare against a target string with need and missing

Problem : return the start index of every anagram of p in s ( LC 438 ). The input is two strings s and p of lowercase letters. (Pro lesson)

Same idea: does s2 contain a permutation of s1 (LC 567)

The input is two strings s1 and s2 of lowercase letters. (Pro lesson)

Variation: minimum window substring (LC 76)

The input is two strings s and t. Return the shortest contiguous substring of s that contains every character of t at least as many times as… (Pro lesson)

Step 4 recap

What it solves : the window must match a target string's character counts (anagrams, permutations) or cover it (minimum window substring). (Pro lesson)

Step 5: Window maximum: store indices, clear stale ones

Problem : the maximum of every window of length k ( LC 239 ). The input is an integer array nums and an integer k (1 ≤ k ≤ len(nums) ). (Pro lesson)

First try a heap

Put (-value, index) in a max-heap, so the top is the maximum. (Pro lesson)

One step further: a monotonic deque (LC 239)

Look at the 3(1) left in the heap in the last row. It is older than 4(2) (it leaves first) and smaller than 4. (Pro lesson)

Step 5 recap

What it solves : the maximum (or minimum) of every fixed-size window, where the state cannot be undone by subtraction. (Pro lesson)

All five steps together

Step State When slow moves if or while Where the answer is updated Step 1 sum / set length exceeds k if when the length equals k Step 2 coun… (Pro lesson)

One Problem, Many Disguises

Disguise (how the problem says it) Translated to the core problem Step LC 346 average of the last size numbers in a stream fixed window with… (Pro lesson)

Common Pitfalls

Mixing [slow, fast] and [slow, fast) . The length is sometimes fast - slow + 1 and sometimes fast - slow , off by one. (Pro lesson)

Say It in the Interview

After confirming whether the input can have negative numbers and how large the alphabet is, you can say: I'll use a sliding window [slow, fa… (Pro lesson)