Sliding Window on Arrays in DSA C++ - Execution Trace

Concept Flow - Sliding Window on Arrays

Start at index 0

↓

Create window of size k

↓

Calculate sum or property of window

↓

Move window forward by 1

↓

Update sum by removing left element, adding right element

↓

Repeat until window reaches end of array

↓

Return or print results

The sliding window moves over the array, updating the sum or property by removing the left element and adding the next right element, avoiding full recalculation each time.

Execution Sample

DSA C++

int arr[] = {1, 3, 2, 6, -1, 4, 1, 8, 2};
int k = 5;
int sum = 0;
for (int i = 0; i < k; i++) sum += arr[i];
for (int i = k; i < 9; i++) {
  sum += arr[i] - arr[i - k];
}

Calculates the sum of every subarray of size 5 by sliding the window across the array.

Execution Table

Step	Operation	Window Indices	Sum Calculation	Window Elements	Sum Value
1	Initialize sum with first window	[0..4]	sum = 1+3+2+6+(-1)	[1, 3, 2, 6, -1]	11
2	Slide window right by 1	[1..5]	sum = 11 + 4 - 1	[3, 2, 6, -1, 4]	14
3	Slide window right by 1	[2..6]	sum = 14 + 1 - 3	[2, 6, -1, 4, 1]	12
4	Slide window right by 1	[3..7]	sum = 12 + 8 - 2	[6, -1, 4, 1, 8]	18
5	Slide window right by 1	[4..8]	sum = 18 + 2 - 6	[-1, 4, 1, 8, 2]	14
6	Window reached end	N/A	Stop sliding	N/A	N/A

💡 Window has slid through all subarrays of size 5, no more windows possible.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
sum	0	11	14	12	18	14	14
window_start	0	0	1	2	3	4	4
window_end	4	4	5	6	7	8	8

Key Moments - 3 Insights

Why do we subtract arr[i-k] and add arr[i] instead of recalculating the sum each time?

Because subtracting the element leaving the window and adding the new element entering the window updates the sum efficiently, as shown in steps 2-5 of the execution_table, avoiding repeated full summations.

What happens when the window reaches the end of the array?

As shown in step 6, the window cannot slide further because the window_end index would exceed the array length, so the process stops.

Why do we initialize the sum with the first window before sliding?

Initializing the sum with the first window (step 1) sets the starting point for sliding updates, so subsequent sums can be updated incrementally.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the sum value after sliding the window?

A 12

B 14

C 20

D 18

💡 Hint

Check the 'Sum Value' column at step 3 in the execution_table.

At which step does the window cover indices [3..7]?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Window Indices' column in the execution_table.

If the window size k was 3 instead of 5, how would the initial sum calculation change?

A Sum would be arr[0] + arr[1]

B Sum would be arr[0] + arr[1] + arr[2]

C Sum would be arr[0] + arr[1] + arr[2] + arr[3]

D Sum would be arr[0] only

💡 Hint

Initial sum is the sum of the first k elements, see step 1 in execution_table.

Concept Snapshot

Sliding Window on Arrays:
- Move a fixed-size window over the array
- Initialize sum with first k elements
- Slide window by removing left element, adding next right element
- Update sum efficiently without full recalculation
- Repeat until window reaches array end

Full Transcript

Sliding window on arrays means moving a fixed-size window across the array to calculate sums or other properties efficiently. We start by summing the first k elements. Then, for each step, we slide the window right by one position. We update the sum by subtracting the element leaving the window and adding the new element entering. This avoids recalculating the sum from scratch each time. We continue sliding until the window reaches the end of the array. This method is efficient and commonly used in problems involving subarrays of fixed size.

Practice

1. What is the main purpose of the sliding window technique on arrays?

easy

A. To find the maximum element in the entire array

B. To sort the array in ascending order

C. To efficiently process subarrays of fixed size without recomputing everything

D. To reverse the array elements

Solution

1. Step 1: Understand the sliding window concept

   The sliding window technique moves a fixed-size window over the array to process subarrays efficiently.

2. Step 2: Identify the purpose

   It avoids recomputing sums or other values for each subarray by updating results incrementally.

3. Final Answer:

   To efficiently process subarrays of fixed size without recomputing everything -> Option C

4. Quick Check:

   Sliding window = efficient fixed-size subarray processing [OK]

Hint: Think of a moving window that updates results quickly [OK]

Common Mistakes:

• Confusing sliding window with sorting
• Thinking it reverses arrays
• Assuming it finds max of whole array only

2. Which of the following is the correct syntax to start a sliding window loop of size k over an array arr of length n in C++?

easy

A. for (int i = k; i < n; i++)

B. for (int i = 0; i < n; i += k)

C. for (int i = 0; i < n + k; i++)

D. for (int i = 0; i <= n - k; i++)

Solution

1. Step 1: Determine valid window start indices

   The window of size k can start at indices from 0 up to n-k to fit inside the array.

2. Step 2: Check loop condition

   The loop must run while i <= n-k to include the last valid window.

3. Final Answer:

   for (int i = 0; i <= n - k; i++) -> Option D

4. Quick Check:

   Loop runs from 0 to n-k inclusive [OK]

Hint: Window start max index = n - k [OK]

Common Mistakes:

• Using i < n instead of i <= n-k
• Incrementing i by k skips windows
• Starting loop at k instead of 0

3. What is the output of the following C++ code?

int arr[] = {1, 3, 2, 6, -1, 4, 1, 8, 2};
int n = 9, k = 5;
int max_sum = 0, window_sum = 0;
for (int i = 0; i < k; i++) {
    window_sum += arr[i];
}
max_sum = window_sum;
for (int i = k; i < n; i++) {
    window_sum += arr[i] - arr[i - k];
    if (window_sum > max_sum) max_sum = window_sum;
}
std::cout << max_sum << std::endl;

medium

A. 18

B. 17

C. 16

D. 19

Solution

1. Step 1: Calculate initial window sum of first 5 elements

   Sum = 1+3+2+6+(-1) = 11

2. Step 2: Slide window and update sums

   Next windows:
   i=5: sum=11+4-1=14
   i=6: sum=14+1-3=12
   i=7: sum=12+8-2=18
   i=8: sum=18+2-6=14
   Max sum found is 18

3. Final Answer:

   18 -> Option A

4. Quick Check:

   Max sliding window sum = 18 [OK]

Hint: Add new element, subtract old element in window [OK]

Common Mistakes:

• Not subtracting the element leaving the window
• Incorrect initial sum calculation
• Off-by-one errors in loop limits

4. Identify the bug in this sliding window code that finds the minimum sum of subarrays of size k:

int min_sum = INT_MAX, window_sum = 0;
for (int i = 0; i < n; i++) {
    window_sum += arr[i];
    if (i >= k) {
        window_sum -= arr[i - k - 1];
    }
    if (i >= k - 1 && window_sum < min_sum) {
        min_sum = window_sum;
    }
}

medium

A. The subtraction should happen when i >= k, but the subtraction index is off by one

B. The subtraction should happen when i >= k - 1, not i >= k

C. The subtraction should happen when i >= k, but loop should start from i = 1

D. The condition should be i > k instead of i >= k

Solution

1. Step 1: Check subtraction timing

   The condition if (i >= k) for subtraction is correct; it starts after the first full window of size k.

2. Step 2: Identify the index bug

   The code subtracts arr[i - k - 1], but it should be arr[i - k]. This is off-by-one; for i = k, it subtracts arr[-1] instead of arr[0].

3. Final Answer:

   The subtraction should happen when i >= k, but the subtraction index is off by one -> Option A

4. Quick Check:

   Index i - k - 1 causes arr[-1] access [OK]

Hint: Check when subtraction starts and which element is removed [OK]

Common Mistakes:

• Starting subtraction too early or too late
• Using wrong index for subtraction
• Not updating min_sum correctly

5. Given an array arr and an integer k, how would you find the maximum average of any subarray of size k using the sliding window technique?

hard

A. Calculate sum of all subarrays of size k and divide each by k, then find max average

B. Use sliding window to find max sum of subarrays of size k, then divide max sum by k

C. Sort the array and take average of last k elements

D. Use two nested loops to check all subarrays and keep track of max average

Solution

1. Step 1: Use sliding window to find max sum of size k

   Sliding window efficiently finds max sum by adding new element and removing old one.

2. Step 2: Calculate max average from max sum

   Divide the max sum by k to get the maximum average.

3. Final Answer:

   Use sliding window to find max sum of subarrays of size k, then divide max sum by k -> Option B

4. Quick Check:

   Max average = max sum / k using sliding window [OK]

Hint: Find max sum first, then divide by k for average [OK]

Common Mistakes:

• Sorting array instead of using sliding window
• Using nested loops causing inefficiency
• Dividing sums incorrectly