Sliding Window on Arrays in DSA C - Execution Trace

Concept Flow - Sliding Window on Arrays

Initialize window start and end pointers

↓

Expand window by moving end pointer

↓

Check if window size reached target

↓

Keep expanding

↓

Slide window forward by moving start pointer

↓

Repeat until end reaches array end

The sliding window moves over the array by expanding the end pointer until the window size is reached, then processes the window and slides forward by moving the start pointer.

Execution Sample

DSA C

int arr[] = {1, 3, 5, 2, 8, 7};
int k = 3;
for (int i = 0; i <= 6 - k; i++) {
    int sum = 0;
    for (int j = i; j < i + k; j++) {
        sum += arr[j];
    }
    printf("%d ", sum);
}

Calculates sum of every subarray of size 3 using a sliding window approach.

Execution Table

Step	Operation	Window Start	Window End	Window Elements	Sum Computed	Visual State
1	Initialize window	0	2	[1, 3, 5]	0	Window covers indices 0 to 2
2	Calculate sum	0	2	[1, 3, 5]	9	Sum = 1+3+5 = 9
3	Slide window forward	1	3	[3, 5, 2]	0	Window moves to indices 1 to 3
4	Calculate sum	1	3	[3, 5, 2]	10	Sum = 3+5+2 = 10
5	Slide window forward	2	4	[5, 2, 8]	0	Window moves to indices 2 to 4
6	Calculate sum	2	4	[5, 2, 8]	15	Sum = 5+2+8 = 15
7	Slide window forward	3	5	[2, 8, 7]	0	Window moves to indices 3 to 5
8	Calculate sum	3	5	[2, 8, 7]	17	Sum = 2+8+7 = 17
9	End	-	-	-	-	Window end reached array end, stop

💡 Window end pointer reached the last index of the array, no more windows of size k possible.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	Final
window_start	0	0	1	2	3	3
window_end	2	2	3	4	5	5
sum	0	9	10	15	17	17

Key Moments - 3 Insights

Why do we move the window start pointer after processing the window?

After calculating the sum for the current window (see steps 2,4,6,8), we move the start pointer forward to slide the window and consider the next subarray. This keeps the window size constant.

Why does the loop stop when window_end reaches the last index?

Because the window size is fixed (k=3), once the window end pointer reaches the last element, no further full windows of size k can be formed. This is shown in step 9 where execution stops.

Why do we reset sum to 0 before calculating each window's sum?

Sum is reset before each calculation (steps 2,4,6,8) to avoid adding previous window sums repeatedly. This ensures each window's sum is calculated fresh from its elements.

Visual Quiz - 3 Questions

Look at the execution table, what is the sum computed at step 6?

A 15

B 17

C 10

D 9

💡 Hint

Check the 'Sum Computed' column at step 6 in the execution_table.

At which step does the window start pointer first move to index 2?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Window Start' column in the execution_table to see when it changes to 2.

If the window size k was 2 instead of 3, how would the number of steps change?

A Fewer steps because windows are bigger

B More steps because more windows fit

C Same number of steps

D No steps because window size is invalid

💡 Hint

Consider how many subarrays of size k fit in the array length (6) and check execution_table for k=3.

Concept Snapshot

Sliding Window on Arrays:
- Use two pointers: start and end
- Expand end to grow window until size k
- Process window (e.g., sum elements)
- Slide window by moving start forward
- Repeat until end reaches array end
- Efficient for fixed-size subarray problems

Full Transcript

Sliding window on arrays uses two pointers to create a moving window over the array. We start with the window covering the first k elements. We calculate the sum of these elements. Then we slide the window forward by moving the start pointer one step and the end pointer one step, keeping the window size constant. We repeat this process until the end pointer reaches the last element of the array. This method helps efficiently process all subarrays of size k without recalculating sums from scratch each time.

Practice

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

easy

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

B. To sort the array in ascending order

C. To reverse the array elements

D. To find the maximum element in the entire array

Solution

1. Step 1: Understand sliding window concept

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

2. Step 2: Identify the main use

   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 A

4. Quick Check:

   Sliding window = efficient subarray processing [OK]

Hint: Sliding window avoids repeated work on overlapping subarrays [OK]

Common Mistakes:

• Thinking it sorts the array
• Assuming it reverses elements
• Confusing it with finding max of whole array

2. Which of the following is the correct syntax to initialize a sliding window sum for the first k elements in C?

easy

A. int sum = 0; for(int i = 1; i <= k; i++) sum += arr[i];

B. int sum = arr[0] + arr[k];

C. int sum = 0; for(int i = 0; i < k; i++) sum += arr[i];

D. int sum = arr[k]; for(int i = 0; i < k; i++) sum += arr[i];

Solution

1. Step 1: Check loop range for first k elements

   The loop should start at 0 and run while i < k to cover first k elements.

2. Step 2: Verify sum initialization and accumulation

   Sum starts at 0 and adds arr[i] for each i in 0 to k-1.

3. Final Answer:

   int sum = 0; for(int i = 0; i < k; i++) sum += arr[i]; -> Option C

4. Quick Check:

   Loop 0 to k-1 sums first k elements [OK]

Hint: Loop from 0 to k-1 to sum first k elements [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Adding arr[k] which is outside first k elements
• Initializing sum incorrectly

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

int arr[] = {1, 3, 2, 6, -1, 4, 1, 8, 2};
int 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 < 9; i++) {
    window_sum += arr[i] - arr[i - k];
    if(window_sum > max_sum) max_sum = window_sum;
}
printf("%d", max_sum);

medium

A. 18

B. 16

C. 17

D. 15

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 = 18

3. Final Answer:

   18 -> Option A

4. Quick Check:

   Max sliding window sum = 18 [OK]

Hint: Update sum by adding new and subtracting old element [OK]

Common Mistakes:

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

4. Identify the error in the following sliding window code snippet and choose the correct fix:

int arr[] = {2, 1, 5, 1, 3, 2};
int k = 3;
int window_sum = 0;
for(int i = 0; i <= k; i++) window_sum += arr[i];
for(int i = k; i < 6; i++) {
    window_sum += arr[i] - arr[i - k];
    printf("%d ", window_sum);
}

medium

A. No error, code is correct

B. Change loop condition to i < k in second for loop

C. Initialize window_sum to arr[0]

D. Change loop condition to i < k in first for loop

Solution

1. Step 1: Check first loop range for initial sum

   Loop runs i = 0 to i = k (inclusive), so 4 elements summed instead of 3.

2. Step 2: Fix loop condition to sum exactly k elements

   Change condition to i < k to sum first 3 elements only.

3. Final Answer:

   Change loop condition to i < k in first for loop -> Option D

4. Quick Check:

   Initial sum must cover exactly k elements [OK]

Hint: Use i < k to sum first k elements, not i <= k [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Changing wrong loop's condition
• Assuming initialization error

5. Given an array of integers and a window size k, how would you find the minimum sum of any contiguous subarray of size k using the sliding window technique?

hard

A. Sort the array and pick first k elements to sum

B. Initialize sum of first k elements, slide window updating sum and track minimum sum found

C. Use nested loops to check all subarrays and find minimum sum

D. Reverse the array and sum last k elements

Solution

1. Step 1: Calculate initial sum of first k elements

   Sum the first k elements to start the sliding window.

2. Step 2: Slide window across array updating sum and track minimum

   For each new element, add it and subtract the element leaving the window, update minimum sum if current sum is smaller.

3. Final Answer:

   Initialize sum of first k elements, slide window updating sum and track minimum sum found -> Option B

4. Quick Check:

   Sliding window tracks sums efficiently to find minimum [OK]

Hint: Track min sum by updating window sum while sliding [OK]

Common Mistakes:

• Sorting array instead of sliding window
• Using nested loops causing inefficiency
• Ignoring elements leaving the window