DSAPatternsAlgorithms

Sliding Window Pattern Deep Dive

Master the sliding window technique for solving subarray and substring problems.

January 25, 20246 min read

Sliding Window Pattern Deep Dive

The sliding window pattern is used for problems involving contiguous sequences (subarrays or substrings).

Types of Sliding Windows

Fixed Size Window

function maxSumSubarray(arr, k) {
  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }
  
  let maxSum = windowSum;
  for (let i = k; i < arr.length; i++) {
    windowSum = windowSum - arr[i - k] + arr[i];
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

Dynamic Size Window

function minSubArrayLen(target, nums) {
  let left = 0, sum = 0, minLen = Infinity;
  
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    
    while (sum >= target) {
      minLen = Math.min(minLen, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }
  
  return minLen === Infinity ? 0 : minLen;
}

When to Use

Maximum/minimum sum of k elements
Longest/shortest substring with condition
Count of subarrays meeting criteria

The key insight: instead of recalculating, we slide!

Comments