Sliding Window Technique: Complete Guide with LeetCode Examples

The sliding window technique maintains a contiguous sub-array (or substring) and slides it across the input to answer questions about sub-ranges — in O(n) time rather than the O(n²) or O(n³) a brute-force nested-loop approach requires.

It appears in roughly one-quarter of all LeetCode medium problems and is tested constantly at FAANG interviews. Mastering fixed and variable windows, and knowing when to use each, unlocks a large family of problems you can solve in a single pass.

Quick reference

Why sliding window works

A brute force scans every sub-array [i, j] — O(n²) pairs, each potentially requiring O(n) work inside. A sliding window avoids this by recognising that when you move from window [i, j] to [i+1, j+1] you only add one element on the right and remove one element on the left. All the bookkeeping can be done incrementally — O(1) per step, O(n) total.

Key insight: the window's left and right boundaries only move forward. Each element is added at most once and removed at most once, giving O(n) amortised complexity.

Pattern 1 — Fixed window

The window size k is given. Compute the answer for the first window, then slide: subtract the leaving element, add the arriving element.

Template:

def fixed_window(arr, k):
    window_sum = sum(arr[:k])          # seed first window
    result = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i]           # add entering element
        window_sum -= arr[i - k]      # remove leaving element
        result = max(result, window_sum)

    return result

Problem 1 — Maximum average subarray of length k (LeetCode 643)

Find the maximum average of any contiguous sub-array of length k.

Python:

def findMaxAverage(nums: list[int], k: int) -> float:
    window = sum(nums[:k])
    best = window

    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)

    return best / k

JavaScript:

function findMaxAverage(nums, k) {
    let window = nums.slice(0, k).reduce((a, b) => a + b, 0);
    let best = window;

    for (let i = k; i < nums.length; i++) {
        window += nums[i] - nums[i - k];
        best = Math.max(best, window);
    }
    return best / k;
}

Java:

public double findMaxAverage(int[] nums, int k) {
    long window = 0;
    for (int i = 0; i < k; i++) window += nums[i];
    long best = window;

    for (int i = k; i < nums.length; i++) {
        window += nums[i] - nums[i - k];
        best = Math.max(best, window);
    }
    return (double) best / k;
}

Go:

func findMaxAverage(nums []int, k int) float64 {
    window := 0
    for _, v := range nums[:k] { window += v }
    best := window

    for i := k; i < len(nums); i++ {
        window += nums[i] - nums[i-k]
        if window > best { best = window }
    }
    return float64(best) / float64(k)
}

Time: O(n) · Space: O(1)

Problem 2 — Contains duplicate within k distance (LeetCode 219)

Given nums and k, return true if any two equal values exist within k indices of each other.

Python:

def containsNearbyDuplicate(nums: list[int], k: int) -> bool:
    window = set()

    for i, v in enumerate(nums):
        if v in window:
            return True
        window.add(v)
        if len(window) > k:          # slide: remove leftmost
            window.remove(nums[i - k])

    return False

Time: O(n) · Space: O(k)

Pattern 2 — Variable window: shrink when invalid

Expand the right boundary freely. When a constraint is violated, shrink from the left until the window is valid again.

Template:

def variable_window_shrink_invalid(s):
    left = 0
    state = {}          # track what's inside window
    result = 0

    for right in range(len(s)):
        # 1. Add s[right] to state
        state[s[right]] = state.get(s[right], 0) + 1

        # 2. Shrink while invalid
        while not is_valid(state):
            state[s[left]] -= 1
            if state[s[left]] == 0:
                del state[s[left]]
            left += 1

        # 3. Window [left, right] is valid — update answer
        result = max(result, right - left + 1)

    return result

Problem 3 — Longest substring without repeating characters (LeetCode 3)

Find the length of the longest substring without repeating characters.

Python:

def lengthOfLongestSubstring(s: str) -> int:
    left = 0
    seen = {}
    best = 0

    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1      # jump left past the duplicate
        seen[ch] = right
        best = max(best, right - left + 1)

    return best

JavaScript:

function lengthOfLongestSubstring(s) {
    const seen = new Map();
    let left = 0, best = 0;

    for (let right = 0; right < s.length; right++) {
        const ch = s[right];
        if (seen.has(ch) && seen.get(ch) >= left) {
            left = seen.get(ch) + 1;
        }
        seen.set(ch, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Java:

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> seen = new HashMap<>();
    int left = 0, best = 0;

    for (int right = 0; right < s.length(); right++) {
        char ch = s.charAt(right);
        if (seen.containsKey(ch) && seen.get(ch) >= left) {
            left = seen.get(ch) + 1;
        }
        seen.put(ch, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Go:

func lengthOfLongestSubstring(s string) int {
    seen := make(map[byte]int)
    left, best := 0, 0

    for right := 0; right < len(s); right++ {
        ch := s[right]
        if idx, ok := seen[ch]; ok && idx >= left {
            left = idx + 1
        }
        seen[ch] = right
        if right-left+1 > best {
            best = right - left + 1
        }
    }
    return best
}

Time: O(n) · Space: O(min(n, alphabet))

Problem 4 — Longest substring with at most k distinct characters (LeetCode 340)

Python:

def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
    left = 0
    freq = {}
    best = 0

    for right, ch in enumerate(s):
        freq[ch] = freq.get(ch, 0) + 1

        while len(freq) > k:
            lch = s[left]
            freq[lch] -= 1
            if freq[lch] == 0:
                del freq[lch]
            left += 1

        best = max(best, right - left + 1)

    return best

Time: O(n) · Space: O(k)

Problem 5 — Fruit into baskets (LeetCode 904)

Equivalent to longest subarray with at most 2 distinct values.

Python:

def totalFruit(fruits: list[int]) -> int:
    basket = {}
    left = 0
    best = 0

    for right, fruit in enumerate(fruits):
        basket[fruit] = basket.get(fruit, 0) + 1

        while len(basket) > 2:
            lf = fruits[left]
            basket[lf] -= 1
            if basket[lf] == 0:
                del basket[lf]
            left += 1

        best = max(best, right - left + 1)

    return best

Time: O(n) · Space: O(1) (at most 3 keys in basket)

Pattern 3 — Variable window: shrink when condition is met

Expand right until the condition is satisfied, record the answer, then shrink from the left to try for a smaller window. Repeat.

Used when you want the minimum window that satisfies a condition.

Template:

def variable_window_shrink_when_met(s, t):
    need = Counter(t)
    missing = len(t)
    left = 0
    best = ""

    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1

        if missing == 0:             # condition met
            # shrink from left
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            # record answer
            if not best or right - left + 1 < len(best):
                best = s[left:right + 1]
            # break condition to start expanding again
            need[s[left]] += 1
            missing += 1
            left += 1

    return best

Problem 6 — Minimum window substring (LeetCode 76)

Find the smallest window in s that contains all characters of t.

Python:

from collections import Counter

def minWindow(s: str, t: str) -> str:
    need = Counter(t)
    missing = len(t)
    left = 0
    start = end = 0

    for right, ch in enumerate(s, 1):   # 1-indexed right
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1

        if missing == 0:
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if end == 0 or right - left < end - start:
                start, end = left, right
            need[s[left]] += 1
            missing += 1
            left += 1

    return s[start:end]

JavaScript:

function minWindow(s, t) {
    const need = {};
    for (const ch of t) need[ch] = (need[ch] || 0) + 1;
    let missing = t.length;
    let left = 0, start = 0, end = 0;

    for (let right = 0; right < s.length; right++) {
        const ch = s[right];
        if (need[ch] > 0) missing--;
        need[ch] = (need[ch] || 0) - 1;

        if (missing === 0) {
            while (need[s[left]] < 0) {
                need[s[left]]++;
                left++;
            }
            if (end === 0 || right - left + 1 < end - start) {
                start = left;
                end = right + 1;
            }
            need[s[left]]++;
            missing++;
            left++;
        }
    }
    return s.slice(start, end);
}

Time: O(|s| + |t|) · Space: O(|t|)

Problem 7 — Permutation in string (LeetCode 567)

Return true if any permutation of p exists as a substring of s.

Python:

from collections import Counter

def checkInclusion(p: str, s: str) -> bool:
    if len(p) > len(s):
        return False

    need = Counter(p)
    window = Counter(s[:len(p)])

    if window == need:
        return True

    for i in range(len(p), len(s)):
        # add new right character
        window[s[i]] += 1
        # remove old left character
        left_ch = s[i - len(p)]
        window[left_ch] -= 1
        if window[left_ch] == 0:
            del window[left_ch]
        if window == need:
            return True

    return False

Time: O(|s|) — Counter comparison is O(26) = O(1) for lowercase alpha · Space: O(1)

Pattern 4 — Monotonic deque window (sliding window maximum)

When you need the min or max of the current window efficiently, a monotonic deque maintains candidates in sorted order. Elements outside the window are evicted from the front; elements that can never be the answer are evicted from the back.

Problem 8 — Sliding window maximum (LeetCode 239)

Return the maximum of each window of size k.

Python:

from collections import deque

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    dq = deque()   # stores indices; front is index of current max
    result = []

    for i, v in enumerate(nums):
        # remove indices outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # remove smaller values from back — they can never be max
        while dq and nums[dq[-1]] < v:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

JavaScript:

function maxSlidingWindow(nums, k) {
    const dq = [];   // stores indices
    const result = [];

    for (let i = 0; i < nums.length; i++) {
        while (dq.length && dq[0] < i - k + 1) dq.shift();
        while (dq.length && nums[dq[dq.length - 1]] < nums[i]) dq.pop();
        dq.push(i);
        if (i >= k - 1) result.push(nums[dq[0]]);
    }
    return result;
}

Time: O(n) · Space: O(k)

Classic interview problems summary

Note: Problem 10 (subarray sum = k with negatives) cannot use sliding window because shrinking the window doesn't monotonically decrease the sum. Use prefix sums + hash map instead.

Problem 9 — Longest repeating character replacement (LeetCode 424)

You can change at most k characters. Find the longest sub-array where all characters are the same after replacements.

Key insight: window is invalid when (window size) - (count of most frequent char) > k.

Python:

def characterReplacement(s: str, k: int) -> int:
    freq = [0] * 26
    left = 0
    max_freq = 0
    best = 0

    for right, ch in enumerate(s):
        freq[ord(ch) - ord('A')] += 1
        max_freq = max(max_freq, freq[ord(ch) - ord('A')])

        # window invalid: replacements needed > k
        while (right - left + 1) - max_freq > k:
            freq[ord(s[left]) - ord('A')] -= 1
            left += 1

        best = max(best, right - left + 1)

    return best

Time: O(n) · Space: O(1)

Sliding window vs two pointers vs prefix sum

Complexity summary

When to use sliding window

Use sliding window when:

• The problem asks about a contiguous sub-array or substring
• The constraint involves a window size k or a property to maximise / minimise
• You need to track something about elements in a range (sum, max, distinct count)
• Brute force is O(n²) or worse and input size is up to 10⁵–10⁶

Do NOT use sliding window when:

• Elements can be negative AND you need sum-based constraints (use prefix sum + hash map)
• Sub-sequences don't need to be contiguous (use DP or two pointer on sorted)
• You need to consider all pairs, not just adjacent windows (use two pointers or binary search)

How to recognise the pattern

Ask these questions in order:

1. Does the problem ask about a contiguous subarray or substring?
   NO  → sliding window probably wrong
   YES ↓

2. Is the window size fixed (k given)?
   YES → fixed window template
   NO  ↓

3. Are you maximising the window?
   YES → shrink when INVALID (Pattern 2)
   NO  ↓

4. Are you minimising the window?
   YES → shrink when CONDITION MET (Pattern 3)
   NO  ↓

5. Do you need min/max of every window?
   YES → monotonic deque (Pattern 4)

Common mistakes

Sliding window vs related techniques

FAQ

Q: What's the difference between sliding window and two pointers? Sliding window is a subset of two pointers where both pointers only move right (the window slides forward). Two pointers includes patterns where pointers start from opposite ends and move toward each other.

Q: Can sliding window work on 2D arrays? Yes — a common trick is to fix the top and bottom row boundaries and apply 1D sliding window on column sums. This gives O(n² × m) instead of O(n³ × m) for a rectangle max-sum problem.

Q: When does shrinking the window from the left not work? When adding/removing an element doesn't change the objective monotonically. Classic example: subarray sum equals k with negative numbers — shrinking doesn't guarantee the sum decreases, so you can't tell when to stop shrinking.

Q: Is the amortised O(n) claim always true for variable windows? Yes — each element is added to the window once (right pointer passes it) and removed at most once (left pointer passes it). Total pointer moves ≤ 2n regardless of how many shrink steps happen.

Q: How do I handle duplicate characters in a fixed-size window comparison? Track a diff counter (number of characters whose frequency differs between window and target). Update diff when a character's frequency crosses the target threshold. Window matches when diff == 0.

Q: Which sliding window problems appear most in FAANG interviews? LeetCode 3 (longest substring no repeat), 76 (min window substring), 239 (sliding window max), 424 (longest repeating replacement), and 567 (permutation in string) are the five most frequently reported. Solve these first.