Sliding Window

//   for r in 0..n-1://     add nums[r] to state//     if r >= k: remove nums[r-k] from state          // window is now exactly [r-k+1, r]//     if r >= k-1: best = f(best, state)//

//   l = 0//   for r in 0..n-1://     add s[r] to state//     while state is INVALID: remove s[l]; l++         // shrink until valid again//     best = max(best, r - l + 1)                      // window [l, r] is valid//

//   for r: add s[r]//     while state is VALID: best = min(best, r-l+1); remove s[l]; l++   // record BEFORE shrinking//   PRECONDITION for a target sum: every number >= 0 (section 0)

// If you came from Session 9.3: this is the case your oracle test catches. The shrink step assumes that// dropping a number from the left can only lower the sum. One negative number makes that false.function shortestSumAtLeast(nums, target) {              // Template C, as written for non-negative input  let l = 0, sum = 0, best = Infinity;  for (let r = 0; r < nums.length; r++) {    sum += nums[r];    while (sum >= target) { best = Math.min(best, r - l + 1); sum -= nums[l++]; }  }  return best === Infinity ? 0 : best;}function shortestSumAtLeastSlow(nums, target) {          // the oracle: every [l, r], no assumptions  let best = Infinity;  for (let l = 0; l < nums.length; l++) {    let sum = 0;    for (let r = l; r < nums.length; r++) { sum += nums[r]; if (sum >= target) best = Math.min(best, r - l + 1); }  }  return best === Infinity ? 0 : best;}// at r = 2 the sum hit 5, it dropped the 3, the sum fell to 2, and shrinking stopped. The -2 stays in the window// for good because the loop only shrinks while the sum is still >= target. Negatives: use a prefix-sum map instead.//// From Session 9.3, stop here: Template A, Template C and this section are the visit. Sections 1 and 2 are the two// shapes you already wrote; sections 3 to 7 are interview practice for after Session 9.4.

function maxSumK(nums, k) {  if (nums.length < k) return 0;  let sum = 0, best = -Infinity;  for (let r = 0; r < nums.length; r++) {    sum += nums[r];    if (r >= k) sum -= nums[r - k];    if (r >= k - 1) best = Math.max(best, sum);  }  return best;}

function lengthOfLongestSubstring(s) {  const seen = new Set();  let l = 0, best = 0;  for (let r = 0; r < s.length; r++) {    while (seen.has(s[r])) seen.delete(s[l++]);    seen.add(s[r]);    best = Math.max(best, r - l + 1);  }  return best;}

function longestKDistinct(s, k) {  const f = new Map();  let l = 0, best = 0;  for (let r = 0; r < s.length; r++) {    f.set(s[r], (f.get(s[r]) ?? 0) + 1);    while (f.size > k) {      f.set(s[l], f.get(s[l]) - 1);      if (f.get(s[l]) === 0) f.delete(s[l]);      l++;    }    best = Math.max(best, r - l + 1);  }  return best;}

function minWindow(s, t) {  const need = new Map();  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);  let have = 0, l = 0, best = [0, Infinity];  const win = new Map();  for (let r = 0; r < s.length; r++) {    const c = s[r];    win.set(c, (win.get(c) ?? 0) + 1);    if (need.has(c) && win.get(c) === need.get(c)) have++;    while (have === need.size) {      if (r - l < best[1] - best[0]) best = [l, r];      const d = s[l++];      win.set(d, win.get(d) - 1);      if (need.has(d) && win.get(d) < need.get(d)) have--;    }  }  return best[1] === Infinity ? '' : s.slice(best[0], best[1] + 1);}

function findAnagrams(s, p) {  const out = [], need = new Array(26).fill(0), win = new Array(26).fill(0);  const ix = (c) => c.charCodeAt(0) - 97;  for (const c of p) need[ix(c)]++;  for (let r = 0; r < s.length; r++) {    win[ix(s[r])]++;    if (r >= p.length) win[ix(s[r - p.length])]--;    if (r >= p.length - 1 && win.every((v, i) => v === need[i])) out.push(r - p.length + 1);  }  return out;}const checkInclusion = (p, s) => findAnagrams(s, p).length > 0; // "permutation in string"

function longestOnes(nums, k) {  let l = 0, zeros = 0, best = 0;  for (let r = 0; r < nums.length; r++) {    if (nums[r] === 0) zeros++;    while (zeros > k) if (nums[l++] === 0) zeros--;    best = Math.max(best, r - l + 1);  }  return best;}

function maxSlidingWindow(nums, k) {  const dq = []; // indices; nums[dq] strictly decreasing front->back  let head = 0; // head index instead of shift() to keep O(1)  const out = [];  for (let r = 0; r < nums.length; r++) {    while (dq.length > head && nums[dq[dq.length - 1]] <= nums[r]) dq.pop(); // drop smaller tail    dq.push(r);    if (dq[head] <= r - k) head++; // front fell out of the window    if (r >= k - 1) out.push(nums[dq[head]]);  }  return out;}