DSA Patterns

Sliding Window

The analytics dashboard recomputes every contiguous range sum from scratch on each scroll. Latency spikes. The feed only needs rolling windows: reuse what stayed inside the frame.

A sliding window is a contiguous range with two boundaries and . The real technique is a plus that makes old starts safe to discard.

What happens first?

Confirm contiguity

Subsequences and arbitrary sets are the wrong model.

Name what the active range must satisfy.

Prove discarded starts cannot help later.

After repair, while valid, or add width?

What actually happens

Naive idea: for every left and right, re-scan the range. Correct, and Θ(n²) or Θ(n³) depending on the check. At n = 10⁵ that is past budget.

Better idea: grow right, update state for the entering value, shrink left while invalid, then record. stays O(n) because neither pointer retreats. Fixed-size windows admit one and remove one each step.

The improved design still fails when negatives break sum monotonicity, when the predicate is not “at most”-style, or when you re-scan the window for a max instead of using a deque. Contiguity is necessary; monotonic discard is the missing proof.

Invariant

After repair, the summary state equals the active contiguous range and satisfies the validity rule (for example, at most K distinct counts). Monotonicity is required to forget left prefixes: without it, a discarded start may still be optimal for a later endpoint.

How to choose a sliding window

1. Is the answer a contiguous range? If not, stop. Subsequences need other tools.

2. Fixed length or validity-driven? Fixed k admits and removes in lockstep. Variable windows need a clear repair rule and .

3. Does discard need monotonicity? Non-negative sums, “at most K,” and product limits usually qualify. Arbitrary signs on sum targets need prefix sums or a deque, not basic shrink-until-small.

Quantitative check

n = 10⁵, longest substring with ≤ 2 distinct characters: naive O(n²) checks are ~10¹⁰ character inspections. Two pointers with a map do ≤ 2n admissions/removals: about 2 × 10⁵ map updates. Same asymptotic story for fixed-k rolling sums versus rebuilding each window.

The window has four parts

Boundaries

left and right identify exactly which contiguous elements are active.

Summary state

Store only what can be updated incrementally: sum, counts, max deque, and so on.

Validity rule

An invariant says whether the active range is admissible for the problem.

Answer rule

Decide when the current range is a legitimate candidate and what to record.

This chapter uses inclusive boundaries [left, right], so the width is right - left + 1. Half-open [left, right) is equally valid: just do not mix the two conventions.

Interactive window lab

Compare a fixed-size rolling sum with a variable-size frequency window. Then open the negative-value trace to see why “shrink until the sum is too small” can silently miss the optimum.

Interactive pointer trace

Sliding Window Lab

Step through the update, the invariant check, and the exact moment an answer is safe to record.

Longest substring with at most 2 distinct characters

valid

Grow right once, then move left only while the frequency-map invariant is broken.

Step 1 / 8

L = R · in

index 0

index 1

index 2

index 3

index 4

Current window

"e" · 1 distinct

counts { e: 1 }

Best known

"e" · length 1

Amber rings mark the best range.

Admit e and record the valid window.

Invariant: counts = {e: 1}; distinct = 1 ≤ 2.

valid ⇔ number of positive-frequency characters ≤ 2

Trace progress

Active windowBest rangein = admitted at rightout = removed at left

Fixed-size vs variable-size windows

Shape	Typical question	Movement	Candidate moment
Fixed length k	Maximum length-k sum, moving average	Admit one and remove one	Whenever width = k
Longest valid	Longest substring with ≤ k distinct values	Grow right; shrink while invalid	After validity is restored
Shortest satisfying	Minimum positive-sum range with sum ≥ target	Grow right; shrink while valid	Before each shrink
Counting	Number of ranges satisfying an “at most” rule	Repair, then count valid suffixes	Add right − left + 1

Longest under a limit

Repair with while invalid, then maximize the width. Example: at most K distinct.

Shortest meeting a target

While valid, minimize the width and keep shrinking. Example: sum ≥ target with non-negative values.

Do not swap the timing

Recording an invalid longest window or shrinking a shortest window before recording it creates subtle bugs.

Why the nested loop is still O(n)

Aggregate analysis

The right pointer advances at most n times. The left pointer never moves backward, so it also advances at most n times across the entire run, not n times for each right position. Therefore the total number of admissions and removals is at most 2n. A while nested inside a for loop is O(n) here because pointer motion is one-way.

n right moves + at most n left moves = O(n) updates

Cost of each update still matters

Scalar sum/count: O(1) update.
Hash frequency map: O(1) expected update.
Balanced ordered map: O(log n), giving O(n log n).
Re-scan the window for max: can degrade to O(nk); use a monotonic deque.

A compact correctness argument

State is exact: adding right and removing left keep the summary equal to the active range.
Discarding is safe: the constraint has the required monotonicity, so a removed start cannot produce a better candidate for this or a later endpoint.
Every useful endpoint is considered: after repair, record the best candidate ending at each right.

Step 2 is the proof people most often skip. “The range is contiguous” is necessary, but not sufficient, for an ordinary sliding window.

Template 1: fixed-size aggregate

Build the first complete window once. Every later candidate differs by exactly one outgoing and one incoming element. Define behavior for k ≤ 0 and k > n instead of letting a slice hide the error.

Python

python

def max_sum_fixed(nums, k):
    """Return (best_sum, start_index), or None if no length-k window exists."""
    n = len(nums)
    if k <= 0 or k > n:
        return None

    window_sum = sum(nums[:k])
    best_sum = window_sum
    best_start = 0

    for right in range(k, n):
        window_sum += nums[right]       # value entering
        window_sum -= nums[right - k]   # value leaving
        start = right - k + 1

        if window_sum > best_sum:
            best_sum = window_sum
            best_start = start

    return best_sum, best_start

# [2, 1, 5, 1, 3, 2], k=3 -> (9, 2), window [5, 1, 3]

Java

java

final class FixedWindow {
    // Returns {bestSum, startIndex}, or null if no length-k window exists.
    static long[] maxSumFixed(int[] nums, int k) {
        int n = nums.length;
        if (k <= 0 || k > n) return null;

        long windowSum = 0;
        for (int i = 0; i < k; i++) windowSum += nums[i];
        long bestSum = windowSum;
        int bestStart = 0;

        for (int right = k; right < n; right++) {
            windowSum += nums[right];       // value entering
            windowSum -= nums[right - k];   // value leaving
            int start = right - k + 1;

            if (windowSum > bestSum) {
                bestSum = windowSum;
                bestStart = start;
            }
        }

        return new long[] {bestSum, bestStart};
    }

    // [2, 1, 5, 1, 3, 2], k=3 -> {9, 2}, window [5, 1, 3]
}

Time: O(n). Extra space: O(1). This works with negative values because the size, not a sum inequality: controls the boundary motion.

Template 2: longest window under a constraint

For “at most K distinct,” extending can add a distinct character but cannot remove one. Once there are too many, moving left is the only repair. Delete zero counts so len(counts) continues to mean “distinct values currently in the window.”

Python

python

def longest_at_most_k_distinct(s, k):
    if k <= 0 or not s:
        return 0

    counts = {}
    left = 0
    best = 0

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

        # 2) Repair until the invariant is true again
        while len(counts) > k:
            outgoing = s[left]
            counts[outgoing] -= 1
            if counts[outgoing] == 0:
                del counts[outgoing]
            left += 1

        # 3) Record only after repair
        best = max(best, right - left + 1)

    return best

# "eceba", k=2 -> 3 ("ece")

Java

java

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

final class LongestDistinctWindow {
    static int longestAtMostKDistinct(String s, int k) {
        if (k <= 0 || s.isEmpty()) return 0;

        // Code points preserve the same character-level contract for Unicode text.
        int[] values = s.codePoints().toArray();
        Map<Integer, Integer> counts = new HashMap<>();
        int left = 0;
        int best = 0;

        for (int right = 0; right < values.length; right++) {
            counts.merge(values[right], 1, Integer::sum);

            while (counts.size() > k) {
                int outgoing = values[left];
                int remaining = counts.get(outgoing) - 1;
                if (remaining == 0) counts.remove(outgoing);
                else counts.put(outgoing, remaining);
                left++;
            }

            best = Math.max(best, right - left + 1);
        }

        return best;
    }

    // "eceba", k=2 -> 3 ("ece")
}

Time: O(n) expected. Space: O(min(n, |Σ|)), where Σ is the value domain or alphabet. Use an array instead of a map when the alphabet is small and fixed.

Template 3: shortest window that reaches a target

With a positive target and non-negative values, expanding never decreases the sum and shrinking never increases it. Once the target is reached, record the current width and keep shrinking to find the shortest valid suffix ending at this right index.

Python

python

def min_length_at_least(nums, target):
    """Precondition: target > 0 and every value in nums is non-negative."""
    left = 0
    total = 0
    best = float("inf")

    for right, value in enumerate(nums):
        total += value

        # Record BEFORE removing the outgoing value.
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1

    return 0 if best == float("inf") else best

# [2, 3, 1, 2, 4, 3], target=7 -> 2 ([4, 3])

Java

java

final class MinimumTargetWindow {
    // Precondition: target > 0 and every value in nums is non-negative.
    static int minLengthAtLeast(int[] nums, long target) {
        int left = 0;
        long total = 0;
        int best = Integer.MAX_VALUE;

        for (int right = 0; right < nums.length; right++) {
            total += nums[right];

            // Record BEFORE removing the outgoing value.
            while (total >= target) {
                best = Math.min(best, right - left + 1);
                total -= nums[left];
                left++;
            }
        }

        return best == Integer.MAX_VALUE ? 0 : best;
    }

    // [2, 3, 1, 2, 4, 3], target=7 -> 2 ([4, 3])
}

The negative-number trap

Counterexample: [1, −1, 5], target = 5

The full range sums to 5, so the positive-only template records length 3.
It removes 1; the sum becomes 4, so its while total >= target loop stops.
But removing −1 next would increase the sum to 5, revealing the optimal range [5] of length 1.

Negative values destroy the ordered relationship between pointer movement and sum. No local decision can tell the basic window which prefix is safe to forget.

Sum exactly K

Use prefix sums plus a hash map of prior prefix frequencies or earliest indices.

Shortest sum ≥ K

For arbitrary signs, use prefix sums plus a monotonic deque.

Range sum queries

Use prefix sums, Fenwick trees, or segment trees depending on whether updates occur.

Arbitrary signs: prefix sums + monotonic deque

Let prefix[j] - prefix[i] be the sum of nums[i:j]. Candidate prefix indices are kept in increasing prefix-sum order. A newer prefix with a smaller sum dominates an older, larger one because it starts later and makes future differences larger.

Python

python

from collections import deque

def shortest_subarray_at_least_k(nums, k):
    prefix = [0]
    for value in nums:
        prefix.append(prefix[-1] + value)

    candidates = deque()  # indices; prefix values increase from front to back
    best = len(nums) + 1

    for right, current_prefix in enumerate(prefix):
        # The front now makes a valid range; pop it to seek a shorter one.
        while candidates and current_prefix - prefix[candidates[0]] >= k:
            best = min(best, right - candidates.popleft())

        # A later prefix with a smaller/equal value dominates the back.
        while candidates and prefix[candidates[-1]] >= current_prefix:
            candidates.pop()

        candidates.append(right)

    return -1 if best == len(nums) + 1 else best

# [1, -1, 5], k=5 -> 1

Java

java

import java.util.ArrayDeque;
import java.util.Deque;

final class ShortestSignedWindow {
    static int shortestSubarrayAtLeastK(int[] nums, long k) {
        long[] prefix = new long[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        Deque<Integer> candidates = new ArrayDeque<>();
        int best = nums.length + 1;

        for (int right = 0; right < prefix.length; right++) {
            while (!candidates.isEmpty()
                    && prefix[right] - prefix[candidates.peekFirst()] >= k) {
                best = Math.min(best, right - candidates.removeFirst());
            }

            while (!candidates.isEmpty()
                    && prefix[candidates.peekLast()] >= prefix[right]) {
                candidates.removeLast();
            }

            candidates.addLast(right);
        }

        return best == nums.length + 1 ? -1 : best;
    }

    // [1, -1, 5], k=5 -> 1
}

Each prefix index enters and leaves the deque at most once, so this stronger technique is also O(n).

Common variants and their state

Problem family	Incremental state	Invariant / answer rule	Important condition
No repeated character	Last index or frequency map	Every count ≤ 1; maximize width	Jump left with `max(left, last[ch] + 1)`
Minimum covering substring	Needed counts + number of satisfied kinds	While fully covered, record and shrink	Multiplicity matters: “AABC” needs two As
Character replacement	Frequencies + maximum frequency	width − max_frequency ≤ replacements	A stale max is safe only with the standard longest-window proof
Maximum/minimum in each k-window	Monotonic deque of indices	Front is the current extreme	Evict expired indices before reading the front
Product less than K	Running product	Repair, then add width to the count	Requires positive values; handle K ≤ 1 explicitly
Exactly K distinct	Two “at most” counts	`atMost(K) − atMost(K − 1)`	The subtraction identity is for counting, not longest length

Counting windows: why width is the contribution

Suppose repair leaves [left, right] valid and validity is preserved when more elements are removed from the left. Then every suffix ending at right is also valid:

[left..right], [left+1..right], …, [right..right] → right − left + 1 windows

This turns an O(n²) enumeration into O(n). It works for suitable “at most” constraints, such as at most K distinct values. It does not automatically apply to an arbitrary predicate; prove that every suffix remains valid first.

Edge cases and failure modes

Input contract

Empty input: decide whether the answer is 0, an empty range, or “not found.”
Invalid k: define k = 0, k < 0, and k > n explicitly.
Numeric domain: state whether negatives, zeros, floats, or overflow are possible.
Character domain: bytes, Unicode code points, and grapheme clusters are not identical.
Streaming: keep outgoing values in a queue if the original input cannot be indexed.

Implementation bugs

if instead of while: one removal may not restore the invariant.
Wrong record point: update a longest answer after repair; update a shortest answer while valid.
Ghost map keys: decrementing to zero without deletion corrupts a distinct count.
Expired deque indices: values alone cannot tell whether the maximum has left the window.
Off by one: write the boundary convention and width formula before coding.

How to choose the next move

1
Confirm contiguity. If candidates are subsequences or arbitrary sets, a window is the wrong model.
2
Choose the boundaries. Is length fixed, or does validity decide when left moves?
3
Name the invariant. Write one sentence such as “the map contains at most K positive counts.”
4
Choose incremental state. Make add-right and remove-left O(1) or amortized O(1).
5
Prove monotonicity or dominance. Explain why every discarded start can never become useful later.
6
Choose the record point. After repair for longest, while valid for shortest, or add width for counting.
7
Test adversarial cases. Use empty input, all equal, all distinct, k at its limits, and negative values when allowed.

Exercises

For longest substring with at most 2 distinct characters on "eceba", write the window invariant after each right advance. When does left move, and why is that start forever discarded?
Trace [1, −1, 5] with target 5 using the non-negative shortest-sum template. Where does monotonicity fail, and which stronger tool recovers length 1?
n = 2 × 10⁵, fixed window k = 500. Compare total additions for rebuilding each window vs rolling update. When would a Fenwick/segment tree still be preferable?

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): amortized analysis of multi-pointer scans.
Classic statements: longest substring without repeating characters; minimum window substring; shortest subarray with sum ≥ k.
LeetCode discussions / editorial notes on monotonic deques for sliding-window maximum (queue as window state).

Takeaway

A sliding window reuses contiguous work under a named invariant. Monotonicity licenses forgetting old starts; aggregate one-way pointer motion keeps the nested loop O(n). When signs or predicates break that proof, graduate to prefix sums or a deque.