🗓️ Day 10: Sliding Window Technique

🫠 Concept Deep Dive

The Sliding Window technique is a smart approach for handling problems involving subarrays, substrings, or contiguous sequences. Instead of using nested loops (which is slow), you maintain a window that slides across the data.

This technique allows you to:

• Optimize time complexity to O(n)
• Solve problems like maximum sum subarray, longest unique substring, or minimum window substring

🔹 When to Use Sliding Window:

• You're working with arrays or strings
• The problem asks for the maximum, minimum, or average of a subarray or substring
• You're looking for patterns in a contiguous sequence

📖 Example 1: Maximum Sum of Subarray of Size K

Problem:

Find the maximum sum of a contiguous subarray of size k.

Approach:

• Create a window of size k
• Slide it across the array by adding the next element and removing the first
• Track the maximum sum

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

  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }
  maxSum = windowSum;

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

  return maxSum;
}

Example:

Input: [2, 1, 5, 1, 3, 2], k = 3
Window moves: [2,1,5] -> [1,5,1] -> [5,1,3] -> [1,3,2]
Max sum = 5+1+3 = 9

📖 Example 2: Longest Substring Without Repeating Characters

Problem:

Find the length of the longest substring with no repeating characters.

Approach:

• Use a hash map to track characters
• Expand the window until you hit a duplicate
• Shrink the window from the left until duplicates are gone

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

  for (let end = 0; end < s.length; end++) {
    const char = s[end];
    if (seen.has(char) && seen.get(char)! >= start) {
      start = seen.get(char)! + 1;
    }
    seen.set(char, end);
    maxLength = Math.max(maxLength, end - start + 1);
  }

  return maxLength;
}

Example:

Input: "abcabcbb"
Longest substring: "abc" => Length = 3

🔬 Real-world Analogy

Think of a window on a train. You can only see what’s inside the window — as the train moves, you see different views. Sliding Window works the same — you shift what you’re observing in a fixed-size or flexible-size range.

📊 Big O Complexity

🧪 LeetCode-style Homework

Problem: Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray of which the sum is greater than or equal to target. If there is no such subarray, return 0.

Function Signature:

function minSubArrayLen(target: number, nums: number[]): number;

Hint:

• Use a dynamic-sized sliding window.
• Shrink the window from the left while the sum is >= target.

🗓️ Summary

• Sliding Window is perfect for contiguous sequence problems.
• Helps reduce time complexity from O(n^2) to O(n).
• Common in substring, subarray, and optimization challenges.

🔬 Up Next

▶️ Day 11: Prefix Sum Technique