Sliding Window

Problem

You are given an array of size N and an integer K.

Your task:
Find the maximum sum of any subarray of size exactly K

---

Understanding the Problem

Let’s take an example:

arr = [2, 1, 5, 1, 3, 2]
k = 3

Possible subarrays of size 3:

[2, 1, 5] → sum = 8
[1, 5, 1] → sum = 7
[5, 1, 3] → sum = 9
[1, 3, 2] → sum = 6

Answer = 9

---

Brute Force Thinking

A straightforward way:

• Pick every subarray of size k

• Calculate sum again and again

Time Complexity = O(n * k)

---

Key Observation

Look at how the window moves:

arr = [2, 1, 5, 1, 3, 2]

[2, 1, 5, 1, 3, 2]
 0  1  2  3  4  5 
 ↑     ↑

[2, 1, 5] → sum = 8  

[2, 1, 5, 1, 3, 2]
 0  1  2  3  4  5 
    ↑     ↑

[1, 5, 1] → sum = 8+1-2 = 7

Instead of recalculating everything:

• Remove 2

• Add 1

---

Sliding Window Idea

Don’t recompute the whole sum.
Just update it while moving forward.

---

Step-by-Step Dry Run

arr = [2, 1, 5, 1, 3, 2]
       0  1  2  3  4  5
        
window (size = 3)

Step 1

[2, 1, 5, 1, 3, 2]
 0  1  2  3  4  5 
 ↑     ↑

Window size = 3
Window elements: [2, 1, 5]
Sum = 8

Step 2

[2, 1, 5, 1, 3, 2]
 0  1  2  3  4  5 
    ↑     ↑

New window element : [1, 5, 1]

Add arr[3] = 1, Remove arr[0] = 2

Sum = 8 + 1 - 2 = 7

Step 3

[2, 1, 5, 1, 3, 2]
 0  1  2  3  4  5 
       ↑     ↑

New window element: [5, 1, 3]

Add arr[4] = 3, Remove arr[1] = 1

Sum = 7 + 3 - 1 = 9

Step 4

[2, 1, 5, 1, 3, 2]
 0  1  2  3  4  5 
          ↑     ↑

New window element: [1, 3, 2]

Add arr[5]=2, Remove arr[2]= 5

Sum = 9 + 2 - 5 = 6

---

Key Insight

At every step:

• Add the next element

• Remove the previous element

Constant work per step → O(n)

---

Code

sum = 0

// Step 1: Calculate sum of first window
for i from 0 to k-1:
    sum = sum + arr[i]

maximum = sum

// Step 2: Slide the window
for i from k to n-1:
    sum = sum + arr[i]        // add next element
    sum = sum - arr[i - k]    // remove previous element

    maximum = max(maximum, sum)

// Final answer
return maximum

---

Complexity

• Time Complexity: O(n)

• Space Complexity: O(1)