Patterns

Window of fixed size k slides across the array; maintain rolling stat

When to useMax/min/sum of every contiguous subarray of size k

iterative

Throttling Gateway

throttling_gateway

Efficient Harvest

amazon_oa_efficient_harvest

Find All Anagrams in a String

find_all_anagrams

Maximum Disk Space Available

find_the_maximum_available_disk_space

Largest Subarray

google_oa_largest_subarray

Secret Fruit List

secret_fruits_list

Sliding Window Maximum | Monotonic Stack

sliding_window_maximum

Sliding Window Introduction

INITIALIZE

build first window of size k; capture initial stat

const qs = [new Limiter(1, 3), new Limiter(10, 20), new Limiter(60, 60)];
let dropped = 0;
let i = 0;

const n = profit.length;
const half = n / 2;
let windowSum = 0;
for (let i = 0; i < k; i++) windowSum += profit[i];
for (let i = half; i < half + k; i++) windowSum += profit[i];
let best = windowSum;

const need = new Map(); /* freq of check */
const window = new Map(); /* freq of first window */
for (let i = 0; i < check.length; i++) window.set(...);
if (matches(need, window)) result.push(0);

const deque = []; /* monotonic increasing deque of indices */
let best = -Infinity;

let bestStart = 0;

let cursor = 0;

const q = []; // monotonic deque of indices
const res = [];

let windowSum = 0;
for (let i = 0; i < k; i++) windowSum += nums[i];
let largest = windowSum;

let windowSum = 0;
for (let i = 0; i < k; i++) windowSum += nums[i];
let total = Math.floor(windowSum / k);

let windowSum = 0;
for (let i = 0; i < k; i++) windowSum += profit[i] + profit[i + n/2];
let best = windowSum;

TRAVERSE

for r=k...n

while (i < requestTimes.length) {

for (let i = 0; i < half - k; i++) {

for (let i = check.length; i < original.length; i++) {

for (let i = 0; i < segments.length; i++) {

for (let i = 1; i <= arr.length - k; i++) {

for (const secret of secretFruitLists) {

for (let i = 0; i < nums.length; i++) {

for (let right = k; right < nums.length; right++) {

for (let right = k; right < nums.length; right++) {

for (let i = 1; i < n / 2; i++) {

[SLIDE]

add arr[r], remove arr[r-k]

  let worst = -Infinity;
  for (const q of qs) worst = Math.max(worst, q.accum - q.limit);
  dropped += Math.max(0, worst);

  windowSum -= profit[i];
  windowSum -= profit[half + i];
  windowSum += profit[i + k];
  windowSum += profit[half + i + k];

  window.set(add, count+1);
  window.set(remove, count-1);
  if (window.get(remove) === 0) window.delete(remove);

  /* evict tail while new element is smaller (keep deque monotone) */
  while (deque.length && segments[deque.at(-1)] >= segments[i]) deque.pop();
  deque.push(i);
  if (deque[0] <= i - x) deque.shift(); /* evict expired head */

  /* lexicographic compare window at i vs window at bestStart */
  if (arr[i] > arr[bestStart]) bestStart = i; /* simplified; see full solution */

    if (matchesAt(cursor, secret)) { cursor += secret.length; break; }
    cursor++;

  while (q.length > 0 && nums[q[q.length - 1]] <= nums[i]) q.pop();
  q.push(i);
  if (q[0] === i - k) q.shift();

  windowSum += nums[right] - nums[right - k];

  windowSum += nums[right] - nums[right - k];

  windowSum -= profit[i-1] + profit[i-1 + n/2];
  windowSum += profit[i+k-1] + profit[i+k-1 + n/2];

[TRACK]

update best with new window's stat

  let worst = -Infinity;
  for (const q of qs) worst = Math.max(worst, q.accum - q.limit);
  dropped += Math.max(0, worst);

  best = Math.max(best, windowSum);

  if (matches(need, window)) result.push(i - check.length + 1);

  if (i >= x - 1) best = Math.max(best, segments[deque[0]]);

  /* lexicographic compare window at i vs window at bestStart */
  if (arr[i] > arr[bestStart]) bestStart = i; /* simplified; see full solution */

    if (matchesAt(cursor, secret)) { cursor += secret.length; break; }
    cursor++;

  if (i >= k - 1) res.push(nums[q[0]]);

  largest = Math.max(largest, windowSum);

  total += Math.floor(windowSum / k);

  best = Math.max(best, windowSum);

RETURN

best result

return dropped;

return best;

return result;

return best;

return arr.slice(bestStart, bestStart + k);

return true;

return res;

return largest;

return total;

return best;