🪟 Sliding Window — JavaScript

Index: Sliding Window Index | Parent: JS Array Index

---

Template 1: Fixed Window Size

// Window of exactly size k
function fixedWindow(arr, k) {
  let windowSum = 0;
  // Build initial window
  for (let i = 0; i < k; i++) windowSum += arr[i];
  let result = windowSum;

  // Slide: add right, remove left
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];
    result = Math.max(result, windowSum); // or min, or track other property
  }
  return result;
}

Template 2: Variable Window Size

// Window that grows/shrinks based on condition
function variableWindow(arr) {
  let left = 0;
  let windowState = /* initial state (sum=0, Map, etc.) */;
  let result = 0;

  for (let right = 0; right < arr.length; right++) {
    // EXPAND: add arr[right] to window
    // windowState += arr[right];

    // SHRINK: while window violates condition, move left
    while (/* window invalid */) {
      // remove arr[left] from window
      left++;
    }

    // UPDATE result — window [left..right] is valid
    result = Math.max(result, right - left + 1);
  }
  return result;
}

---

Q1. Maximum Sum Subarray of Size K [E][FB]

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Fixed window size k + maximize sum = Fixed Sliding Window. Key signal: "subarray of size K".

Step 2 — Brute force:

Every subarray of size k: O(n×k). Too slow for large n.

Step 3 — Optimal insight:

Instead of re-summing, slide the window: add one new element on the right, remove one old element on the left. O(1) per step.

Step 4 — Algorithm:

1. Compute sum of first k elements

2. For each step i from k to n-1: sum += arr[i] - arr[i-k]

3. Track maximum

Step 5 — Edge cases:

- k > array length: invalid input

Way of Thinking: Fixed window: compute first window sum, then slide — add incoming, remove outgoing.

function maxSumSubarray(arr, k) {
  let windowSum = arr.slice(0, k).reduce((a, b) => a + b, 0);
  let maxSum = windowSum;

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

console.log(maxSumSubarray([2,1,5,1,3,2], 3)); // 9  (5+1+3)

---

Q2. Smallest Subarray with Sum >= S [M][FB]

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Variable window + minimize length + sum threshold = Variable Sliding Window.

Step 2 — Brute force:

Every subarray, check sum → O(n²). Need O(n).

Step 3 — Optimal insight:

Expand right to grow sum. Once sum >= S, try shrinking from left to find smallest valid window. Sum can only decrease by removing from left, so greedy shrink is safe.

Step 4 — Algorithm:

1. left=0, sum=0, minLen=Infinity

2. right expands: sum += nums[right]

3. While sum >= S: minLen = min(minLen, right-left+1), sum -= nums[left++]

Step 5 — Edge cases:

- No valid subarray: return 0

- All elements are 0: sum never reaches S

Way of Thinking: Variable window. Expand right. When sum >= S, record length, then shrink from left to find minimum.

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++];
    }
  }
  return minLen === Infinity ? 0 : minLen;
}

console.log(minSubarrayLen(7, [2,3,1,2,4,3])); // 2  ([4,3])

---

Q3. Longest Substring Without Repeating Characters [M][FB]

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Longest window without a constraint violation (repeated char) = Variable Sliding Window + hashmap.

Step 2 — Brute force:

Check every substring with Set → O(n²). Need O(n).

Step 3 — Optimal insight:

Store last seen index of each char. When duplicate found at right, jump left to lastSeen[char] + 1. This avoids slow one-by-one shrinking.

Step 4 — Algorithm:

1. Map stores char → last index

2. left = 0, maxLen = 0

3. For each right: if char is in map AND its index >= left, jump left past it

4. Update map and maxLen

Step 5 — Edge cases:

- All unique: window spans entire string

- All same: window size = 1

Way of Thinking: Variable window with a Map tracking last seen index. When duplicate found, jump left to lastSeen + 1.

function lengthOfLongestSubstring(s) {
  const lastSeen = new Map();
  let left = 0, maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (lastSeen.has(ch) && lastSeen.get(ch) >= left) {
      left = lastSeen.get(ch) + 1;
    }
    lastSeen.set(ch, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

console.log(lengthOfLongestSubstring("abcabcbb")); // 3 "abc"
console.log(lengthOfLongestSubstring("pwwkew"));   // 3 "wke"

---

Q4. Longest Substring with At Most K Distinct Characters [M]

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

"At most K distinct" + maximize length = Variable Sliding Window with frequency map.

Step 2 — Brute force:

All substrings with a Set check → O(n²). Need O(n).

Step 3 — Optimal insight:

Expand right freely. Once map has > K distinct chars, shrink from left, decrementing frequency. Remove from map when frequency hits 0.

Step 4 — Algorithm:

1. freq Map, left=0, maxLen=0

2. Add s[right] to freq

3. While freq.size > k: decrement freq[s[left]], delete if 0, left++

4. maxLen = max(maxLen, right-left+1)

Step 5 — Edge cases:

- k=0: always returns 0

- k >= total distinct chars: window is entire string

Way of Thinking: Variable window. Track frequency with a Map. When map size exceeds K, shrink from left.

function longestSubstringKDistinct(s, k) {
  const freq = new Map();
  let left = 0, maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    freq.set(s[right], (freq.get(s[right]) || 0) + 1);

    while (freq.size > k) {
      const lc = s[left++];
      freq.set(lc, freq.get(lc) - 1);
      if (freq.get(lc) === 0) freq.delete(lc);
    }
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

console.log(longestSubstringKDistinct("araaci", 2)); // 4  "araa"

---

Q5. Maximum Average Subarray of Size K [E]

function findMaxAverage(nums, k) {
  let sum = nums.slice(0, k).reduce((a, b) => a + b, 0);
  let maxSum = sum;

  for (let i = k; i < nums.length; i++) {
    sum += nums[i] - nums[i - k];
    maxSum = Math.max(maxSum, sum);
  }
  return maxSum / k;
}

console.log(findMaxAverage([1,12,-5,-6,50,3], 4)); // 12.75

---

Q6. Permutation in String [M][FB]

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Check if any permutation of s1 exists in s2 = Fixed window of size s1.length over s2 + frequency comparison.

Step 2 — Brute force:

Generate all permutations of s1, search in s2 → O(n!) — impossible.

Step 3 — Optimal insight:

Two strings are permutations iff their character frequencies match. Slide a window of size s1.length across s2, maintaining a running frequency array.

Step 4 — Algorithm:

1. Build freq array for s1 (26 slots, one per letter)

2. Build freq array for first window in s2

3. If arrays match: return true

4. Slide: add s2[right], remove s2[right - s1.length], compare

Step 5 — Edge cases:

- s1 longer than s2: impossible, return false

- s1 length 1: check any single char match

Way of Thinking: Fixed window of size s1.length. Track character frequency of s1. Slide window over s2, compare frequencies.

function checkInclusion(s1, s2) {
  if (s1.length > s2.length) return false;
  const need = new Array(26).fill(0);
  const window = new Array(26).fill(0);
  const a = 'a'.charCodeAt(0);

  for (const ch of s1) need[ch.charCodeAt(0) - a]++;
  for (let i = 0; i < s1.length; i++) window[s2[i].charCodeAt(0) - a]++;

  if (need.join() === window.join()) return true;

  for (let i = s1.length; i < s2.length; i++) {
    window[s2[i].charCodeAt(0) - a]++;
    window[s2[i - s1.length].charCodeAt(0) - a]--;
    if (need.join() === window.join()) return true;
  }
  return false;
}

console.log(checkInclusion("ab", "eidbaooo")); // true
console.log(checkInclusion("ab", "eidboaoo")); // false

---

Q7. Max Consecutive Ones After Flipping K Zeros [M][FB]

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Maximize a window with at most K "violations" (zeros) = Variable Sliding Window.

Step 2 — Brute force:

All substrings, count zeros → O(n²). Need O(n).

Step 3 — Optimal insight:

Expand right freely. When zeros in window > k, shrink from left. If we remove a zero, decrement count. No need to recalculate from scratch.

Step 4 — Algorithm:

1. left=0, zeros=0, maxLen=0

2. If nums[right] === 0: zeros++

3. While zeros > k: if nums[left] === 0: zeros--; left++

4. maxLen = max(maxLen, right-left+1)

Step 5 — Edge cases:

- k=0: longest run of 1s with no flips

- All zeros with k >= n: entire array

Way of Thinking: Variable window. Count zeros in window. When zeros > K, shrink from left (if we removed a zero, decrement count).

function longestOnes(nums, k) {
  let left = 0, zeros = 0, maxLen = 0;

  for (let right = 0; right < nums.length; right++) {
    if (nums[right] === 0) zeros++;

    while (zeros > k) {
      if (nums[left] === 0) zeros--;
      left++;
    }
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

console.log(longestOnes([1,1,1,0,0,0,1,1,1,1,0], 2)); // 6
console.log(longestOnes([0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], 3)); // 10

---

Pattern Summary