Pattern Reference
Sliding Window - Advanced
"At-most-k trick, exactly-k count formula, multiple-pointer windows, deque optimization for range max/min."
Loading...
Deep Dive Tutorial
The at-most-k trick: count(exactly k) = count(at-most-k) - count(at-most-(k-1)). This converts "count subarrays with exactly k distinct" into two easier "at-most" problems, each solvable in O(n) with a shrinking window. For minimum window substring: expand right until condition met, shrink left while condition holds.
At-most-k trick and min window template
// Count subarrays with exactly k distinct elements
// = atMost(k) - atMost(k-1)
function countExactlyK(nums, k) {
const atMost = (limit) => {
const freq = new Map();
let count = 0, l = 0;
for (let r = 0; r < nums.length; r++) {
freq.set(nums[r], (freq.get(nums[r]) || 0) + 1);
while (freq.size > limit) {
const lv = nums[l++];
freq.set(lv, freq.get(lv) - 1);
if (!freq.get(lv)) freq.delete(lv);
}
count += r - l + 1; // all subarrays ending at r with ≤ limit distinct
}
return count;
};
return atMost(k) - atMost(k - 1);
}
// Minimum window containing all characters of t
function minWindow(s, t) {
const need = new Map(), have = new Map();
for (const c of t) need.set(c, (need.get(c) || 0) + 1);
let satisfied = 0, minLen = Infinity, l = 0, res = '';
for (let r = 0; r < s.length; r++) {
have.set(s[r], (have.get(s[r]) || 0) + 1);
if (need.has(s[r]) && have.get(s[r]) === need.get(s[r])) satisfied++;
while (satisfied === need.size) {
if (r - l + 1 < minLen) { minLen = r - l + 1; res = s.slice(l, r + 1); }
have.set(s[l], have.get(s[l]) - 1);
if (need.has(s[l]) && have.get(s[l]) < need.get(s[l])) satisfied--;
l++;
}
}
return res;
}Worked Problems
frame
Advanced sliding window patterns:
- Exactly k distinct: atMost(k) - atMost(k-1)
- Min window with all chars: expand right, shrink left greedily
- Max element k times: track count of max, shrink when count ≥ k
- Window with constraint on sum: shrink when exceeds, expand otherwise
Key insight for "at most k": Count of subarrays ending at r with at most k distinct = r - l + 1, where l is the leftmost valid start. This counts all valid right-ends for subarrays ending at r.
Template: right pointer always advances; left pointer shrinks when constraint violated.
- Exactly k distinct: atMost(k) - atMost(k-1)
- Min window with all chars: expand right, shrink left greedily
- Max element k times: track count of max, shrink when count ≥ k
- Window with constraint on sum: shrink when exceeds, expand otherwise
Key insight for "at most k": Count of subarrays ending at r with at most k distinct = r - l + 1, where l is the leftmost valid start. This counts all valid right-ends for subarrays ending at r.
Template: right pointer always advances; left pointer shrinks when constraint violated.