Sliding Window on Arrays in DSA Python

Mental Model

A sliding window moves over the array to look at a small part at a time, updating the result as it goes.

Analogy: Imagine looking through a small window on a long fence, moving it step by step to see different parts without stepping back.

Array: [1] [2] [3] [4] [5] [6] [7]
Window: ↑ -> -> (covers first 3 elements)

Dry Run Walkthrough

Input: array: [1, 3, 2, 5, 7, 2, 4], window size: 3

Goal: Find the maximum sum of any 3 consecutive elements

Step 1: Calculate sum of first window (first 3 elements)

Window covers [1, 3, 2], sum = 6

Why: We need a starting sum to compare with next windows

Step 2: Slide window right by 1: remove 1, add 5

Window covers [3, 2, 5], sum = 10

Why: Update sum efficiently without adding all elements again

Step 3: Slide window right by 1: remove 3, add 7

Window covers [2, 5, 7], sum = 14

Why: Keep updating sum to find max without full recalculation

Step 4: Slide window right by 1: remove 2, add 2

Window covers [5, 7, 2], sum = 14

Why: Check if new sum is max or equal max

Step 5: Slide window right by 1: remove 5, add 4

Window covers [7, 2, 4], sum = 13

Why: Final window sum to compare

Result:

Maximum sum is 14 from windows [2, 5, 7] and [5, 7, 2]

Annotated Code

DSA Python

class SlidingWindow:
    def max_sum_subarray(self, arr, k):
        if len(arr) < k or k == 0:
            return 0
        window_sum = sum(arr[:k])  # sum of first window
        max_sum = window_sum
        for i in range(k, len(arr)):
            window_sum += arr[i] - arr[i - k]  # slide window right
            if window_sum > max_sum:
                max_sum = window_sum
        return max_sum

# Driver code
arr = [1, 3, 2, 5, 7, 2, 4]
k = 3
sw = SlidingWindow()
print(sw.max_sum_subarray(arr, k))

window_sum = sum(arr[:k]) # sum of first window

Calculate initial sum of the first window

window_sum += arr[i] - arr[i - k] # slide window right

Update window sum by removing left element and adding new right element

if window_sum > max_sum: max_sum = window_sum

Keep track of maximum sum found so far

Output

14

Complexity Analysis

Time: O(n) because we visit each element once while sliding the window

Space: O(1) because we only store sums and counters, no extra array

vs Alternative: Naive approach sums each window fully in O(k) time, leading to O(n*k) total, which is slower

Edge Cases

Empty array or window size zero

Returns 0 immediately as no valid window exists

DSA Python

if len(arr) < k or k == 0:
    return 0

Window size equals array length

Returns sum of entire array as only one window exists

DSA Python

window_sum = sum(arr[:k])  # sum of first window

Window size larger than array length

Returns 0 because no window can be formed

DSA Python

if len(arr) < k or k == 0:
    return 0

When to Use This Pattern

When you need to find something about all subarrays of fixed size, use sliding window to avoid repeated work and improve efficiency.

Common Mistakes

Mistake: Recalculating the sum of the window from scratch every time instead of updating it
Fix: Update the sum by subtracting the element leaving the window and adding the new element entering

Summary

Finds max sum of any subarray of fixed size by moving a window over the array

Use when you need to analyze all subarrays of a fixed length efficiently

The key is to update the window sum by removing the left element and adding the right element instead of recalculating

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