Sliding Window: From Quadratic Loops to a Linear Scan
Derive a fixed-window algorithm, state its invariant and test the boundary cases yourself.
Key Learning Objectives
- Recognise fixed-size contiguous-subarray questions.
- Explain the rolling-sum invariant.
- Implement O(n) maximum-window sum.
- Handle invalid window sizes explicitly.
Spot the repeated work
Suppose you need the largest sum of exactly k consecutive values. The direct solution adds each length-k slice independently. There are about n-k+1 candidate slices, each requiring k additions, for O(nk) time. Adjacent slices overlap in k-1 places: recomputing their shared values wastes work. Sliding window is useful when the answer for a new contiguous interval can be updated cheaply from the previous interval. This fixed-length case has a particularly simple invariant.
Maintain a rolling sum
First compute the sum of the first k elements. When moving the window right by one place, subtract the element that leaves and add the element that enters. After each update, currentSum equals the sum of precisely the active k items. That invariant proves the algorithm is correct. The code scans each element a constant number of times, so time is O(n) and additional working memory is O(1). Be careful with all-negative arrays: initialising best to zero would be wrong.
function maxWindowSum(values: number[], k: number): number | null {
if (k < 1 || k > values.length) return null;
let sum = 0;
for (let i = 0; i < k; i++) sum += values[i];
let best = sum;
for (let right = k; right < values.length; right++) {
sum += values[right] - values[right - k];
best = Math.max(best, sum);
}
return best;
}
The previous window sum changes by one outgoing and one incoming element; null reports an invalid window size.
Understand when the technique does not transfer directly
A fixed-size rolling sum is not automatically a solution to variable-size questions. For a shortest subarray with sum at least a target, shrinking a window assumes that extending the right edge cannot make the sum smaller; that works for nonnegative inputs but breaks with negative values. For mixed-sign numbers, prefix sums and an appropriate data structure may be necessary. Always write down the invariant and input assumptions before adapting a memorised template.
Build It: Study streak analyser
Given daily study hours, report the highest total for any consecutive seven days.
Project Deliverables
- A typed rolling-window function.
- Tests for negative values, one-element arrays, k equal to n and invalid k.
- A complexity explanation in two sentences.
Acceptance Criteria
- Output matches brute-force results for at least five test arrays.
- No nested full-window recomputation in the final algorithm.
- Invalid k is handled without throwing.
Next Steps & Related Learning
This interactive lesson is part of the LeetCode Practice curriculum. Continue exploring or try another interactive lesson: