What a sliding window is
A window is a contiguous range of an array, from index left to index right. A sliding window algorithm moves that range along the array one step at a time instead of examining every possible range from scratch. Two index variables, the two pointers, mark the window's edges. Only one thing is recomputed on each move: the part of the answer that changed because one element entered the window or one element left it.
The technique matters because problems about contiguous subarrays or substrings are usually described with two nested loops, one for the start and one for the end, which cost O(n²). If the question can be answered by tracking a running total or a set of the window's contents, the window can slide across the array in a single pass, and the cost drops to O(n).
Fixed-size window
The simplest case is a window whose length k never changes. Take the maximum sum of any k consecutive elements. Summing each window separately costs O(n · k). Sliding reuses the previous sum: add the element that enters on the right, subtract the element that leaves on the left.
static int MaxSumOfWindow(int[] nums, int k) {
if (k <= 0 || k > nums.Length) return 0;
int sum = 0;
for (int i = 0; i < k; i++) sum += nums[i];
int best = sum;
for (int right = k; right < nums.Length; right++) {
sum += nums[right];
sum -= nums[right - k];
best = Math.Max(best, sum);
}
return best;
}
For nums = {2, 1, 5, 1, 3, 2} and k = 3, the windows sum to 8, 7, 9 and 6, so the method returns 9. The first loop builds the first window, and the second loop slides it with two arithmetic operations per step.
Variable-size window
In most lessons of this chapter the window's length changes. The usual rule is: grow the window on the right, and shrink it from the left whenever it breaks the condition. Every iteration then ends with a valid window, and you record its length.
Here is the longest subarray with a sum of at most S, for an array of positive integers:
static int LongestAtMost(int[] nums, int S) {
int left = 0, sum = 0, best = 0;
for (int right = 0; right < nums.Length; right++) {
sum += nums[right];
while (sum > S) {
sum -= nums[left];
left++;
}
best = Math.Max(best, right - left + 1);
}
return best;
}
With nums = {3, 2, 5, 2, 2, 1, 1, 3, 1, 2} and S = 11, it returns 6, the length of 2, 2, 1, 1, 3, 1 (sum 10). If every element is larger than S, the window ends each step empty and the method returns 0.
The length of the window is right - left + 1, because both ends are included. Off-by-one errors in this formula are the most common mistake. Some solutions use a half-open window instead, where last is one past the end and the length is last - first. Pick one convention and keep it throughout.
Why it is linear
The inner while loop makes the code look quadratic, but it isn't. Both pointers only move forward. right advances once per outer iteration, and left never goes back, so it advances at most n times in total. Every element enters the window once and leaves it at most once. The work over the whole run is about 2n steps, so the time is O(n). This kind of accounting, where the cost is counted over the whole run instead of per iteration, is called amortized analysis.
The extra space depends on what the window must remember. A running sum needs O(1). A set of the values currently in the window, or a count per value, needs up to O(n) in the worst case.
What the window can track in C#
Different problems need different bookkeeping. The pattern stays the same and only the state changes:
- A running sum in an
int(or alongif the total can pass about 2.1 billion). - A
HashSet<int>for "no repeated values".Addreturnsfalsewhen the value is already present, andContainsasks without changing the set. - A
Dictionary<int, int>of counts for "at most K distinct values".dict.Countis the number of distinct values, and a key must be removed once its count reaches 0, or the size would be wrong. - Indices for the answer itself, when the problem asks where the best window is, not just how long it is.
Two C# habits help with these. Arrays use Length, while collections use Count, both without parentheses. And reading a missing key from a Dictionary with dict[key] throws a KeyNotFoundException, so use GetValueOrDefault or ContainsKey when the key might not be there yet.
When the technique applies
A sliding window works when two conditions hold:
- The answer is about a contiguous range. Subsequences, which may skip elements, don't fit.
- Shrinking the window can only help the condition, and growing it can only hurt. A sum limit on positive numbers is a good example: removing an element always lowers the sum.
The second point is why negative numbers are a trap. In a sum problem with negative values, removing an element from the left can raise the sum, so the loop that shrinks until the sum is small enough no longer finds the right window. Those problems need other tools, such as prefix sums.
A checklist for the lessons ahead
- Decide what a valid window is, in one sentence.
- Choose the state that tells you whether the window is valid after each change, such as a sum, a set or a dictionary.
- Move
rightforward in aforloop and update the state with the new element. - While the window is invalid, remove the element at
leftfrom the state and moveleftforward. - Record the answer from the valid window, using
right - left + 1for its length.
Some lessons use a variation: they loop over left instead and push right forward as far as the window stays valid. Both versions keep two indices that never move backward, and both are linear.
Key takeaways
- A sliding window reuses work: update the state for the element that enters and the one that leaves, instead of recomputing the window.
- Fixed windows move both ends together. Variable windows grow on the right and shrink on the left to stay valid.
- The nested loops are amortized linear because neither pointer moves backward.
- The window's length is
right - left + 1when both ends are included. - The technique needs a contiguous range, and a condition that shrinking helps; negative numbers can break that for sums.