🗓️ Day 7: Sliding Window Technique

🧠 Concept Deep Dive

Sliding Window is a powerful pattern to reduce nested loops and improve time complexity, especially for problems involving subarrays, substrings, or sequences.

Instead of re-computing the result from scratch for every window of data, we "slide" a window over the data and update our result incrementally.

🔹 When to Use Sliding Window:

• Finding max/min sum of a subarray of fixed size
• Finding longest substring without repeating characters
• Detecting anagrams in a string

🔹 Types of Sliding Window:

1. Fixed-size window: window size k is constant
2. Dynamic-size window: window expands/contracts based on conditions

📖 Example 1: Fixed-size Window

Problem:

Find the maximum sum of any subarray of size k.

Approach:

• Use a window of size k
• Add incoming element to current sum
• Subtract outgoing element

function maxSubarraySum(nums: number[], k: number): number {
  let maxSum = 0;
  let windowSum = 0;

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

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

  return maxSum;
}

// Test
console.log(maxSubarraySum([2, 1, 5, 1, 3, 2], 3)); // Output: 9

Visualization:

Window size k = 3
[2, 1, 5] -> sum = 8
   [1, 5, 1] -> sum = 7
      [5, 1, 3] -> sum = 9 ✅
         [1, 3, 2] -> sum = 6

💪 Example 2: Dynamic-size Window

Problem:

Find the length of the longest substring without repeating characters.

Approach:

• Use two pointers to expand/contract window
• Use a set to track unique characters

function lengthOfLongestSubstring(s: string): number {
  const seen = new Set<string>();
  let left = 0, maxLength = 0;

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

  return maxLength;
}

// Test
console.log(lengthOfLongestSubstring("abcabcbb")); // Output: 3 ("abc")

Visualization:

left = 0, right = 2
seen = {a, b, c} ✅

right = 3: duplicate 'a' → shrink window from left

🧰 Real-world Analogy

Think of a sliding window like looking through a camera frame while panning across a landscape. You only focus on what's in the frame (window) and shift as needed.

🔢 Big O Complexity

🧪 LeetCode-style Homework

Problem: Max Consecutive Ones III

Function Signature:

function longestOnes(nums: number[], k: number): number;

Input:

nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2

Output:

6

Explanation: Replace up to 2 zeros with 1s to form longest subarray of 1s.

📆 Summary

• Sliding window lets you solve contiguous problems in O(n)
• Fixed window = same size every time
• Dynamic window = grows/shrinks as needed
• Reduces nested loops into single-pass efficient code

🔬 Up Next

▶️ Day 8: Two Pointers Pattern — solving problems with two simultaneous scans!