LC Patterns — Sliding Window

long long s = 0;
for (int i = 0; i < k; ++i) s += nums[i];          // warm-up on the first k
int best = s;
for (int r = k; r < n; ++r) {
    s += nums[r] - nums[r - k];                     // slide by one: one in, one out
    best = max(best, (int)s);
}

int l = 0, best = 0;
for (int r = 0; r < n; ++r) {
    add(nums[r]);                                   // 1. expand
    while (invalid()) remove(nums[l++]);            // 2. shrink until valid again
    best = max(best, r - l + 1);                    // 3. window is valid here
}

int l = 0, best = INT_MAX;
for (int r = 0; r < n; ++r) {
    add(nums[r]);
    while (valid()) {                               // shrink while STILL valid
        best = min(best, r - l + 1);                // record BEFORE breaking validity
        remove(nums[l++]);
    }
}

int l = 0; long long count = 0;
for (int r = 0; r < n; ++r) {
    add(nums[r]);
    while (invalid()) remove(nums[l++]);
    count += r - l + 1;                             // every left in [l,r] gives a valid window ending at r
}

What it is: The window size k is given — compute something (max average, count of vowels, threshold checks) over every contiguous block of exactly k elements. Slide by one: add the element entering, subtract the one leaving, never recompute the whole block.

Intuition: two neighbouring windows share k−1 elements — recomputing throws that overlap away. The delta (one in, one out) is the whole idea. This is the "hello world" of the topic: drill the slide mechanics here so the variable-size patterns are pure thinking.

double findMaxAverage(vector<int>& nums, int k) {
    double s = 0;
    for (int i = 0; i < k; ++i) s += nums[i];             // warm-up on first k
    double best = s;
    for (int r = k; r < (int)nums.size(); ++r) {
        s += nums[r] - nums[r - k];                       // one in, one out
        best = max(best, s);
    }
    return best / k;
}

What it is: The window size is fixed by the pattern string's length, and the summary is a character-count map: does the current window hold exactly the same multiset of characters as the pattern? Slide across the text, updating two counts per step, and report every position where the counts match.

Intuition: an anagram is defined by character counts — order doesn't matter — so a window matches when its count map equals the pattern's. The efficiency trick: don't compare whole maps each step. Keep a running need counter (pattern characters still unmatched inside the window); the window is an anagram exactly when need == 0, and it moves by at most 1 per slide.

vector<int> findAnagrams(string s, string p) {
    vector<int> res;
    int n = s.size(), k = p.size();
    if (n < k) return res;
    int cnt[26] = {0};
    for (char c : p) ++cnt[c - 'a'];
    int need = k;                                    // chars still needed in the window
    for (int r = 0; r < n; ++r) {
        if (cnt[s[r]-'a']-- > 0) --need;             // consumed a needed char
        if (r >= k && cnt[s[r-k]-'a']++ >= 0) ++need; // char leaving gives one back
        if (need == 0) res.push_back(r - k + 1);
    }
    return res;
}

What it is: The workhorse: find the longest contiguous run satisfying a rule — no repeated characters, at most k distinct elements, all-ones-after-flips. Grow the right end greedily; whenever the rule breaks, move the left end just far enough to fix it; the answer is the biggest valid window you ever saw.

Intuition: greedy growth is safe thanks to monotonicity: if [l, r] is invalid, every window containing it is invalid — so the left end never backs up, and each element enters and leaves at most once (amortized O(n)). The summary carries the rule: a last-seen map/set for "no repeats," a distinct-count map for "at most k kinds."

int lengthOfLongestSubstring(string s) {
    vector<int> last(128, -1);                   // char → last index seen
    int l = 0, best = 0;
    for (int r = 0; r < (int)s.size(); ++r) {
        if (last[s[r]] >= l) l = last[s[r]] + 1; // jump past prev copy (never backward)
        last[s[r]] = r;
        best = max(best, r - l + 1);
    }
    return best;
}

What it is: A sub-species of Pattern 3: the window may contain up to k violations — k zeros you can flip, k characters you can replace, k deletions — and you want the longest such window. The summary tracks the cost to fix; shrink when the cost passes the budget k.

Intuition: "flip at most k zeros for the longest run of 1s" = "longest window containing at most k zeros" — the budget is the constraint, and it's monotonic. For character replacement (424): a window is fixable when window_len − count_of_most_frequent_char ≤ k — everything except the majority character gets replaced.

int longestOnes(vector<int>& nums, int k) {
    int l = 0, zeros = 0, best = 0;
    for (int r = 0; r < (int)nums.size(); ++r) {
        if (nums[r] == 0) ++zeros;
        while (zeros > k) if (nums[l++] == 0) --zeros;   // shrink until budget ok
        best = max(best, r - l + 1);
    }
    return best;
}

What it is: The mirror of Pattern 3: find the smallest window that satisfies the rule — the shortest subarray with sum ≥ target, the shortest substring of s covering all of t. Grow until satisfied, then shrink aggressively while it stays satisfied, recording each valid size.

Intuition: once the window satisfies the rule, growing further can't give a shorter answer — so the moment you're valid, squeeze from the left until you break validity, collecting candidate sizes. The record-inside-the-shrink-loop placement (Template S) is the exact mirror of Pattern 3, and the #1 thing people flip the wrong way.

int minSubArrayLen(int target, vector<int>& nums) {
    int l = 0, best = INT_MAX; long long sum = 0;
    for (int r = 0; r < (int)nums.size(); ++r) {
        sum += nums[r];
        while (sum >= target) {              // shrink while STILL valid
            best = min(best, r - l + 1);     // record before breaking
            sum -= nums[l++];
        }
    }
    return best == INT_MAX ? 0 : best;
}

What it is: Not longest or shortest but how many subarrays satisfy the rule. Two tools: (a) for monotonic "≤"-style rules, every valid window [l, r] means all sub-windows ending at r are valid too → add r − l + 1 per step; (b) for "exactly k" rules, count atMost(k) − atMost(k−1) — two easy windows instead of one impossible one.

Intuition: (a) works because validity is downward-closed: if [l, r] is valid, so are [l+1, r], …, [r, r] — the number of valid left-ends is just the window length. (b) works because "exactly k" isn't monotonic, but "at most k" is — and exactly-k = atMost(k) − atMost(k−1), turning one impossible problem into two Template C runs. This subtraction is the signature move; interviewers watch for it.

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    if (k <= 1) return 0;
    int l = 0, prod = 1, count = 0;
    for (int r = 0; r < (int)nums.size(); ++r) {
        prod *= nums[r];
        while (prod >= k) prod /= nums[l++];   // restore validity
        count += r - l + 1;                    // subarrays ending at r
    }
    return count;
}
// exactly-k distinct (992):  atMost(k) - atMost(k-1)

What it is: The summary you need is the window's max or min — which a plain counter can't un-do (remove the max and you don't know the runner-up). Keep a deque of candidate indices in decreasing order (for max): the front is the current max, expired indices pop from the front, and smaller-and-newer-beaten values pop from the back.

Intuition: when a new element enters, every smaller element still in the deque can never be a future maximum (the newcomer is bigger and outlives them) — so throw them away. What's left is a decreasing staircase of "values that could still matter." The deque is its own reusable micro-pattern (next-greater-element reuses it).

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;                                    // indices, values decreasing
    vector<int> res;
    for (int r = 0; r < (int)nums.size(); ++r) {
        while (!dq.empty() && nums[dq.back()] <= nums[r]) dq.pop_back();
        dq.push_back(r);
        if (dq.front() <= r - k) dq.pop_front();      // drop expired front
        if (r >= k - 1) res.push_back(nums[dq.front()]);
    }
    return res;
}

What it is: The window summary is a hash of the window's contents, updatable in O(1) as it slides (subtract the leaving character's contribution, multiply, add the entering one). Turns "compare every length-L window against a pattern / against each other" from O(nL) into O(n).

Intuition: treat the window as a number in base b (b > alphabet size), mod a big prime; sliding is one multiply-add. Equal windows ⇒ equal hashes; unequal hashes ⇒ definitely different — so hash first, verify contents only on a hit. The marquee composition: 1044 = binary search (on answer length L) + rolling hash (do any two length-L windows collide?) — a two-file combo worth naming.

vector<string> findRepeatedDnaSequences(string s) {
    unordered_set<string> seen, repeated;
    for (int i = 0; i + 10 <= (int)s.size(); ++i) {
        string w = s.substr(i, 10);
        if (!seen.insert(w).second) repeated.insert(w);   // insert failed ⇒ already present
    }
    return {repeated.begin(), repeated.end()};
}
// Rabin–Karp: roll a base-b hash mod a large prime instead of substr(); watch overflow (use long long).