17-Jan-2025

The sliding window technique is a powerful optimization method used to solve problems involving arrays or strings where you need to find a subarray or substring that satisfies a specific condition. It’s particularly useful when dealing with contiguous sequences of elements. Instead of iterating through every possible subarray/substring, which can lead to O(n^2) or O(n^3) time complexity, the sliding window approach often reduces the complexity to O(n).

Core Idea:

Imagine a “window” that slides over the array/string. This window has a fixed or variable size, and we maintain certain information about the elements within the window. As the window slides, we update this information incrementally, avoiding redundant calculations.

Example: Finding the maximum sum of a subarray of size k

Let’s say we have an array arr = [1, 4, 2, 10, 23, 3, 1, 0, 20] and k = 4. We want to find the maximum sum of any contiguous subarray of size 4.

function maxSubarraySum(arr, k) {
  if (arr.length < k) {
    return null; // Handle edge case where k is larger than the array
  }

  let maxSum = 0;
  let windowSum = 0;

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

  // Slide the window and update the sum incrementally
  for (let i = k; i < arr.length; i++) {
    windowSum = windowSum - arr[i - k] + arr[i]; // Remove the leftmost element and add the rightmost
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}


const arr = [1, 4, 2, 10, 23, 3, 1, 0, 20];
const k = 4;
const result = maxSubarraySum(arr, k);
console.log(result); // Output: 39 (10 + 23 + 3 + 1)

Explanation:

1. Initialization: We calculate the sum of the first window (elements from index 0 to k-1).
2. Sliding: In each iteration of the outer loop, we slide the window to the right by one position.
3. Incremental Update: Instead of recalculating the sum of the entire window, we subtract the element that just left the window ( arr[i-k] ) and add the new element that entered the window (arr[i] ).
4. Max Sum: We keep track of the maximum sum encountered so far.

When to use the Sliding Window Technique:

• Problems involving subarrays/substrings of a specific length.
• Problems where you need to find the minimum/maximum/longest/shortest subarray/substring satisfying a condition.
• Optimization problems where redundant calculations can be avoided.

The Sliding Window Technique is a valuable tool to have in your DSA problem-solving arsenal. It can significantly improve the efficiency of your solutions by reducing time complexity. By understanding its core idea and practicing its application, you can tackle a wide range of array and string problems effectively.