15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A fixed size sliding window is a contiguous segment of exactly k values that moves right one position at a time. Each move subtracts the value that leaves and adds the value that enters, so the window sum updates in O(1). Scanning all n - k + 1 windows takes O(n) time and O(1) extra space.
| Window size | right - left + 1 = k, with 1 <= k <= length |
|---|---|
| Number of windows | n - k + 1 |
| Slide update | sum = sum - A[left] + A[right + 1], then left and right each move up by 1 |
| Time | O(k) for the first window plus O(n - k) slides = O(n) |
| Recomputing every window | O(nk), which the running sum avoids |
| Extra space | O(1): left, right, sum and best |
This lesson assumes you can:
Use length for the number of values in an array. Valid indices run from 0 through length - 1.
A window is a contiguous inclusive segment from left through right.
Its size is:
For a fixed window size k, every evaluated window must satisfy:
Before processing, validate:
An empty array, k = 0, a negative k, or k > length is invalid.
Use this array:
1A = [2, 1, 5, 1, 3, 2]
2 0 1 2 3 4 5 indices
3
4k = 3Find the maximum sum among all contiguous windows containing exactly three values.
Start with the first possible window. A size-three window beginning at index 0 ends at index 2.
1A = [2, 1, 5, 1, 3, 2]
2 0 1 2 3 4 5
3 └───────┘
4 left = 0
5 right = 2The initial sum is:
The first complete state is:
1window = A[0..2] = [2, 1, 5]
2sum = 8
3best = 8There are:
fixed-size windows to examine:
1A[0..2] = [2, 1, 5]
2A[1..3] = [1, 5, 1]
3A[2..4] = [5, 1, 3]
4A[3..5] = [1, 3, 2]Do not add all three values again after every move. When the window slides right by one position, two membership changes occur:
left boundary.right boundary.The values in the middle remain in the window. Their contribution to sum does not change.
A fixed-size sliding window in one picture: keep a running sum, add the number that enters, subtract the one that leaves, and remember the best. Here the best is 9.
The window is [2, 1, 5].
The outgoing value is A[left] = A[0] = 2.
The incoming value is A[right + 1] = A[3] = 1.
Update the running sum before moving the boundaries:
Then increment both boundaries:
1left = 1
2right = 3The new window is [1, 5, 1]. Its sum is 7, which does not exceed best.
The outgoing value is A[1] = 1.
The incoming value is A[4] = 3.
Move both boundaries:
1left = 2
2right = 4The window is [5, 1, 3]. Since 9 > 8, update best to 9.
The outgoing value is A[2] = 5.
The incoming value is A[5] = 2.
Move both boundaries:
1left = 3
2right = 5The window is [1, 3, 2]. Its sum does not exceed best.
Now right = 5, which is the final index. The algorithm has evaluated the window ending at length - 1, so return:
1best = 9The algorithm preserves the following rule at every evaluated state:
sum equals the sum of exactly the elements from index left through index right.right - left + 1 = k.best is the largest sum among all complete windows evaluated so far.These statements form the loop invariant.
For example, at State 2:
1left = 2
2right = 4
3window = A[2..4] = [5, 1, 3]The boundary relation holds:
The running sum matches that exact window:
The windows evaluated so far have sums 8, 7, and 9. Therefore:
1best = 9Adjacent fixed-size windows overlap in k - 1 positions. Moving one position right removes only A[left] and introduces only the next value after the old right boundary.
Reject invalid window sizes first. A size-k window cannot exist if k <= 0 or k > length.
For a valid k:
left = 0.right = k - 1. This makes the first window exactly A[0..k-1].k values to form the initial sum.best to this actual initial sum. Do not use 0, because all window sums may be negative.A[left], the outgoing value.A[right + 1], the incoming value.left.right.best.best.The incoming element is at right + 1 before right advances. The outgoing element is at left before left advances.
Function contract
1maxFixedWindowSum(values, k)
2
3Input:
4 values: an array of numeric values
5 k: required number of contiguous values in each window
6
7Return:
8 the maximum sum among all contiguous windows of exactly k values
9
10Invalid input:
11 rejects when k <= 0 or k > length(values)
12 An empty array is rejected for every k.
13
14Mutation behavior:
15 does not modify values
16
17Auxiliary variables:
18 left, right, sum, best101 function maxFixedWindowSum(values, k):
202 n ← length(values)
303
404 if k <= 0 or k > n:
505 reject InvalidWindowSize
606
707 left ← 0
808 right ← k - 1
909 sum ← 0
1010
1111 for index ← 0 to k - 1:
1212 sum ← sum + values[index]
1313
1414 best ← sum
1515
1616 while right < n - 1:
1717 sum ← sum - values[left]
1818 sum ← sum + values[right + 1]
1919 left ← left + 1
2020 right ← right + 1
2121
2222 if sum > best:
2323 best ← sum
2424
2525 return bestLines 11–12 form the initial window sum. Lines 16–23 evaluate each later window exactly once.
Use the original input:
1values = [2, 1, 5, 1, 3, 2]
2k = 3| Pseudocode line | State |
|---|---|
| 02 | n = 6 |
| 04 | k = 3 is valid because 1 <= 3 <= 6 |
| 07 | left = 0 |
| 08 | right = 2 |
| 09 | sum = 0 |
Lines 11–12 run for index = 0 through 2.
index | Update on line 12 | sum |
|---|---|---|
| 0 | 0 + values[0] = 0 + 2 | 2 |
| 1 | 2 + values[1] = 2 + 1 | 3 |
| 2 | 3 + values[2] = 3 + 5 | 8 |
| Pseudocode line | State |
|---|---|
| 14 | best = 8 |
At this point:
1left = 0
2right = 2
3sum = 8
4best = 8Line 16 checks:
1right < n - 1
22 < 5The condition is true.
| Pseudocode line | Update | State after update |
|---|---|---|
| 17 | sum = 8 - values[0] | sum = 6 |
| 18 | sum = 6 + values[3] | sum = 7 |
| 19 | increment left | left = 1 |
| 20 | increment right | right = 3 |
| 22 | check 7 > 8 | false |
| 23 | no update | best = 8 |
The represented window is now values[1..3] = [1, 5, 1].
Line 16 checks:
13 < 5The condition is true.
| Pseudocode line | Update | State after update |
|---|---|---|
| 17 | sum = 7 - values[1] | sum = 6 |
| 18 | sum = 6 + values[4] | sum = 9 |
| 19 | increment left | left = 2 |
| 20 | increment right | right = 4 |
| 22 | check 9 > 8 | true |
| 23 | best = sum | best = 9 |
The represented window is now values[2..4] = [5, 1, 3].
Line 16 checks:
14 < 5The condition is true.
| Pseudocode line | Update | State after update |
|---|---|---|
| 17 | sum = 9 - values[2] | sum = 4 |
| 18 | sum = 4 + values[5] | sum = 6 |
| 19 | increment left | left = 3 |
| 20 | increment right | right = 5 |
| 22 | check 6 > 9 | false |
| 23 | no update | best = 9 |
The represented window is now values[3..5] = [1, 3, 2].
Line 16 checks:
15 < 5The condition is false. The loop stops.
Line 25 returns:
19Assume values has length n and the validation step accepts k. Therefore:
The algorithm returns the maximum sum among all contiguous windows of exactly k values.
Lines 7 and 8 set:
1left = 0
2right = k - 1The initial boundaries have size:
Lines 11–12 add values[0] through values[k - 1]. Therefore, sum equals the sum of exactly the values from left through right.
Line 14 sets best = sum. At this moment, exactly one complete window has been evaluated, so best is the largest sum among all evaluated windows.
The invariant holds before the while loop begins.
Assume the invariant holds at the start of one while-loop iteration. The current window is values[left..right], and it has size k.
Line 17 subtracts values[left], which is the value leaving when the window moves right.
Line 18 adds values[right + 1], which is the value entering the next window.
Lines 19 and 20 increment both boundaries. The new boundaries are:
1new left = old left + 1
2new right = old right + 1Their size remains:
The algorithm removes exactly the old leftmost value and adds exactly the new rightmost value, so sum becomes the sum of exactly the elements in the new window.
Lines 22–23 compare this complete window sum with best. After the comparison, best is the largest sum among every window evaluated so far.
The invariant is preserved.
The loop continues while:
1right < n - 1Each iteration increments right by one. The loop terminates when right = n - 1.
The algorithm evaluates every valid fixed-size window from:
1values[0..k-1]through:
1values[n-k..n-1]At termination, the invariant states that best is the largest sum among all evaluated windows. All size-k windows have been evaluated, so best is the required maximum window sum.
Let n be length(values).
Lines 11–12 read and add exactly k elements.
1k additionsThe cost is:
There are:
total window positions.
The first position is formed during initialization. Every later position requires one slide, so there are:
slides.
Each slide performs constant work:
Sliding costs:
The total work is:
Because k <= n, the total is:
The algorithm uses:
1left, right, sum, best, n, indexIt does not allocate another array and does not modify the input array.
Auxiliary space is:
If each window sum were recomputed from scratch, each of the n - k + 1 windows could require up to k additions.
That work is:
which is:
The running-sum approach avoids re-adding the k - 1 overlapping values after each one-step slide.
Reject invalid sizes before forming the initial window.
| Input | Required result |
|---|---|
values = [], k = 1 | reject as invalid |
values = [4, -2, 7], k = 0 | reject as invalid |
values = [4, -2, 7], k = 4 | reject as invalid |
Without validation, setting right = k - 1 or reading the initial window can access positions that do not exist.
| Input | Windows | Result |
|---|---|---|
values = [4, -2, 7], k = 1 | [4], [-2], [7] | 7 |
values = [4, -2, 7], k = 3 | [4, -2, 7] | 9 |
values = [-5, -2, -7], k = 2 | [-5, -2], [-2, -7] | -7 |
The all-negative case requires best to begin as the first real window sum.
Incorrect update:
1sum ← sum + values[right + 1]Exposing input:
1values = [2, 1, 5, 1]
2k = 3Initial window:
1[2, 1, 5]
2sum = 8The next window should be [1, 5, 1] with sum 7.
The incorrect update produces:
1sum = 8 + 1 = 9That 9 still includes the outgoing 2, so it is not the next window sum.
Correction:
1sum ← sum - values[left]
2sum ← sum + values[right + 1]Incorrect loop assumption:
1Stop before evaluating the window whose right boundary is length - 1.Exposing input:
1values = [1, 1, 10]
2k = 2The windows are:
1[1, 1] sum = 2
2[1, 10] sum = 11Stopping before the final right endpoint misses [1, 10] and can return 2 instead of 11.
Correction: evaluate every right endpoint from k - 1 through length - 1. In the pseudocode, continue while:
1right < n - 1and process the slide that makes right = n - 1.
best to zeroIncorrect initialization:
1best ← 0Exposing input:
1values = [-5, -2, -7]
2k = 2Window sums are:
1[-5, -2] = -7
2[-2, -7] = -9The correct answer is -7.
With best = 0, neither negative window sum exceeds 0, so the incorrect result is:
10Correction:
1best ← sumafter computing the initial window sum.
Implement this contract:
1maxFixedWindowSum(values, k)
2
3Returns:
4 the maximum sum among all contiguous windows of exactly k values
5
6Rejects:
7 invalid k values where k <= 0 or k > length(values)
8
9Does not:
10 modify valuesThe tests cover:
k = 1,k = length(values),1def max_fixed_window_sum(values, k):
2 n = len(values)
3 if k <= 0 or k > n:
4 raise ValueError("invalid window size")
5 left, right = 0, k - 1
6 total = sum(values[:k]) # first window
7 best = total # not 0: every window sum may be negative
8 while right < n - 1:
9 total = total - values[left] + values[right + 1] # one out, one in
10 left += 1
11 right += 1
12 if total > best:
13 best = total
14 return best
15
16print("max window sum =", max_fixed_window_sum([2, 1, 5, 1, 3, 2], 3))
17print("all negative =", max_fixed_window_sum([-5, -2, -7], 2))
18try:
19 max_fixed_window_sum([4, -2, 7], 4)
20except ValueError:
21 print("k = 4 on 3 values: rejected")1public class Main {
2 static int maxFixedWindowSum(int[] values, int k) {
3 int n = values.length;
4 if (k <= 0 || k > n) throw new IllegalArgumentException("invalid window size");
5 int left = 0, right = k - 1;
6 int sum = 0;
7 for (int index = 0; index < k; index++) sum += values[index]; // first window
8 int best = sum; // not 0: every window sum may be negative
9 while (right < n - 1) {
10 sum = sum - values[left] + values[right + 1]; // one out, one in
11 left++;
12 right++;
13 if (sum > best) best = sum;
14 }
15 return best;
16 }
17
18 public static void main(String[] args) {
19 System.out.println("max window sum = " + maxFixedWindowSum(new int[]{2, 1, 5, 1, 3, 2}, 3));
20 System.out.println("all negative = " + maxFixedWindowSum(new int[]{-5, -2, -7}, 2));
21 try {
22 maxFixedWindowSum(new int[]{4, -2, 7}, 4);
23 } catch (IllegalArgumentException e) {
24 System.out.println("k = 4 on 3 values: rejected");
25 }
26 }
27}1#include <iostream>
2#include <stdexcept>
3#include <vector>
4using namespace std;
5
6int maxFixedWindowSum(const vector<int>& values, int k) {
7 int n = values.size();
8 if (k <= 0 || k > n) throw invalid_argument("invalid window size");
9 int left = 0, right = k - 1;
10 int sum = 0;
11 for (int index = 0; index < k; index++) sum += values[index]; // first window
12 int best = sum; // not 0: every window sum may be negative
13 while (right < n - 1) {
14 sum = sum - values[left] + values[right + 1]; // one out, one in
15 left++;
16 right++;
17 if (sum > best) best = sum;
18 }
19 return best;
20}
21
22int main() {
23 cout << "max window sum = " << maxFixedWindowSum({2, 1, 5, 1, 3, 2}, 3) << "\n";
24 cout << "all negative = " << maxFixedWindowSum({-5, -2, -7}, 2) << "\n";
25 try {
26 maxFixedWindowSum({4, -2, 7}, 4);
27 } catch (const invalid_argument&) {
28 cout << "k = 4 on 3 values: rejected" << endl;
29 }
30}1function maxFixedWindowSum(values, k) {
2 const n = values.length;
3 if (k <= 0 || k > n) throw new RangeError('invalid window size');
4 let left = 0;
5 let right = k - 1;
6 let sum = 0;
7 for (let index = 0; index < k; index++) sum += values[index]; // first window
8 let best = sum; // not 0: every window sum may be negative
9 while (right < n - 1) {
10 sum = sum - values[left] + values[right + 1]; // one out, one in
11 left++;
12 right++;
13 if (sum > best) best = sum;
14 }
15 return best;
16}
17
18console.log(`max window sum = ${maxFixedWindowSum([2, 1, 5, 1, 3, 2], 3)}`);
19console.log(`all negative = ${maxFixedWindowSum([-5, -2, -7], 2)}`);
20try {
21 maxFixedWindowSum([4, -2, 7], 4);
22} catch (e) {
23 console.log('k = 4 on 3 values: rejected');
24}Neighbouring windows share k - 1 values, so a slide only subtracts one value and adds one. That is constant work for each of the n - k slides, plus O(k) for the first window. Recomputing each window from scratch would cost O(nk).
Window sums can all be negative. For [-5, -2, -7] with k = 2 the sums are -7 and -9, and the answer is -7. With best = 0 the code would return 0, a sum no window has.
No window of k values exists, so the function rejects the input. It also rejects k <= 0 and an empty array. Check 1 <= k <= length before reading anything, or the first window reads past the end.
It stops after evaluating the window whose right edge is the last index. The loop runs while right < n - 1, and the final slide makes right equal n - 1. Stopping one slide early misses windows such as [1, 10] in [1, 1, 10].
A fixed window always holds exactly k values, so both edges move together by one. A variable-size window grows and shrinks depending on a condition, and its edges move separately. This page covers only the fixed case.