Day 12 – Sliding Window

Master the art of efficient array and string processing using the sliding window technique. Learn to solve subarray and substring problems in linear time.

🎯 When to use: Contiguous subarrays/substrings 🪟 Fixed vs Variable window sizes ⚡ Time: O(n), Space: O(k) typically

Learning Objectives

Identify when Sliding Window pattern applies to a problem
Implement both fixed-size and variable-size window solutions
Use frequency maps and expand/contract patterns effectively
Analyze time and space complexity correctly
Avoid common implementation pitfalls and edge cases

Visual Intuition

Fixed Window Moving Across Array

Variable Window Expanding/Contracting

Core Concepts

What is a Sliding Window?

A sliding window is a technique where we maintain a subarray or substring that "slides" through the data structure. Instead of checking every possible subarray (O(n²)), we efficiently expand and contract our window in one pass (O(n)).

Fixed-Size Windows

The window size remains constant throughout the algorithm. Common for problems asking for:

Maximum sum of subarray of size k
Average of subarrays of size k
First negative number in every window of size k

Variable-Size Windows

The window size changes based on conditions. Used for problems like:

Longest substring without repeating characters
Smallest subarray with sum ≥ target
Longest subarray with at most k distinct elements

Two Pointers vs Sliding Window

Two Pointers	Sliding Window
Can start from ends (left=0, right=n-1)	Usually starts from beginning (left=right=0)
Pointers can move independently	Window maintains contiguous elements
Used for sorted arrays, palindromes	Used for subarrays, substrings

Expand/Contract Template

Pseudocode Pattern:
1. Initialize left = 0, right = 0
2. Expand right pointer, add element to window
3. While window violates condition: contract from left
4. Update answer with current valid window
5. Repeat until right reaches end

Step-by-Step Templates

Fixed-Size Window Template

def fixed_window_template(arr, k):
    if len(arr) < k:
        return []
    
    # Calculate sum of first window
    window_sum = sum(arr[:k])
    result = [window_sum]
    
    # Slide the window
    for i in range(k, len(arr)):
        # Remove leftmost element, add rightmost
        window_sum = window_sum - arr[i-k] + arr[i]
        result.append(window_sum)
    
    return result

function fixedWindowTemplate(arr, k) {
    if (arr.length < k) return [];
    
    // Calculate sum of first window
    let windowSum = arr.slice(0, k).reduce((a, b) => a + b, 0);
    const result = [windowSum];
    
    // Slide the window
    for (let i = k; i < arr.length; i++) {
        // Remove leftmost element, add rightmost
        windowSum = windowSum - arr[i - k] + arr[i];
        result.push(windowSum);
    }
    
    return result;
}

Variable-Size Window Template

def variable_window_template(arr, condition):
    left = 0
    result = 0  # or float('inf') for minimum problems
    window_state = {}  # frequency map or other state
    
    for right in range(len(arr)):
        # Expand: add arr[right] to window
        # Update window_state
        
        # Contract: while window violates condition
        while condition_violated(window_state):
            # Remove arr[left] from window
            # Update window_state
            left += 1
        
        # Update result with current valid window
        result = max(result, right - left + 1)
    
    return result

function variableWindowTemplate(arr, condition) {
    let left = 0;
    let result = 0; // or Infinity for minimum problems
    const windowState = new Map(); // frequency map or other state
    
    for (let right = 0; right < arr.length; right++) {
        // Expand: add arr[right] to window
        // Update windowState
        
        // Contract: while window violates condition
        while (conditionViolated(windowState)) {
            // Remove arr[left] from window
            // Update windowState
            left++;
        }
        
        // Update result with current valid window
        result = Math.max(result, right - left + 1);
    }
    
    return result;
}

Binary Array with K Flips Pattern

def longest_ones_after_k_flips(nums, k):
    left = 0
    zero_count = 0
    max_length = 0
    
    for right in range(len(nums)):
        # Expand: add nums[right] to window
        if nums[right] == 0:
            zero_count += 1
        
        # Contract: while we have more than k zeros
        while zero_count > k:
            if nums[left] == 0:
                zero_count -= 1
            left += 1
        
        # Update result
        max_length = max(max_length, right - left + 1)
    
    return max_length

function longestOnesAfterKFlips(nums, k) {
    let left = 0;
    let zeroCount = 0;
    let maxLength = 0;
    
    for (let right = 0; right < nums.length; right++) {
        // Expand: add nums[right] to window
        if (nums[right] === 0) {
            zeroCount++;
        }
        
        // Contract: while we have more than k zeros
        while (zeroCount > k) {
            if (nums[left] === 0) {
                zeroCount--;
            }
            left++;
        }
        
        // Update result
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

Product-Based Window Pattern

def subarray_product_less_than_k(nums, k):
    if k <= 1:
        return 0
    
    left = 0
    product = 1
    count = 0
    
    for right in range(len(nums)):
        # Expand: multiply by nums[right]
        product *= nums[right]
        
        # Contract: while product >= k
        while product >= k:
            product //= nums[left]
            left += 1
        
        # Count subarrays ending at 'right'
        count += right - left + 1
    
    return count

function subarrayProductLessThanK(nums, k) {
    if (k <= 1) return 0;
    
    let left = 0;
    let product = 1;
    let count = 0;
    
    for (let right = 0; right < nums.length; right++) {
        // Expand: multiply by nums[right]
        product *= nums[right];
        
        // Contract: while product >= k
        while (product >= k) {
            product /= nums[left];
            left++;
        }
        
        // Count subarrays ending at 'right'
        count += right - left + 1;
    }
    
    return count;
}

Dry Runs

Max Sum Subarray of Size K=3

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

Step	Window	Sum	Max Sum
1	[2, 1, 5]	8	8
2	[1, 5, 1]	7	8
3	[5, 1, 3]	9	9
4	[1, 3, 2]	6	9

Longest Substring Without Repeats

String: "abcabcbb"

Right	Char	Window	Action	Max Length
0	a	"a"	Expand	1
1	b	"ab"	Expand	2
2	c	"abc"	Expand	3
3	a	"bca"	Contract left to 1, then expand	3
4	b	"cab"	Contract left to 2, then expand	3

Worked Examples

1. Max Sum Subarray of Size K

Problem: Find the maximum sum of any contiguous subarray of size k.

Approach: Use fixed window sliding technique. Calculate sum of first k elements, then slide window by removing leftmost and adding rightmost element.

Complexity: Time O(n), Space O(1)

def max_sum_subarray(arr, k):
    if len(arr) < k:
        return 0
    
    # Sum of first window
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Slide the window
    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

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

function maxSumSubarray(arr, k) {
    if (arr.length < k) return 0;
    
    // Sum of first window
    let windowSum = arr.slice(0, k).reduce((a, b) => a + b, 0);
    let maxSum = windowSum;
    
    // Slide the window
    for (let i = k; i < arr.length; i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        maxSum = Math.max(maxSum, windowSum);
    }
    
    return maxSum;
}

// Example usage
console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // Output: 9

2. Longest Substring Without Repeating Characters

Problem: Find the length of the longest substring without repeating characters.

Approach: Use variable window with set/map to track characters. Expand window and contract when duplicate found.

Complexity: Time O(n), Space O(min(m,n)) where m is charset size

def length_of_longest_substring(s):
    char_set = set()
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        # Contract window until no duplicates
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        
        # Add current character and update max length
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)
    
    return max_length

# Example usage
print(length_of_longest_substring("abcabcbb"))  # Output: 3

function lengthOfLongestSubstring(s) {
    const charSet = new Set();
    let left = 0;
    let maxLength = 0;
    
    for (let right = 0; right < s.length; right++) {
        // Contract window until no duplicates
        while (charSet.has(s[right])) {
            charSet.delete(s[left]);
            left++;
        }
        
        // Add current character and update max length
        charSet.add(s[right]);
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

// Example usage
console.log(lengthOfLongestSubstring("abcabcbb")); // Output: 3

3. Minimum Window Substring

Problem: Find the minimum window in string s that contains all characters of string t.

Approach: Use frequency maps to track needed characters. Expand to find valid window, then contract to minimize.

Complexity: Time O(|s| + |t|), Space O(|s| + |t|)

def min_window_substring(s, t):
    if not s or not t:
        return ""
    
    # Frequency map for characters in t
    need = {}
    for char in t:
        need[char] = need.get(char, 0) + 1
    
    left = 0
    need_met = 0  # Number of unique chars in t satisfied
    have = {}     # Frequency map for current window
    
    min_len = float('inf')
    min_start = 0
    
    for right in range(len(s)):
        char = s[right]
        have[char] = have.get(char, 0) + 1
        
        # Check if frequency requirement is met for this char
        if char in need and have[char] == need[char]:
            need_met += 1
        
        # Contract window when all requirements met
        while need_met == len(need):
            # Update minimum window if current is smaller
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_start = left
            
            # Remove leftmost character
            left_char = s[left]
            have[left_char] -= 1
            if left_char in need and have[left_char] < need[left_char]:
                need_met -= 1
            left += 1
    
    return s[min_start:min_start + min_len] if min_len != float('inf') else ""

# Example usage
print(min_window_substring("ADOBECODEBANC", "ABC"))  # Output: "BANC"

function minWindowSubstring(s, t) {
    if (!s || !t) return "";
    
    // Frequency map for characters in t
    const need = new Map();
    for (const char of t) {
        need.set(char, (need.get(char) || 0) + 1);
    }
    
    let left = 0;
    let needMet = 0; // Number of unique chars in t satisfied
    const have = new Map(); // Frequency map for current window
    
    let minLen = Infinity;
    let minStart = 0;
    
    for (let right = 0; right < s.length; right++) {
        const char = s[right];
        have.set(char, (have.get(char) || 0) + 1);
        
        // Check if frequency requirement is met for this char
        if (need.has(char) && have.get(char) === need.get(char)) {
            needMet++;
        }
        
        // Contract window when all requirements met
        while (needMet === need.size) {
            // Update minimum window if current is smaller
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }
            
            // Remove leftmost character
            const leftChar = s[left];
            have.set(leftChar, have.get(leftChar) - 1);
            if (need.has(leftChar) && have.get(leftChar) < need.get(leftChar)) {
                needMet--;
            }
            left++;
        }
    }
    
    return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
}

// Example usage
console.log(minWindowSubstring("ADOBECODEBANC", "ABC")); // Output: "BANC"

4. Fruit Into Baskets (Longest Subarray with At Most 2 Distinct)

Problem: Find the longest subarray with at most 2 distinct elements.

Approach: Use variable window with frequency map. Contract when more than 2 distinct elements.

def fruit_into_baskets(fruits):
    left = 0
    fruit_count = {}
    max_length = 0
    
    for right in range(len(fruits)):
        # Add fruit to basket
        fruit = fruits[right]
        fruit_count[fruit] = fruit_count.get(fruit, 0) + 1
        
        # Contract window if more than 2 fruit types
        while len(fruit_count) > 2:
            left_fruit = fruits[left]
            fruit_count[left_fruit] -= 1
            if fruit_count[left_fruit] == 0:
                del fruit_count[left_fruit]
            left += 1
        
        # Update max length
        max_length = max(max_length, right - left + 1)
    
    return max_length

# Example usage
print(fruit_into_baskets([1, 2, 1]))  # Output: 3

function fruitIntoBaskets(fruits) {
    let left = 0;
    const fruitCount = new Map();
    let maxLength = 0;
    
    for (let right = 0; right < fruits.length; right++) {
        // Add fruit to basket
        const fruit = fruits[right];
        fruitCount.set(fruit, (fruitCount.get(fruit) || 0) + 1);
        
        // Contract window if more than 2 fruit types
        while (fruitCount.size > 2) {
            const leftFruit = fruits[left];
            fruitCount.set(leftFruit, fruitCount.get(leftFruit) - 1);
            if (fruitCount.get(leftFruit) === 0) {
                fruitCount.delete(leftFruit);
            }
            left++;
        }
        
        // Update max length
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

// Example usage
console.log(fruitIntoBaskets([1, 2, 1])); // Output: 3

5. Longest Ones After K Flips

Problem: Find the longest subarray of 1s after flipping at most k zeros.

Approach: Track number of zeros in window. Contract when zeros exceed k.

def longest_ones_after_k_flips(nums, k):
    left = 0
    zero_count = 0
    max_length = 0
    
    for right in range(len(nums)):
        # Count zeros in current window
        if nums[right] == 0:
            zero_count += 1
        
        # Contract window if too many zeros
        while zero_count > k:
            if nums[left] == 0:
                zero_count -= 1
            left += 1
        
        # Update max length
        max_length = max(max_length, right - left + 1)
    
    return max_length

# Example usage
print(longest_ones_after_k_flips([1,1,1,0,0,0,1,1,1,1,0], 2))  # Output: 6

function longestOnesAfterKFlips(nums, k) {
    let left = 0;
    let zeroCount = 0;
    let maxLength = 0;
    
    for (let right = 0; right < nums.length; right++) {
        // Count zeros in current window
        if (nums[right] === 0) {
            zeroCount++;
        }
        
        // Contract window if too many zeros
        while (zeroCount > k) {
            if (nums[left] === 0) {
                zeroCount--;
            }
            left++;
        }
        
        // Update max length
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

// Example usage
console.log(longestOnesAfterKFlips([1,1,1,0,0,0,1,1,1,1,0], 2)); // Output: 6

6. Subarray Product Less Than K

Problem: Count number of contiguous subarrays where product is less than k.

Approach: Use variable window with product tracking. Key insight: subarrays ending at position right = right - left + 1.

def subarray_product_less_than_k(nums, k):
    if k <= 1:
        return 0
    
    left = 0
    product = 1
    count = 0
    
    for right in range(len(nums)):
        # Expand window
        product *= nums[right]
        
        # Contract window while product >= k
        while product >= k:
            product //= nums[left]
            left += 1
        
        # Add count of subarrays ending at 'right'
        count += right - left + 1
    
    return count

# Example usage
print(subarray_product_less_than_k([10, 5, 2, 6], 100))  # Output: 8

function subarrayProductLessThanK(nums, k) {
    if (k <= 1) return 0;
    
    let left = 0;
    let product = 1;
    let count = 0;
    
    for (let right = 0; right < nums.length; right++) {
        // Expand window
        product *= nums[right];
        
        // Contract window while product >= k
        while (product >= k) {
            product /= nums[left];
            left++;
        }
        
        // Add count of subarrays ending at 'right'
        count += right - left + 1;
    }
    
    return count;
}

// Example usage
console.log(subarrayProductLessThanK([10, 5, 2, 6], 100)); // Output: 8

Common Pitfalls

Avoid These Mistakes:

Off-by-one errors when contracting: Make sure to remove the correct element when moving the left pointer
Forgetting to update answer after contraction: Always check if current window is better after shrinking
Not removing zero-count keys from frequency maps: Can lead to incorrect distinct count tracking
Using sliding window with negative numbers in sum problems: Breaks the monotonic property needed for window contraction
Not handling edge cases: Empty arrays, k > array length, k = 0
Incorrect window expansion/contraction order: Always expand first, then contract while invalid

Example: Incorrect Frequency Map Management

# ❌ WRONG: Leaves zero counts in map
def wrong_approach(s):
    char_count = {}
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
        # Contraction logic here
        char_count[removed_char] -= 1  # This leaves 0 counts!
    return len(char_count)  # Wrong distinct count

# ✅ CORRECT: Remove zero-count entries
def correct_approach(s):
    char_count = {}
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
        # Contraction logic here
        char_count[removed_char] -= 1
        if char_count[removed_char] == 0:
            del char_count[removed_char]  # Remove zero counts
    return len(char_count)  # Correct distinct count

// ❌ WRONG: Leaves zero counts in map
function wrongApproach(s) {
    const charCount = new Map();
    for (const char of s) {
        charCount.set(char, (charCount.get(char) || 0) + 1);
        // Contraction logic here
        charCount.set(removedChar, charCount.get(removedChar) - 1); // Leaves 0 counts!
    }
    return charCount.size; // Wrong distinct count
}

// ✅ CORRECT: Remove zero-count entries
function correctApproach(s) {
    const charCount = new Map();
    for (const char of s) {
        charCount.set(char, (charCount.get(char) || 0) + 1);
        // Contraction logic here
        charCount.set(removedChar, charCount.get(removedChar) - 1);
        if (charCount.get(removedChar) === 0) {
            charCount.delete(removedChar); // Remove zero counts
        }
    }
    return charCount.size; // Correct distinct count
}

Complexity Analysis & When Not to Use

Time Complexity

Most sliding window problems achieve O(n) time complexity because:

Each element is visited at most twice (once by right pointer, once by left pointer)
Inner while loop doesn't create nested loops since left pointer only moves forward
Total operations across all iterations remain linear

Space Complexity

Fixed window: Usually O(1) if only tracking window sum/properties
Variable window with frequency maps: O(k) where k is the number of distinct elements
Character problems: O(min(n, charset_size))

When NOT to Use Sliding Window

Sliding Window doesn't work when:

Array contains negative numbers and you need sum-based windows (breaks monotonicity)
Non-contiguous subarrays/substr