March 10, 2025

Sliding Window

The Sliding Window Algorithm is an optimization technique used to reduce the time complexity of problems involving arrays or lists. It helps in scenarios where we need to process a subset of data that “slides” over a collection.

Why Use Sliding Window?

Instead of repeatedly recalculating a subset’s properties (like sum, average, or maximum), the sliding window technique maintains a running result and updates it dynamically as the window slides forward. This often reduces an solution to .

Real-World Applications

Types of Sliding Window

Key Differences:

Examples in JavaScript

  1. Finding Maximum Sum of k Consecutive Elements (Fixed-size)
function maxSumSubarray(arr, k) {
  let maxSum = 0;
  let windowSum = 0;

  // Compute sum of the first k elements
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }
  maxSum = windowSum;

  // Slide the window
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}

console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // Output: 9
  1. Longest Substring Without Repeating Characters (Dynamic-size)
function longestUniqueSubstring(s) {
  let charSet = new Set();
  let left = 0;
  let maxLength = 0;

  for (let right = 0; right < s.length; right++) {
    while (charSet.has(s[right])) {
      charSet.delete(s[left]);
      left++;
    }
    charSet.add(s[right]);
    maxLength = Math.max(maxLength, right - left + 1);
  }

  return maxLength;
}

console.log(longestUniqueSubstring("abcabcbb")); // Output: 3

When to Use Sliding Window