Sliding Window on Arrays in DSA Python - Execution Trace

Concept Flow - Sliding Window on Arrays

Initialize window start and end pointers

↓

Expand window by moving end pointer

↓

Check window size or condition

↓

Process window

↓

Slide window by moving start pointer

↓

Repeat until end reaches array end

Start with a window covering part of the array, expand it by moving the end pointer, process when window size or condition is met, then slide the window forward by moving the start pointer, repeat until the end reaches the array's end.

Execution Sample

DSA Python

arr = [1, 3, 2, 5, 7, 2]
window_size = 3
start = 0
for end in range(len(arr)):
    if end - start + 1 == window_size:
        print(arr[start:end+1])
        start += 1

Prints all subarrays of size 3 using a sliding window.

Execution Table

Step	Operation	start	end	Window Elements	Action	Visual State
1	Initialize start=0, end=0	0	0	[1]	Window size < 3, expand end	Window: [1]
2	Move end to 1	0	1	[1, 3]	Window size < 3, expand end	Window: [1, 3]
3	Move end to 2	0	2	[1, 3, 2]	Window size == 3, print and slide start	Window: [1, 3, 2]
4	Slide start to 1	1	2	[3, 2]	Prepare for next window	Window: [3, 2]
5	Move end to 3	1	3	[3, 2, 5]	Window size == 3, print and slide start	Window: [3, 2, 5]
6	Slide start to 2	2	3	[2, 5]	Prepare for next window	Window: [2, 5]
7	Move end to 4	2	4	[2, 5, 7]	Window size == 3, print and slide start	Window: [2, 5, 7]
8	Slide start to 3	3	4	[5, 7]	Prepare for next window	Window: [5, 7]
9	Move end to 5	3	5	[5, 7, 2]	Window size == 3, print and slide start	Window: [5, 7, 2]
10	Slide start to 4	4	5	[7, 2]	End reached, stop	Window: [7, 2]

💡 End pointer reached the last element, no more full windows of size 3

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
start	0	0	0	0	1	1	2	2	3	3	4
end	0	0	1	2	2	3	3	4	4	5	5
window_elements	[1]	[1]	[1,3]	[1,3,2]	[3,2]	[3,2,5]	[2,5]	[2,5,7]	[5,7]	[5,7,2]	[7,2]

Key Moments - 3 Insights

Why do we check if window size equals the target size before processing?

Because only when the window size matches the target (3 here) do we have a complete subarray to process, as shown in steps 3, 5, 7, and 9 in the execution_table.

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

Moving the start pointer slides the window forward to consider the next subarray, which is why after printing the window at steps 3, 5, 7, and 9, start is incremented in the next step.

What happens when the end pointer reaches the last element?

When end reaches the last element (step 10), we cannot form a new full window of the target size, so the process stops, as noted in the exit_note.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what are the elements in the window?

A [3, 2, 5]

B [2, 5, 7]

C [1, 3, 2]

D [5, 7, 2]

💡 Hint

Check the 'Window Elements' column at step 3 in the execution_table.

At which step does the start pointer first move from 0 to 1?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look at the 'start' variable in variable_tracker after each step.

If the window size was 2 instead of 3, how would the action at step 3 change?

A Window would never be processed

B Window would be processed and start moved earlier, at step 2

C Window would be processed at step 3 as before

D Start pointer would not move

💡 Hint

Think about when the window size condition is met for size 2 compared to size 3.

Concept Snapshot

Sliding Window on Arrays:
- Use two pointers: start and end
- Expand end to grow window
- When window size matches target, process window
- Slide start to move window forward
- Repeat until end reaches array end

Full Transcript

Sliding window on arrays uses two pointers to create a moving window over the array. We start both pointers at the beginning. We move the end pointer to expand the window. When the window size equals the target size, we process the window (like printing the elements). Then we move the start pointer forward to slide the window. This repeats until the end pointer reaches the last element. This method efficiently processes all subarrays of a fixed size without re-examining elements unnecessarily.

Practice

1. What does the sliding window technique help to optimize when working with arrays?

easy

A. It reduces the time complexity by avoiding repeated calculations over overlapping subarrays.

B. It sorts the array in ascending order.

C. It finds the maximum element in the entire array.

D. It reverses the array elements.

Solution

1. Step 1: Understand the sliding window purpose

   The sliding window technique moves a fixed-size window over the array to process elements efficiently without recalculating everything each time.

2. Step 2: Identify what it optimizes

   It avoids repeated work on overlapping parts of the array, thus reducing time complexity compared to naive methods.

3. Final Answer:

   It reduces the time complexity by avoiding repeated calculations over overlapping subarrays. -> Option A

4. Quick Check:

   Sliding window = avoids repeated calculations [OK]

Hint: Sliding window avoids redoing work on overlapping parts [OK]

Common Mistakes:

• Thinking it sorts the array
• Assuming it finds max element always
• Confusing it with reversing arrays

2. Which of the following is the correct syntax to initialize a sliding window sum for the first 3 elements of an array arr in Python?

easy

A. window_sum = sum(arr[0:3])

B. window_sum = sum(arr[1:4])

C. window_sum = sum(arr[0:2])

D. window_sum = sum(arr[3:6])

Solution

1. Step 1: Identify the first 3 elements slice

   The first 3 elements are at indices 0, 1, and 2, so the slice is arr[0:3] because the end index is exclusive.

2. Step 2: Use sum function on correct slice

   sum(arr[0:3]) correctly sums elements at indices 0, 1, and 2.

3. Final Answer:

   window_sum = sum(arr[0:3]) -> Option A

4. Quick Check:

   sum(arr[0:3]) sums first 3 elements [OK]

Hint: Remember Python slices exclude the end index [OK]

Common Mistakes:

• Using wrong slice indices like arr[1:4]
• Using arr[0:2] which misses the third element
• Using arr[3:6] which skips first elements

3. What is the output of the following code?

arr = [2, 1, 5, 1, 3, 2]
window_size = 3
window_sum = sum(arr[0:3])
result = [window_sum]
for i in range(3, len(arr)):
    window_sum += arr[i] - arr[i - window_size]
    result.append(window_sum)
print(result)

medium

A. [2, 1, 5, 1]

B. [8, 9, 7, 6]

C. [8, 7, 9, 6]

D. [6, 7, 8, 9]

Solution

1. Step 1: Calculate initial window sum

   sum(arr[0:3]) = 2 + 1 + 5 = 8, so result starts as [8].

2. Step 2: Slide window and update sums

   i=3: window_sum = 8 + arr[3] - arr[0] = 8 + 1 - 2 = 7; result = [8,7] i=4: window_sum = 7 + arr[4] - arr[1] = 7 + 3 - 1 = 9; result = [8,7,9] i=5: window_sum = 9 + arr[5] - arr[2] = 9 + 2 - 5 = 6; result = [8,7,9,6]

3. Final Answer:

   [8, 7, 9, 6] -> Option C

4. Quick Check:

   Sliding sums = [8,7,9,6] [OK]

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

Common Mistakes:

• Not subtracting the element leaving the window
• Incorrect initial sum calculation
• Appending wrong values to result

4. Find the error in the following sliding window code that calculates sums of windows of size 2:

arr = [4, 3, 2, 1]
window_size = 2
window_sum = sum(arr[0:window_size])
result = [window_sum]
for i in range(window_size, len(arr)):
    window_sum = window_sum + arr[i] + arr[i - window_size]
    result.append(window_sum)
print(result)

medium

A. The loop range should start from 0, not window_size.

B. The window_sum update should subtract arr[i - window_size], not add it.

C. The initial window_sum calculation is incorrect.

D. The result list should be initialized as empty.

Solution

1. Step 1: Analyze window_sum update

   The code adds both arr[i] and arr[i - window_size], but it should add the new element and subtract the element leaving the window.

2. Step 2: Correct the update formula

   Change window_sum = window_sum + arr[i] + arr[i - window_size] to window_sum = window_sum + arr[i] - arr[i - window_size].

3. Final Answer:

   The window_sum update should subtract arr[i - window_size], not add it. -> Option B

4. Quick Check:

   Subtract leaving element, not add [OK]

Hint: Subtract old element leaving window, add new element [OK]

Common Mistakes:

• Adding both new and old elements instead of subtracting old
• Wrong loop start index
• Incorrect initial sum

5. Given an array arr = [1, 3, 2, 6, -1, 4, 1, 8, 2] and window size 5, which sliding window sum is the maximum?
Use the sliding window technique to find the maximum sum of any 5 consecutive elements.

hard

A. 16

B. 19

C. 17

D. 18

Solution

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

   sum(arr[0:5]) = 1 + 3 + 2 + 6 + (-1) = 11

2. Step 2: Slide window and update sums, track max

   i=5: sum = 11 + 4 - 1 = 14 (max=14) i=6: sum = 14 + 1 - 3 = 12 (max=14) i=7: sum = 12 + 8 - 2 = 18 (max=18) i=8: sum = 18 + 2 - 6 = 14 (max=18)

3. Final Answer:

   18 -> Option D

4. Quick Check:

   Max sliding sum = 18 [OK]

Hint: Track max while sliding window sums update [OK]

Common Mistakes:

• Not updating max after each slide
• Wrong initial sum calculation
• Forgetting to subtract element leaving window