Sliding Window Technique

Definition

The Sliding Window technique is used to perform operations on a specific “window” size of an array or string. Instead of recalculating the entire window every time, you “slide” it by one position: add the new element entering the window and remove the old element leaving it.

How it Works

1. Create Window: Start with the first K elements.
2. Slide: To move to the next position, subtract the element that just fell out of the left side and add the element entering the right side.
3. Benefit: This avoids nested loops.

Real-World Analogy

Train Windows: Imagine a long train passing by. You have a window frame that allows you to see exactly 3 train cars at a time. As the train moves, you don’t look at a completely new set of cars; you just see one new car appear on the right, and one old car disappear on the left.

Example

Problem: Find the maximum sum of any contiguous subarray of size $k=3$. Array: [2, 1, 5, 1, 3, 2]

• Window 1: [2, 1, 5] Sum = 8.
• Slide: Remove 2, Add 1. New Window [1, 5, 1] Sum = 7.
• Slide: Remove 1, Add 3. New Window [5, 1, 3] Sum = 9. (Max)

Code Example (Python)

def max_sum_subarray(arr, k):
    # Calculate sum of first window
    max_sum = current_sum = sum(arr[:k])
   
    # Slide the window
    for i in range(len(arr) - k):
        # Subtract element leaving, add element entering
        current_sum = current_sum - arr[i] + arr[i+k]
        max_sum = max(max_sum, current_sum)
       
    return max_sum

print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3)) # Output: 9

Complexity Analysis

• Time Complexity: O(N). We pass through the array once. (Brute force would be O(N times K)).
• Space Complexity: O(1).

Use Cases

• String Problems: Finding the longest substring without repeating characters.
• Analytics: Moving averages (e.g., “average stock price over the last 30 days”).