DSA — Sliding Window

What is Sliding Window?

A technique that maintains a window of elements and slides it across the data.

Fixed Window

def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

Variable Window

def min_subarray_len(target, arr):
    left = 0
    current_sum = 0
    min_length = float('inf')
    
    for right in range(len(arr)):
        current_sum += arr[right]
        
        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            current_sum -= arr[left]
            left += 1
    
    return min_length if min_length != float('inf') else 0

Longest Substring Without Repeating

def length_of_longest_substring(s):
    char_map = {}
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        if s[right] in char_map:
            left = max(left, char_map[s[right]] + 1)
        char_map[s[right]] = right
        max_length = max(max_length, right - left + 1)
    
    return max_length

When to Use

Pattern	Example
Fixed window	Max sum of k elements
Variable window	Minimum window substring
Sliding with condition	Longest substring with k distinct

Mini Practice

1. Find max sum subarray
2. Minimum window substring
3. Longest substring without repeats
4. Maximum of all subarrays of size k

Up Next

Continue with Two Pointers — two pointer technique.