Free lesson · DSA Mastery - Interview Prep, End to End

Introduction to Sliding Window

Medium6 min readdsasliding-window

Introduction to Sliding Window

Sliding window is one of the highest-leverage techniques in interview prep. It turns a large class of "find the best/longest/shortest contiguous subarray or substring" problems from O(n²) brute force into O(n) single-pass solutions. If prefix sum (Module 11) is about precomputing so range queries are cheap, sliding window is about maintaining a running view of a contiguous range as it slides across the data - adding one element on the right, removing elements on the left, and never re-examining what's already settled.

This introduction lays out the mental model, the two major variants (fixed-size and dynamic-size), the bookkeeping that makes windows work, and exactly when to reach for the technique versus prefix sum, two pointers, or a hash map.

What a Window Actually Is

A "window" is a contiguous range [left, right] over an array or string. As right advances, the element entering on the right is included in the window's running state (a sum, a character-frequency map, a count of distinct values, whatever the problem tracks). When the window needs to shrink, left advances and the departing element is excluded from that same state.

The defining property: each element is added to the window at most once and removed at most once. Both pointers only ever move forward. That's why a sliding window is O(n) even though it has a nested-looking structure - the inner left loop, across the entire run, advances a total of at most n times, not n times per outer step.

graph LR
    subgraph "Window slides right"
    A["left"] -.-> B["[ a b c ]"]
    B -.-> C["right"]
    end
    D["Enter on right:<br/>add to state"] --> E["Exit on left:<br/>remove from state"]

    style A fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This diagram shows a window as a contiguous range bounded by a left and a right pointer. As the window slides right, the entering element is added to the window's running state, and when the window shrinks from the left, the departing element is removed from that state. Each element enters and leaves at most once.

The Two Variants

Almost every sliding-window problem is one of two shapes. Recognizing which you're facing tells you the loop skeleton immediately.

Fixed-Size Windows

The window has a constant width k given by the problem: "maximum sum of any subarray of length k," "find all anagrams of length m." You advance right, and once the window reaches width k, every further step adds one element on the right and drops one on the left in lockstep. The window size never changes.

The key efficiency: don't recompute the window's state from scratch each step. Maintain it incrementally - add the entering element, subtract the leaving one. That single insight is what separates the O(n) solution from the O(n·k) brute force.

Dynamic-Size Windows

The window grows and shrinks based on a condition, not a fixed width: "longest substring without repeating characters," "smallest subarray with sum ≥ target," "longest substring with at most k distinct characters." You expand right to include more, and whenever the window violates its condition, you contract left until it's valid again.

Two dynamic shapes recur:

• Longest-valid: expand greedily; when invalid, shrink just enough to restore validity; track the maximum window size seen while valid.
• Shortest-valid: expand until valid; then shrink as far as possible while staying valid, tracking the minimum size.

graph TD
    A["Sliding Window"] --> B["Fixed Size k"]
    A --> C["Dynamic Size"]
    B --> D["Add right, drop left<br/>in lockstep"]
    C --> E["Longest valid:<br/>expand, shrink to restore"]
    C --> F["Shortest valid:<br/>expand to satisfy,<br/>shrink while still valid"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9

This diagram divides sliding window into two variants. Fixed-size windows add one element on the right and drop one on the left in lockstep, keeping a constant width. Dynamic-size windows either expand and shrink to find the longest valid window, or expand to satisfy a condition then shrink while staying valid to find the shortest.

The Dynamic-Window Skeleton

Nearly every dynamic problem fits one template. Expand the window by moving right; after each expansion, restore validity by moving left; update the answer at the right moment.

int left = 0;
// windowState: a sum, freq map, distinct count, etc.
for (int right = 0; right < n; right++) {
    // 1. include nums[right] in windowState
    while (/* window is invalid */) {
        // 2. exclude nums[left] from windowState
        left++;
    }
    // 3. window [left, right] is now valid -> update answer
}

The three slots - include, restore, update - are where each problem's specific logic lives. The skeleton never changes; what you track in windowState and what "invalid" means is what varies. For shortest-valid problems, the while shrinks while valid and the answer update happens inside the loop instead.

What the Window Tracks (Bookkeeping)

The window's "state" is whatever lets you check the condition in O(1) per step. Common choices:

• A running sum - for sum-based conditions (Minimum Size Subarray Sum, Maximum Average Subarray).
• A frequency hash map - for character/element counts (Longest Substring Without Repeating Characters, anagram problems, at-most-k-distinct).
• A distinct-count integer - derived from the frequency map, incremented when a count goes 0→1 and decremented when it goes 1→0.
• A "how many constraints are satisfied" counter - for multi-character targets (Minimum Window Substring).

Choosing the right state is the actual problem-solving step. The window mechanics are identical; the bookkeeping is bespoke.

When to Use Sliding Window

"Contiguous subarray or substring, plus a property that you can update incrementally as the window moves - that's the sliding-window signature."

Reach for it when all of these hold:

• The answer is a contiguous subarray or substring (not a subsequence - order-preserving-but-gappy selections need DP, not a window).
• You're optimizing or counting over those ranges (longest, shortest, maximum sum, number of valid windows).
• The window's validity can be maintained incrementally - adding/removing one element updates the state in O(1) or O(log n), without rescanning the window.

A crucial precondition for many window problems: monotonicity. Growing the window must move you monotonically toward (or away from) validity. This is why "subarray sum equals k with negative numbers" is not a sliding-window problem - adding an element can increase or decrease the sum, so shrinking/growing doesn't behave predictably. That problem needs prefix sum + hash map (Module 11). With all-positive values, the sum grows monotonically and a window works.

Sliding Window vs. Neighboring Techniques

Sliding window and two pointers are close cousins - both move forward-only pointers - but a window maintains aggregate state over a range, while classic two pointers compare the two endpoints. Many sources lump them together; the distinction worth keeping is whether you track what's inside the window (window) or just the boundaries (two pointers).

Common Pitfalls Before You Start

• Recomputing window state from scratch each step. This silently turns an O(n) window into O(n·k) or O(n²). Always update incrementally.
• Using a window when negatives break monotonicity. Check whether growing the window behaves predictably. If not, it's a prefix-sum problem.
• Updating the answer at the wrong time. Longest-valid problems update after restoring validity; shortest-valid problems update while still valid. Mixing these is the most common dynamic-window bug.
• Forgetting to remove the leaving element's state. When left advances, its element must be fully removed from the sum/map/count, or the window's state silently corrupts.
• Off-by-one in fixed windows. The window [right-k+1, right] has exactly k elements when right >= k-1. Begin recording answers only once the window is full.

What This Module Covers

The module is organized by the two variants:

• Fixed Size (12.2–12.7): Maximum Average Subarray, anagram and permutation matching, distinct-elements-in-fixed-window, vowel counting, and the concatenated-words problem. These cement incremental state maintenance at constant width.
• Dynamic Size (12.8–12.22): the heart of the module - longest-without-repeats, character-replacement, minimum-size-subarray-sum, at-most-k-distinct and its many relatives, the "exactly k" counting trick (atMost(k) − atMost(k−1)), and the two hardest, Minimum Window Substring and Subarrays with K Different Integers.

Each problem walks the brute-force → sliding-window arc, so you see why the window is correct, not just that it works. By the end, the dynamic-window skeleton above should be something you can write from memory and adapt on sight.

Let's begin with the fixed-size variant and the cleanest possible example: Maximum Average Subarray I, where the window is a running sum of constant width.

Back to DSA Mastery - Interview Prep, End to End