Sliding Window

// Template 1: fixed-size window. Neighbouring windows share k - 1 elements, so update the summary
// with the element that enters and the one that leaves instead of recomputing it: O(n), not O(n · k).
export function maxWindowSum(nums, k) {
  if (k <= 0 || k > nums.length) return null;
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];   // the first full window ends at index k - 1
  let best = sum;
  for (let right = k; right < nums.length; right++) {
    sum += nums[right] - nums[right - k];       // nums[right] enters, nums[right - k] leaves
    best = Math.max(best, sum);
  }
  return best;
}

// Template 2: variable window, LONGEST valid. Grow right; while the window breaks the rule, shrink left;
// then the window is the longest valid one ending at right. Works when shrinking a valid window keeps it valid.
// Example rule: at most k distinct characters.
export function longestAtMostKDistinct(s, k) {
  const count = new Map();   // character → copies inside s[left..right]
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    count.set(s[right], (count.get(s[right]) ?? 0) + 1);
    while (count.size > k) {                     // invalid: too many distinct characters
      const out = s[left];
      if (count.get(out) === 1) count.delete(out); // delete at zero so size stays honest
      else count.set(out, count.get(out) - 1);
      left++;
    }
    best = Math.max(best, right - left + 1);     // record AFTER shrinking
  }
  return best;
}

// Template 3: variable window, SHORTEST valid. Grow right until the window is valid; then, while it stays
// valid, record it and shrink left. Example rule: sum >= target, with positive numbers only.
export function shortestSumAtLeast(nums, target) {
  let left = 0;
  let sum = 0;
  let best = Infinity;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= target) {                      // valid: record BEFORE shrinking
      best = Math.min(best, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }
  return best === Infinity ? 0 : best;
}

// Template 4: monotonic deque. Holds indices whose values DECREASE from front to back, so the front is
// always the maximum of the current window. Every index is pushed once and popped once: O(n) overall.
export function windowMax(nums, k) {
  const dq = [];      // indices; dq[head..] is the live part of the deque
  let head = 0;       // moving head instead of dq.shift(), which is O(n)
  const out = [];
  for (let i = 0; i < nums.length; i++) {
    if (head < dq.length && dq[head] <= i - k) head++;               // front index slid out
    while (dq.length > head && nums[dq.at(-1)] <= nums[i]) dq.pop(); // can never be a max again
    dq.push(i);
    if (i >= k - 1) out.push(nums[dq[head]]);                        // window [i - k + 1, i] is full
  }
  return out;
}