Pattern Guide
Sliding Window — Advanced Patterns
"At-most-k trick: exactly-k = at-most-k minus at-most-(k-1). Frequency-based windows."
Advanced sliding window patterns beyond the basics: (1) at-most-k trick to count subarrays with exactly k distinct elements; (2) minimum window with frequency constraints; (3) sliding window with deque for range max/min; (4) multiple-pointer windows for complex conditions. The "exactly k = at-most-k minus at-most-(k-1)" identity is the key trick for counting problems.
Problems you can solve with this pattern
4 problems · click any to start solving
// 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;
}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.
// 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;
}- 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.