Patterns

Window expands by moving right, shrinks by moving left when invariant violated

When to useLongest/shortest substring with constraint, max sum subarray with constraint

iterative

Count Maximum Teams

amazon_oa_count_maximum_teams

Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

continuous_subarray_with_diff_of_limit

Count Number of Nice Subarrays

count_number_of_nice_subarrays

Least Consecutive Cards to Match

least_consecutive_cards_to_match

Longest Substring without Repeating Characters

longest_substring_without_repeating_characters

Minimum Window Substring

minimum_window_substring

Subarray Sum Longest

subarray_sum_longest

Subarray Sum Shortest

subarray_sum_shortest

Longest Repeating Character Replacementmedium

longest_repeating_character_replacement · no slots

Minimum Size Subarray Summedium

minimum_size_subarray_sum · no slots

INITIALIZE

window state (map/sum/etc), left=0, best result

skill.sort((a, b) => a - b);
let left = 0, teams = 0;

let left = 0, best = 0;
const minDeque = [], maxDeque = [];

let left = 0, count = 0, odds = 0;  // inside atMost(limit)

const window = new Map();
let left = 0, shortest = cards.length + 1;

const freq = new Map();
let left = 0, best = 0;

const need = new Map(); /* build from check */
const window = new Map();
let left = 0, formed = 0;
let best = '';

let windowSum = 0, length = 0, left = 0;

let windowSum = 0, length = nums.length + 1, left = 0;

—

TRAVERSE

for right in range

for (let right = 0; right < skill.length; right++) {

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

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

for (let right = 0; right < cards.length; right++) {

for (let right = 0; right < s.length; right++) {

for (let right = 0; right < original.length; right++) {

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

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

—

[EXPAND]

add arr[right] to window state

  if (right - left + 1 === teamSize) { teams++; left = right + 1; }

  // maintain monotonic deques: pop stale back entries, push right
  while (minDeque.length && nums[right] < nums[minDeque.at(-1)]) minDeque.pop();
  minDeque.push(right);
  while (maxDeque.length && nums[right] > nums[maxDeque.at(-1)]) maxDeque.pop();
  maxDeque.push(right);

  if (nums[right] % 2 === 1) odds++;

  window.set(cards[right], (window.get(cards[right]) ?? 0) + 1);

  const ch = s[right];
  freq.set(ch, (freq.get(ch) ?? 0) + 1);

  window.set(ch, (window.get(ch) ?? 0) + 1);
  if (need.has(ch) && window.get(ch) === need.get(ch)) formed++;

  windowSum += nums[right];

  windowSum += nums[right];

—

shrink

while invariant violated, remove arr[left] and left++

  while (skill[right] - skill[left] > maxDiff) { left++; }

  while (nums[maxDeque[0]] - nums[minDeque[0]] > limit) {
    if (maxDeque[0] === left) maxDeque.shift();
    if (minDeque[0] === left) minDeque.shift();
    left++;
  }

  while (odds > limit) {
    if (nums[left] % 2 === 1) odds--;
    left++;
  }

  while (window.get(cards[right]) === 2) {
    shortest = Math.min(shortest, right - left + 1);
    window.set(cards[left], window.get(cards[left]) - 1);
    left++;
  }

  while (freq.get(ch) > 1) {
    freq.set(s[left], freq.get(s[left]) - 1);
    left++;
  }

  while (formed === required) {
    /* record candidate */
    /* remove original[left] from window */
    left++;
  }

  while (windowSum > target) {
    windowSum -= nums[left];
    left++;
  }

  while (windowSum >= target) {
    length = Math.min(length, right - left + 1);
    windowSum -= nums[left];
    left++;
  }

—

[TRACK]

update best result with current window

  if (right - left + 1 === teamSize) { teams++; left = right + 1; }

  best = Math.max(best, right - left + 1);

  count += right - left + 1;

  window.set(cards[right], (window.get(cards[right]) ?? 0) + 1);

  best = Math.max(best, right - left + 1);

  /* candidate updated inside shrink loop */

  length = Math.max(length, right - left + 1);

  /* tracked inside shrink */

—

RETURN

best result

return teams;

return best;

return atMost(nums, k) - atMost(nums, k - 1);

return shortest !== cards.length + 1 ? shortest : -1;

return best;

return best;

return length;

return length;

—