Sliding Window on Arrays in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the sliding window technique in arrays?

It is a method to create a 'window' of fixed size that moves over the array to solve problems efficiently by avoiding repeated work.

beginner

Why is sliding window better than nested loops for some problems?

Because it reduces time complexity by reusing previous computations instead of recalculating for every new window, often changing O(n*k) to O(n).

beginner

In sliding window, what happens when the window moves forward?

The element leaving the window is removed from the current calculation, and the new element entering the window is added.

intermediate

How do you find the maximum sum of any subarray of size k using sliding window?

1. Calculate sum of first k elements.
2. Slide the window by one element at a time:
- Subtract element leaving window
- Add element entering window
3. Track the maximum sum found.

beginner

What is a common real-life example to understand sliding window?

Imagine looking through a fixed-size window on a moving train to see parts of the scenery. You only focus on what is inside the window as it moves forward.

What does the sliding window technique help to avoid?

A Recalculating values for overlapping parts of the array

B Sorting the array multiple times

C Using extra memory for storing all subarrays

D Ignoring elements outside the window

Sliding window avoids recalculating values for overlapping parts by updating the result incrementally.

If you want to find the average of every subarray of size 3, what is the first step?

A Sort the array

B Calculate sum of first 3 elements

C Find the maximum element

D Reverse the array

You start by calculating the sum of the first 3 elements to form the initial window.

When sliding the window forward by one element, what do you do?

A Add the new element and subtract the old element leaving the window

B Add both new and old elements

C Subtract both new and old elements

D Ignore the new element

You add the new element entering the window and subtract the element leaving to update the sum efficiently.

What is the time complexity of sliding window for fixed size k over an array of size n?

A O(n^2)

B O(n*k)

C O(n)

D O(k)

Sliding window processes each element once, resulting in O(n) time complexity.

Which problem is best suited for sliding window?

A Binary search in sorted array

B Sorting an array

C Finding shortest path in graph

D Finding max sum of subarrays of fixed size

Sliding window is ideal for problems involving fixed-size subarrays like max sum.

Explain how the sliding window technique works on arrays with an example.

Think about moving a fixed-size window over the array and updating sums.

Describe the benefits of using sliding window over nested loops for subarray problems.

Focus on how sliding window reduces repeated calculations.

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