Many problems ask you to compute something over every contiguous subarray of length k in an array of length n. The brute-force approach recomputes the answer from scratch for each subarray, doing O(k) work per position and O(n * k) total. The sliding window technique eliminates this redundancy by recognizing that consecutive windows overlap in k - 1 elements. Instead of recomputing, you update the answer: add the element entering the window on the right and remove the element leaving on the left.

Think of it like a physical window frame sliding across a row of numbers painted on a wall. At each step, you see exactly k numbers. Moving the frame one position to the right reveals one new number on the right edge and hides one number on the left edge. Everything in between stays the same. Your running computation only needs to account for the two elements that changed.

Why O(n) Instead of O(n * k)

Each element in the array is involved in exactly two operations: it is added when it enters the window's right edge, and it is removed when it leaves the window's left edge. That is 2n operations total regardless of k. Whether your window is size 3 or size 3,000, the work per element is constant.

This is the key insight that makes sliding window problems efficient. You are not recomputing the answer - you are maintaining it incrementally.

The Two Phases

Every fixed-size sliding window solution has two phases:

Phase 1 - Initialize. Process the first k elements to build the initial window state. For a sum problem, add the first k elements. For a frequency problem, count occurrences in the first k characters. This phase runs once and costs O(k).

Phase 2 - Slide. For each new position from index k to n - 1, add the incoming element (index i) and remove the outgoing element (index i - k). Update the answer. This phase runs n - k times, each step O(1), for O(n) total.

Running State Examples

The "state" you maintain depends on the problem:

• Maximum sum of subarray of size k - maintain a running sum. Add nums[i], subtract nums[i - k].
• Maximum/minimum in window - maintain a monotonic deque (covered later in this lesson).
• Anagram detection - maintain a frequency count of characters in the current window and compare to the target frequency.
• Number of distinct elements in window - maintain a hash map of element counts.

The pattern is always the same: define your state, build it for the first window, then update it incrementally as the window slides.

Now that you understand the concept, here is the concrete template you should internalize. Every fixed-size sliding window problem follows this skeleton - only the state initialization, update logic, and answer extraction change between problems.

The Template

The three pieces you customize for each problem are:

1. State - what you track (sum, frequency map, deque, count of distinct elements)
2. Add/Remove - how incoming and outgoing elements modify the state
3. Evaluate - how you extract the answer from the current state

Concrete Example: Maximum Sum Subarray of Size k

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

• Initial window [2, 1, 5] → sum = 8
• Slide to [1, 5, 1] → sum = 8 + 1 - 2 = 7
• Slide to [5, 1, 3] → sum = 7 + 3 - 1 = 9
• Slide to [1, 3, 2] → sum = 9 + 2 - 5 = 6
• Maximum sum = 9

Step through the buy-and-sell stock problem to see how a single scan tracks the minimum price and maximum profit:

Edge Cases to Handle

Before writing the sliding logic, check these conditions:

• k > n - The window does not fit. Return a sentinel or raise an error depending on the problem statement.
• k = n - Only one window exists. The initialization phase gives the answer; no sliding needed.
• k = 1 - Every element is its own window. The problem degenerates to scanning the array once.
• Empty array - n = 0 means no window is possible.

Adding these checks as early returns at the top of your function prevents index errors and shows your interviewer you think about boundaries.

Practice

Apply the fixed window template to find the maximum average subarray.

A classic application of fixed-size sliding windows is detecting whether one string contains a permutation (anagram) of another. The key insight is that any permutation of a string has the same length and the same character frequencies - only the order differs. So checking if s2 contains a permutation of s1 becomes: slide a window of size len(s1) across s2 and check if the character frequencies in the window match s1's frequencies.

The Frequency Map Approach

Build a frequency map for s1. Then maintain a frequency map for the current window in s2. At each slide, increment the count for the incoming character and decrement the count for the outgoing character. If the two maps match, the current window is an anagram of s1.

Optimizing the Comparison

Comparing two frequency maps at every step costs O(26) for lowercase English letters - constant time, so the overall algorithm is already O(n). But you can optimize further by tracking a matches counter: the number of characters whose window frequency equals the target frequency. When matches == 26, the window is a permutation.

The matches variable turns the O(26) comparison into O(1) per slide. Each character change updates at most two entries in the frequency array, and each update adjusts matches by at most 1.

Watch how the sliding window checks for a permutation by comparing frequency maps:

Why Delete Zero Counts

In the Counter approach, deleting keys with zero counts (del window[char] when count reaches 0) is important for correct comparison. If you leave zero-count keys in the window map, the comparison window == target may fail even when the windows match - because the target map does not contain keys for characters that are not in s1. Cleaning up zeros keeps the maps structurally identical when their contents are equivalent.

Step through the sliding window as it finds all anagram starting positions:

Practice

Implement the permutation-in-string check using a fixed window with frequency maps.

Some fixed-window problems require more than a running sum or frequency map. The "sliding window maximum" problem asks for the maximum element in every window of size k. A naive approach checks all k elements per window, costing O(n * k). A sorted structure like a balanced BST gives O(n log k). But a monotonic deque solves it in O(n) by maintaining a cleverly ordered subset of the window's elements.

The Problem with Simple Max Tracking

You might think: just track the current maximum with a variable. When the incoming element is larger, update the max. The problem arises when the outgoing element is the current maximum. You cannot recover the second-largest element without scanning the entire window - and scanning costs O(k) per step.

A heap (priority queue) seems like a natural fit, but removing an arbitrary element from a heap costs O(k) because you have to find it first. Lazy deletion (marking elements as removed and skipping them when they surface at the top) works but adds complexity and worst-case overhead.

The Monotonic Deque

A monotonic deque (double-ended queue) maintains elements in decreasing order from front to back. The front always holds the index of the current window maximum. Here is how it works:

Invariant: Every element in the deque is a potential future maximum. An element is useless if there is a newer element in the window that is larger - it can never be the maximum because the newer, larger element will outlast it in the window.

Adding an element (right side): Before pushing index i onto the back of the deque, pop all indices from the back whose values are less than or equal to nums[i]. They can never be the window maximum while nums[i] is in the window, so they are discarded.

Removing an element (left side): If the front of the deque equals the outgoing index i - k, pop it. The maximum has left the window.

Reading the maximum: The front of the deque is always the index of the maximum element in the current window.

Why O(n)

Each index is pushed onto the deque exactly once and popped at most once. The while loop that removes smaller elements from the back may pop multiple elements in a single step, but each of those elements was pushed once and is now being popped once. Over the entire array, total pushes = n and total pops <= n, giving 2n operations. The amortized cost per element is O(1).

This is the same argument as the sliding window sum: each element participates in a constant number of operations across its lifetime in the window.

When to Use a Monotonic Deque

Use a monotonic deque when the problem asks for the maximum or minimum in every fixed-size window. The deque approach extends to:

• Sliding window minimum - maintain the deque in increasing order instead of decreasing.
• Sliding window max minus min - maintain two deques simultaneously, one for max and one for min.
• First/last element greater than X in window - the deque front or back gives this directly.

The pattern also appears in variable-size window problems and in dynamic programming optimizations, but for this lesson the focus is fixed windows.

Practice

Implement the sliding window maximum using a monotonic deque.