Back to DSA

Sliding Window Technique Tutorial

Lesson 1 of 3: Sliding Window Fundamentals

Progress33%

Sliding Window Fundamentals

The sliding window technique is a powerful algorithmic pattern for solving problems involving arrays or strings where you need to find a subarray or substring that meets certain criteria.

Key Concepts:
• Window: A contiguous subarray/substring
• Fixed Window: Window size remains constant
• Variable Window: Window size changes based on conditions
• Two Pointers: Left and right pointers to define window boundaries

When to Use Sliding Window:
• Finding maximum/minimum sum of subarray of size k
• Finding longest substring with k distinct characters
• Finding all anagrams of a pattern in a string
• Finding smallest subarray with sum >= target

Time Complexity: O(n) - Single pass through the array
Space Complexity: O(1) to O(k) depending on the problem

The key insight is to avoid recalculating everything when the window slides - instead, we add the new element and remove the old element.

Example

// Basic sliding window template
function slidingWindow(arr, k) {
  let windowSum = 0;
  let maxSum = 0;
  
  // Calculate sum of first window
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }
  maxSum = windowSum;
  
  // Slide the window
  for (let i = k; i < arr.length; i++) {
    // Add new element, remove old element
    windowSum = windowSum - arr[i - k] + arr[i];
    maxSum = Math.max(maxSum, windowSum);
  }
  
  return maxSum;
}

// Example usage
const arr = [1, 4, 2, 10, 2, 3, 1, 0, 20];
const k = 4;
console.log(slidingWindow(arr, k)); // Output: 24 (subarray [2, 10, 2, 3])

// Visualization:
// Window 1: [1, 4, 2, 10] = 17
// Window 2: [4, 2, 10, 2] = 18  
// Window 3: [2, 10, 2, 3] = 17
// Window 4: [10, 2, 3, 1] = 16
// Window 5: [2, 3, 1, 0] = 6
// Window 6: [3, 1, 0, 20] = 24 (maximum)

Visualization

Array: [1, 4, 2, 10, 2, 3, 1, 0, 20], k = 4

Step 1: [1, 4, 2, 10] = 17
Step 2: [4, 2, 10, 2] = 18
Step 3: [2, 10, 2, 3] = 17
Step 4: [10, 2, 3, 1] = 16
Step 5: [2, 3, 1, 0] = 6
Step 6: [3, 1, 0, 20] = 24 ← Maximum

Exercise

Implement a function to find the maximum sum of any contiguous subarray of size k: 1. Use sliding window technique 2. Handle edge cases (empty array, k > array length) 3. Return the maximum sum found 4. Optimize for O(n) time complexity

Lesson 1 of 3