# 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:

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

Possible subarrays of size 3:

```plaintext
[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:

```plaintext
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**

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

**Step 1**

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

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

**Step 2**

```plaintext
[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**

```plaintext
[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**

```plaintext
[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

```javascript
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)`