🪟 Sliding Window Technique

Intermediate ~12 min read

You need to find the maximum sum of 3 consecutive elements in an array. The naive approach recalculates the sum for each window - that's wasteful! Sliding window reuses the previous sum by subtracting the left element and adding the right. Let's see how.

The Problem: Maximum Sum Subarray

Given an array, find the maximum sum of k consecutive elements.

Example

Array: [2, 1, 5, 1, 3, 2]
k = 3

Windows:
[2, 1, 5] = 8
[1, 5, 1] = 7
[5, 1, 3] = 9  ← Maximum!
[1, 3, 2] = 6

Naive: Recalculate each sum → O(n×k)

Sliding window: Reuse previous sum → O(n)

How Sliding Window Works

Instead of recalculating the entire sum, slide the window by removing the leftmost element and adding the next element.

The Algorithm (Fixed Window)

Calculate sum of first k elements
For each new element:
- Subtract the element leaving the window
- Add the element entering the window
Track the maximum sum

window_sum = window_sum - arr[i-k] + arr[i]

# Sliding Window Technique
# Find optimal subarrays efficiently

print("=== Problem: Maximum Sum Subarray ===")
print("Find the maximum sum of k consecutive elements\n")

def max_sum_naive(arr, k):
    """Naive: Recalculate sum for each window - O(n*k)"""
    n = len(arr)
    max_sum = float('-inf')
    operations = 0
    
    for i in range(n - k + 1):
        window_sum = 0
        for j in range(i, i + k):
            window_sum += arr[j]
            operations += 1
        max_sum = max(max_sum, window_sum)
    
    return max_sum, operations

def max_sum_sliding_window(arr, k):
    """Sliding window: Reuse previous sum - O(n)"""
    n = len(arr)
    
    # Calculate first window
    window_sum = sum(arr[:k])
    max_sum = window_sum
    operations = k
    
    # Slide the window
    for i in range(k, n):
        # Remove left element, add right element
        window_sum = window_sum - arr[i - k] + arr[i]
        max_sum = max(max_sum, window_sum)
        operations += 2  # One subtraction, one addition
    
    return max_sum, operations

# Test
arr = [2, 1, 5, 1, 3, 2, 4, 6, 8]
k = 3

print(f"Array: {arr}")
print(f"Window size: {k}\n")

result, ops = max_sum_naive(arr, k)
print(f"❌ Naive O(n*k): Max sum = {result}, Operations = {ops}")

result, ops = max_sum_sliding_window(arr, k)
print(f"✅ Sliding Window O(n): Max sum = {result}, Operations = {ops}\n")

print("=== The Pattern ===")
print("1. Calculate sum of first window")
print("2. Slide: Remove leftmost, add rightmost")
print("3. Update max/min as you go")
print("4. Result: O(n) instead of O(n*k)!")

print("\n=== Variable Window: Longest Substring ===")
print("Find longest substring with at most k distinct characters\n")

def longest_substring_k_distinct(s, k):
    """Variable-size sliding window"""
    char_count = {}
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        # Expand window
        char_count[s[right]] = char_count.get(s[right], 0) + 1
        
        # Shrink window if too many distinct chars
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
        
        # Update max
        max_length = max(max_length, right - left + 1)
    
    return max_length

s = "araaci"
k = 2
result = longest_substring_k_distinct(s, k)
print(f"String: '{s}'")
print(f"Max {k} distinct chars: {result} (substring: 'araa')")
print("✅ Variable window adjusts size dynamically!")

Output

Click Run to execute your code

Why it's faster:

Naive: Recalculate k elements for each window → O(n×k)
Sliding: Just 2 operations per window → O(n)
For k=100, n=1000: 100,000 ops vs 2,000 ops!

Quick Quiz

Why is it called "sliding" window?

Show answer
Because the window "slides" one position at a time, removing the left element and adding the right element - like sliding a physical window frame!
What's the space complexity?

Show answer
O(1) - we only store the current window sum and max, regardless of array size!

Two Types of Windows

# Sliding Window Patterns
# Fixed vs Variable window sizes

print("=== Pattern 1: Fixed Window Size ===")
print("Window size is constant\n")

def max_average_subarray(arr, k):
    """Find subarray with maximum average"""
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    for i in range(k, len(arr)):
        window_sum = window_sum - arr[i - k] + arr[i]
        max_sum = max(max_sum, window_sum)
    
    return max_sum / k

arr = [1, 12, -5, -6, 50, 3]
k = 4
print(f"Array: {arr}")
print(f"Max average of {k} elements: {max_average_subarray(arr, k):.1f}\n")

print("=== Pattern 2: Variable Window Size ===")
print("Window grows/shrinks based on condition\n")

def min_subarray_sum(arr, target):
    """Smallest subarray with sum >= target"""
    min_length = float('inf')
    window_sum = 0
    left = 0
    
    for right in range(len(arr)):
        window_sum += arr[right]
        
        # Shrink window while condition met
        while window_sum >= target:
            min_length = min(min_length, right - left + 1)
            window_sum -= arr[left]
            left += 1
    
    return min_length if min_length != float('inf') else 0

arr = [2, 3, 1, 2, 4, 3]
target = 7
print(f"Array: {arr}")
print(f"Smallest subarray with sum >= {target}: length {min_subarray_sum(arr, target)}\n")

print("=== Pattern 3: String Window (Character Frequency) ===")
print("Track character counts in window\n")

def longest_substring_without_repeating(s):
    """Longest substring with unique characters"""
    char_index = {}
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        if s[right] in char_index and char_index[s[right]] >= left:
            # Move left past the duplicate
            left = char_index[s[right]] + 1
        
        char_index[s[right]] = right
        max_length = max(max_length, right - left + 1)
    
    return max_length

s = "abcabcbb"
print(f"String: '{s}'")
print(f"Longest unique substring: {longest_substring_without_repeating(s)} ('abc')\n")

print("=== When to Use Sliding Window ===")
print("✅ Finding optimal subarray/substring")
print("✅ Contiguous elements with a condition")
print("✅ Can be fixed or variable size")
print("✅ Always O(n) time!")

Output

Click Run to execute your code

Type	Window Size	When to Use	Example
Fixed Window	Constant (k)	Find optimal k-sized subarray	Max sum of k elements
Variable Window	Grows/shrinks	Find optimal size based on condition	Longest substring with k distinct chars

When to Use Sliding Window

✅ Use Sliding Window When:

Finding optimal contiguous subarray/substring
Problem asks for "maximum/minimum of k elements"
Problem asks for "longest/shortest substring with condition"
Elements must be consecutive (no gaps)

❌ Don't Use When:

Elements don't need to be contiguous
Need to find pairs/triplets (use two pointers)
Need all subarrays (not just optimal one)

Common Mistakes

❌ Forgetting to Initialize Window

# Wrong: Starting from index k
for i in range(k, len(arr)):
    window_sum = window_sum - arr[i-k] + arr[i]
# window_sum is undefined!

# Right: Calculate first window
window_sum = sum(arr[:k])
for i in range(k, len(arr)):
    window_sum = window_sum - arr[i-k] + arr[i]

❌ Wrong Index for Removal

# Wrong
window_sum = window_sum - arr[i] + arr[i+k]

# Right: Remove element k positions back
window_sum = window_sum - arr[i-k] + arr[i]

Summary

The 3-Point Sliding Window Guide

Pattern: Reuse previous calculation by sliding the window
Complexity: O(n) time, O(1) space - much better than O(n×k)
Types: Fixed size (constant k) or variable size (dynamic)

Interview tip: When you see "contiguous subarray" or "substring", think sliding window!

What's Next?

You've mastered array techniques! Next: String Manipulation - learn string operations, pattern matching, and how to apply sliding window to string problems.

Practice: Try "Longest Substring Without Repeating Characters" - it combines sliding window with a hash map!

Previous Two Pointers

Next String Manipulation