Sliding window technique in Data Structures Theory - Step-by-Step Execution

Concept Flow - Sliding window technique

Start with window at beginning

↓

Check window size or condition

↓

If condition met

→Process current window

↓

Slide window forward by moving start and/or end

↓

Repeat until end of data reached

↓

Stop

The sliding window technique moves a fixed or variable size window over data, processing each window efficiently by updating from the previous one.

Execution Sample

Data Structures Theory

arr = [1, 3, 2, 5, 1, 1, 2]
window_size = 3
for i in range(len(arr) - window_size + 1):
    window = arr[i:i+window_size]
    print(sum(window))

This code calculates the sum of every subarray of size 3 by sliding a window over the array.

Analysis Table

Step	Window Start Index	Window End Index	Window Elements	Sum of Window	Action
1	0	2	[1, 3, 2]	6	Calculate sum of first window
2	1	3	[3, 2, 5]	10	Slide window right by 1, calculate sum
3	2	4	[2, 5, 1]	8	Slide window right by 1, calculate sum
4	3	5	[5, 1, 1]	7	Slide window right by 1, calculate sum
5	4	6	[1, 1, 2]	4	Slide window right by 1, calculate sum
6	-	-	-	-	Reached end of array, stop

💡 Window end index reached the last element, no more windows possible.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
i	-	0	1	2	3	4	End
window	-	[1, 3, 2]	[3, 2, 5]	[2, 5, 1]	[5, 1, 1]	[1, 1, 2]	-
sum(window)	-	6	10	8	7	4	-

Key Insights - 3 Insights

Why do we stop when the window end index reaches the last element?

Because the window size is fixed, once the end index reaches the last element, we cannot form a full window beyond that point. See execution_table row 6.

Why do we slide the window by moving the start index forward?

Sliding the window forward means removing the first element and adding the next element after the current window. This keeps the window size constant and allows efficient processing. See execution_table rows 2-5.

Can the window size change during sliding?

Yes, in some problems the window size can vary based on conditions, but in this example it is fixed. Variable window sizes require adjusting start and end pointers carefully.

Visual Quiz - 3 Questions

Look at the execution_table, what is the sum of the window at step 3?

A 7

B 8

C 10

D 6

💡 Hint

Check the 'Sum of Window' column at step 3 in the execution_table.

At which step does the window first include the element '5'?

A Step 2

B Step 1

C Step 3

D Step 4

💡 Hint

Look at the 'Window Elements' column in execution_table rows to find when '5' appears.

If the window size was 2 instead of 3, how many steps would the loop run?

A 5

B 4

C 6

D 7

💡 Hint

Calculate len(arr) - window_size + 1 with window_size=2 and compare with execution_table step count.

Concept Snapshot

Sliding window technique:
- Move a window over data to process subarrays or substrings
- Window size can be fixed or variable
- Slide by moving start and/or end pointers
- Efficient for problems needing continuous segment analysis
- Avoids repeated full scans by reusing previous computations

Full Transcript

The sliding window technique involves moving a window of fixed or variable size over a data sequence. At each step, the window covers a subset of elements which can be processed efficiently. For example, summing elements inside the window can be done by updating the previous sum instead of recalculating fully. The window slides forward by moving its start and end positions, stopping when the window can no longer fit inside the data. This technique is useful for problems involving continuous segments like subarrays or substrings. The execution table shows how the window moves step-by-step, what elements it covers, and the sum calculated at each step. Key points include understanding when to stop sliding and how the window moves forward. This approach reduces repeated work and improves performance in many algorithms.

Practice

1. What is the main purpose of the sliding window technique in data processing?

easy

A. To efficiently process continuous segments of data without repeated work

B. To sort data in ascending order

C. To store data permanently in memory

D. To randomly access elements in a list

Solution

1. Step 1: Understand the sliding window concept

   The sliding window technique moves a fixed-size window over data to process parts efficiently.

2. Step 2: Identify the main goal

   It avoids repeated calculations by updating results as the window moves, improving efficiency.

3. Final Answer:

   To efficiently process continuous segments of data without repeated work -> Option A

4. Quick Check:

   Sliding window = efficient continuous data processing [OK]

Hint: Think of a moving window checking parts step-by-step [OK]

Common Mistakes:

• Confusing sliding window with sorting algorithms
• Thinking it stores data permanently
• Assuming it accesses data randomly

2. Which of the following is the correct way to initialize a sliding window of size 3 over a list arr in Python?

easy

A. window = arr{0:3}

B. window = arr(0,3)

C. window = arr[0:3]

D. window = arr[3]

Solution

1. Step 1: Recall Python slicing syntax

   Python uses square brackets and colon to slice lists: arr[start:end] extracts elements from start up to but not including end.

2. Step 2: Apply slicing for window size 3

   To get first 3 elements, use arr[0:3]. Other options use incorrect syntax.

3. Final Answer:

   window = arr[0:3] -> Option C

4. Quick Check:

   Python slice for first 3 elements = arr[0:3] [OK]

Hint: Remember Python slices use square brackets and colon [OK]

Common Mistakes:

• Using parentheses instead of brackets for slicing
• Using curly braces which are invalid for lists
• Accessing a single element instead of a slice

3. Consider the Python code below using sliding window to find the maximum sum of any 3 consecutive numbers in arr:

arr = [2, 1, 5, 1, 3, 2]
window_sum = sum(arr[0:3])
max_sum = window_sum
for i in range(3, len(arr)):
    window_sum += arr[i] - arr[i-3]
    if window_sum > max_sum:
        max_sum = window_sum
print(max_sum)

What is the output?

medium

A. 7

B. 8

C. 6

D. 9

Solution

1. Step 1: Calculate initial window sum

   Sum of first 3 elements: 2 + 1 + 5 = 8. Set max_sum = 8.

2. Step 2: Slide window and update sums

   i=3: window_sum = 8 + arr[3] - arr[0] = 8 + 1 - 2 = 7 (max_sum=8)
   i=4: window_sum = 7 + arr[4] - arr[1] = 7 + 3 - 1 = 9 (max_sum=9)
   i=5: window_sum = 9 + arr[5] - arr[2] = 9 + 2 - 5 = 6 (max_sum=9)

3. Final Answer:

   9 -> Option D

4. Quick Check:

   Max sum of 3 consecutive = 9 [OK]

Hint: Add new element, subtract old element to update sum [OK]

Common Mistakes:

• Recalculating sum of window each time instead of updating
• Mixing up indices when subtracting old element
• Not updating max_sum correctly

4. The following code attempts to find the minimum sum of any 2 consecutive numbers in arr using sliding window:

arr = [4, 3, 7, 1, 2]
window_sum = arr[0] + arr[1]
min_sum = window_sum
for i in range(2, len(arr)):
    window_sum = window_sum + arr[i] - arr[i-1]
    if window_sum < min_sum:
        min_sum = window_sum
print(min_sum)

What is the error in this code?

medium

A. The window size is incorrectly handled in subtraction index

B. The loop range should start from 1, not 2

C. The initial window sum is calculated incorrectly

D. The comparison operator in if statement is wrong

Solution

1. Step 1: Analyze window size and indices

   The window size is 2. When sliding to include arr[i], subtract the leaving element arr[i-2].

2. Step 2: Identify the error

   Code subtracts arr[i-1], but should subtract arr[i-2]. arr[i-1] remains in the window.

3. Step 3: Verify with trace

   i=2: should be 7 + 7 - 4 = 10, but code 7 + 7 - 3 = 11 (wrong).

4. Final Answer:

   The window size is incorrectly handled in subtraction index -> Option A

5. Quick Check:

   For size k=2, subtract arr[i-k] [OK]

Hint: Check subtraction index matches window size [OK]

Common Mistakes:

• Using wrong index for element leaving the window
• Starting loop at wrong index
• Incorrect initial sum calculation

5. You want to find the longest substring of a string s that contains at most 2 distinct characters using the sliding window technique. Which approach correctly applies the sliding window here?

hard

A. Fix window size to 2 and slide over the string

B. Expand the window by moving right pointer, shrink from left when distinct chars exceed 2

C. Count total distinct characters in the string once and return that count

D. Use nested loops to check all substrings of length 2

Solution

1. Step 1: Understand problem requirements

   We want the longest substring with at most 2 distinct characters, so window size is variable.

2. Step 2: Apply sliding window logic

   Expand window by moving right pointer. If distinct chars exceed 2, shrink window from left until condition holds.

3. Step 3: Evaluate options

   Expand the window by moving right pointer, shrink from left when distinct chars exceed 2 matches this approach. Fix window size to 2 and slide over the string fixes window size incorrectly. Options C and D do not use sliding window properly.

4. Final Answer:

   Expand the window by moving right pointer, shrink from left when distinct chars exceed 2 -> Option B

5. Quick Check:

   Variable window size with condition check = Expand the window by moving right pointer, shrink from left when distinct chars exceed 2 [OK]

Hint: Adjust window size dynamically based on distinct chars count [OK]

Common Mistakes:

• Fixing window size instead of adjusting dynamically
• Not shrinking window when condition breaks
• Using brute force nested loops instead of sliding window