Sliding Window Technique

The Problem

Given an array of integers and a number, find the maximum sum of any subarray of length num. This problem is ideal for demonstrating the sliding window technique, which optimizes nested loops into a single pass.

Example:

maxSubarraySum([2, 6, 9, 2, 1, 8, 5, 6, 3], 3); // Returns 19 (from subarray [8, 5, 6])

Approach 1: Brute Force (Naive)

function maxSubarraySum(arr, num) {
  if (arr.length < num) return null;
  let max = -Infinity;
  for (let i = 0; i <= arr.length - num; i++) {
    let temp = 0;
    for (let j = 0; j < num; j++) {
      temp += arr[i + j];
    }
    max = Math.max(max, temp);
  }
  return max;
}

Explanation:

1. Outer loop iterates until reaching arr.length - num, to prevent running out of the array in the inner loop
2. Inner loop sums num number of elements starting from the current outer loop index
3. Compare each window’s sum to find the maximum.

Approach 2: Sliding Window (Optimized)

function maxSubarraySum(arr, num) {
  if (arr.length < num) return null;
  let max = 0;
  let temp = 0;

  for (let i = 0; i < num; i++) {
    max += arr[i];
  }

  temp = max;
  for (let i = num; i < arr.length; i++) {
    temp = temp - arr[i - num] + arr[i];
    max = Math.max(max, temp);
  }

  return max;
}

Explanation:

1. Initial window: Sum the first num elements.
2. Sliding logic:

• Subtract the outgoing element (left edge of the previous window).
• Add the incoming element (new right edge).

3. Efficiency: Reuses the previous sum to avoid recalculating from scratch.

Performance Comparison

Conclusion

The sliding window technique is a smart way of avoiding recalculation, reducing time complexity from O(n²) to O(n) while using constant space. It’s a powerful technique for optimizing problems involving contiguous sequences.